Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
variable_and_expressions.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// IWYU pragma: private, include "ortools/math_opt/cpp/math_opt.h"
15// IWYU pragma: friend "ortools/math_opt/cpp/.*"
16
17// An object oriented wrapper for variables in ModelStorage (used internally by
18// Model) with support for arithmetic operations to build linear expressions and
19// express linear constraints.
20//
21// Types are:
22// - Variable: a reference to a variable of an ModelStorage.
23//
24// - LinearExpression: a weighted sum of variables with an optional offset;
25// something like `3*x + 2*y + 5`.
26//
27// - LinearTerm: a term of a linear expression, something like `2*x`. It is
28// used as an intermediate in the arithmetic operations that builds linear
29// expressions.
30//
31// - (Lower|Upper)BoundedLinearExpression: two classes representing the result
32// of the comparison of a LinearExpression with a constant. For example `3*x
33// + 2*y + 5 >= 3`.
34//
35// - BoundedLinearExpression: the result of the comparison of a linear
36// expression with two bounds, an upper bound and a lower bound. For example
37// `2 <= 3*x + 2*y + 5 <= 3`; or `4 >= 3*x + 2*y + 5 >= 1`.
38//
39// - QuadraticTermKey: a key used internally to represent a pair of Variables.
40//
41// - QuadraticTerm: a term representing the product of a scalar coefficient
42// and two Variables (possibly the same); something like `2*x*y` or `3*x*x`.
43// It is used as an intermediate in the arithmetic operations that build
44// quadratic expressions.
45//
46// - QuadraticExpression: a sum of a quadratic terms, linear terms, and a
47// scalar offset; something like `3*x*y + 2*x*x + 4x + 5`.
48//
49// - VariablesEquality: the result of comparing two Variable instances with
50// the == operator. For example `a == b`. This intermediate class support
51// implicit conversion to both bool and BoundedLinearExpression types. This
52// enables using variables as key of maps (using the conversion to bool)
53// without preventing adding constraints of variable equality.
54//
55// The basic arithmetic operators are overloaded for those types so that we can
56// write math expressions with variables to build linear expressions. The >=, <=
57// and == comparison operators are overloaded to produce BoundedLinearExpression
58// that can be used to build constraints.
59//
60// For example we can have:
61// const Variable x = ...;
62// const Variable y = ...;
63// const LinearExpression expr = 2 * x + 3 * y - 2;
64// const BoundedLinearExpression bounded_expr = 1 <= 2 * x + 3 * y - 2 <= 10;
65//
66// To making working with containers of doubles/Variables/LinearExpressions
67// easier, the template methods Sum() and InnerProduct() are provided, e.g.
68// const std::vector<int> ints = ...;
69// const std::vector<double> doubles = ...;
70// const std::vector<Variable> vars = ...;
71// const std::vector<LinearTerm> terms = ...;
72// const std::vector<LinearExpression> exprs = ...;
73// const LinearExpression s1 = Sum(ints);
74// const LinearExpression s2 = Sum(doubles);
75// const LinearExpression s3 = Sum(vars);
76// const LinearExpression s4 = Sum(terms);
77// const LinearExpression s5 = Sum(exprs);
78// const LinearExpression p1 = InnerProduct(ints, vars);
79// const LinearExpression p2 = InnerProduct(terms, doubles);
80// const LinearExpression p3 = InnerProduct(doubles, exprs);
81// These methods work on any iterable type (defining begin() and end()). For
82// InnerProduct, the inputs must be of equal size, and a compile time error will
83// be generated unless at least one input is a container of a type implicitly
84// convertible to double.
85//
86// Pre C++20, avoid the use of std::accumulate and std::inner_product with
87// LinearExpression, they cause a quadratic blowup in running time.
88//
89// While there is some complexity in the source, users typically should not need
90// to look at types other than Variable and LinearExpression too closely. Their
91// code usually will only refer to those types.
92#ifndef OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
93#define OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
94
95#include <stdint.h>
96
97#include <initializer_list>
98#include <iterator>
99#include <limits>
100#include <ostream>
101#include <string>
102#include <utility>
103
104#include "absl/container/flat_hash_map.h"
105#include "absl/log/check.h"
106#include "absl/log/log.h"
107#include "absl/strings/string_view.h"
108#include "ortools/math_opt/cpp/key_types.h" // IWYU pragma: export
112
113namespace operations_research {
114namespace math_opt {
115
116// Forward declaration needed by Variable.
117class LinearExpression;
118
119// A value type that references a variable from ModelStorage. Usually this type
120// is passed by copy.
121class Variable final : public ModelStorageElement<
122 ElementType::kVariable, Variable,
123 // This type has a special equality operator
124 // (see `VariablesEquality` below).
125 ModelStorageElementEquality::kWithoutEquality> {
126 public:
128
129 inline double lower_bound() const;
130 inline double upper_bound() const;
131 inline bool is_integer() const;
132 inline absl::string_view name() const;
133
134 inline LinearExpression operator-() const;
135};
136
137namespace internal {
138
139// The result of the equality comparison between two Variable.
140//
141// We use an object here to delay the evaluation of equality so that we can use
142// the operator== in two use-cases:
143//
144// 1. when the user want to test that two Variable values references the same
145// variable. This is supported by having this object support implicit
146// conversion to bool.
147//
148// 2. when the user want to use the equality to create a constraint of equality
149// between two variables.
151 // Users are not expected to call this constructor. Instead they should only
152 // use the overload of `operator==` that returns this when comparing two
153 // Variable. For example `x == y`.
155 inline operator bool() const; // NOLINT
158};
159
160} // namespace internal
161
163 const Variable& rhs);
164inline bool operator!=(const Variable& lhs, const Variable& rhs);
165
166template <typename V>
167using VariableMap = absl::flat_hash_map<Variable, V>;
168
169// A term in an sum of variables multiplied by coefficients.
171 // Usually this constructor is never called explicitly by users. Instead it
172 // will be implicitly used when writing linear expression. For example `x +
173 // 2*y` will automatically use this constructor to build a LinearTerm from `x`
174 // and the overload of the operator* will also automatically create the one
175 // from `2*y`.
176 inline LinearTerm(Variable variable, double coefficient);
177 inline LinearTerm operator-() const;
178 inline LinearTerm& operator*=(double d);
179 inline LinearTerm& operator/=(double d);
182};
183
184inline LinearTerm operator*(double coefficient, LinearTerm term);
185inline LinearTerm operator*(LinearTerm term, double coefficient);
186inline LinearTerm operator*(double coefficient, Variable variable);
187inline LinearTerm operator*(Variable variable, double coefficient);
188inline LinearTerm operator/(LinearTerm term, double coefficient);
189inline LinearTerm operator/(Variable variable, double coefficient);
190
191// Forward declaration so that we may add it as a friend to LinearExpression
193
194// This class represents a sum of variables multiplied by coefficient and an
195// optional offset constant. For example: "3*x + 2*y + 5".
196//
197// All operations, including constructor, will raise an assertion if the
198// operands involve variables from different Model objects.
199//
200// Contrary to Variable type, expressions owns the linear expression their
201// represent. Hence they are usually passed by reference to prevent unnecessary
202// copies.
203//
204// TODO(b/169415098): add a function to remove zero terms.
205// TODO(b/169415834): study if exact zeros should be automatically removed.
206// TODO(b/169415103): add tests that some expressions don't compile.
208 public:
209 // For unit testing purpose, we define optional counters. We have to
210 // explicitly define the default constructor, copy constructor and assignment
211 // operators in that case. Else we use the defaults.
212#ifndef MATH_OPT_USE_EXPRESSION_COUNTERS
213 LinearExpression() = default;
214 LinearExpression(const LinearExpression& other) = default;
215#else // MATH_OPT_USE_EXPRESSION_COUNTERS
218#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
219 // Usually users should use the overloads of operators to build linear
220 // expressions. For example, assuming `x` and `y` are Variable, then `x + 2*y
221 // + 5` will build a LinearExpression automatically.
222 inline LinearExpression(std::initializer_list<LinearTerm> terms,
223 double offset);
224 inline LinearExpression(double offset); // NOLINT
225 inline LinearExpression(Variable variable); // NOLINT
226 inline LinearExpression(const LinearTerm& term); // NOLINT
228 // A moved-from `LinearExpression` is the zero expression: it's not associated
229 // to a storage, has no terms and its offset is zero.
230 inline LinearExpression(LinearExpression&& other) noexcept;
231 inline LinearExpression& operator=(LinearExpression&& other) noexcept;
232
233 inline LinearExpression& operator+=(const LinearExpression& other);
234 inline LinearExpression& operator+=(const LinearTerm& term);
235 inline LinearExpression& operator+=(Variable variable);
236 inline LinearExpression& operator+=(double value);
237 inline LinearExpression& operator-=(const LinearExpression& other);
238 inline LinearExpression& operator-=(const LinearTerm& term);
239 inline LinearExpression& operator-=(Variable variable);
240 inline LinearExpression& operator-=(double value);
241 inline LinearExpression& operator*=(double value);
242 inline LinearExpression& operator/=(double value);
243
244 // Adds each element of items to this.
245 //
246 // Specifically, letting
247 // (i_1, i_2, ..., i_n) = items
248 // adds
249 // i_1 + i_2 + ... + i_n
250 // to this.
251 //
252 // Example:
253 // const Variable a = ...;
254 // const Variable b = ...;
255 // const std::vector<Variable> vars = {a, b};
256 // LinearExpression expr(8.0);
257 // expr.AddSum(vars);
258 // Results in expr having the value a + b + 8.0.
259 //
260 // Compile time requirements:
261 // * Iterable is a sequence (an array or object with begin() and end()).
262 // * The type of an element of items is one of double, Variable, LinearTerm
263 // or LinearExpression (or is implicitly convertible to one of these types,
264 // e.g. int).
265 //
266 // Note: The implementation is equivalent to:
267 // for(const auto item : items) {
268 // *this += item;
269 // }
270 template <typename Iterable>
271 inline void AddSum(const Iterable& items);
272
273 // Creates a new LinearExpression object equal to the sum. The implementation
274 // is equivalent to:
275 // LinearExpression expr;
276 // expr.AddSum(items);
277 template <typename Iterable>
278 static inline LinearExpression Sum(const Iterable& items);
279
280 // Adds the inner product of left and right to this.
281 //
282 // Specifically, letting
283 // (l_1, l_2 ..., l_n) = left,
284 // (r_1, r_2, ..., r_n) = right,
285 // adds
286 // l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n
287 // to this.
288 //
289 // Example:
290 // const Variable a = ...;
291 // const Variable b = ...;
292 // const std::vector<Variable> left = {a, b};
293 // const std::vector<double> right = {10.0, 2.0};
294 // LinearExpression expr(3.0);
295 // expr.AddInnerProduct(left, right)
296 // Results in expr having the value 10.0 * a + 2.0 * b + 3.0.
297 //
298 // Compile time requirements:
299 // * LeftIterable and RightIterable are both sequences (arrays or objects
300 // with begin() and end())
301 // * For both left and right, their elements a type of either double,
302 // Variable, LinearTerm or LinearExpression (or type implicitly convertible
303 // to one of these types, e.g. int).
304 // * At least one of left or right has elements with type double (or a type
305 // implicitly convertible, e.g. int).
306 // Runtime requirements (or CHECK fails):
307 // * left and right have an equal number of elements.
308 //
309 // Note: The implementation is equivalent to the following pseudocode:
310 // for(const auto& [l, r] : zip(left, right)) {
311 // *this += l * r;
312 // }
313 // In particular, the multiplication will be performed on the types of the
314 // elements in left and right (take care with low precision types), but the
315 // addition will always use double precision.
316 template <typename LeftIterable, typename RightIterable>
317 inline void AddInnerProduct(const LeftIterable& left,
318 const RightIterable& right);
319
320 // Creates a new LinearExpression object equal to the inner product. The
321 // implementation is equivalent to:
322 // LinearExpression expr;
323 // expr.AddInnerProduct(left, right);
324 template <typename LeftIterable, typename RightIterable>
325 static inline LinearExpression InnerProduct(const LeftIterable& left,
326 const RightIterable& right);
327
328 // Returns the terms in this expression.
329 inline const VariableMap<double>& terms() const;
330 inline double offset() const;
331
332 // Compute the numeric value of this expression when variables are substituted
333 // by their values in variable_values.
334 //
335 // Will CHECK fail if a variable in terms() is missing from variables_values.
336 double Evaluate(const VariableMap<double>& variable_values) const;
337
338 // Compute the numeric value of this expression when variables are substituted
339 // by their values in variable_values, or zero if missing from the map.
340 //
341 // This function won't check that the variables in the input map are indeed in
342 // the same model as the ones of the expression.
344 const VariableMap<double>& variable_values) const;
345
346#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
347 static thread_local int num_calls_default_constructor_;
348 static thread_local int num_calls_copy_constructor_;
349 static thread_local int num_calls_move_constructor_;
350 static thread_local int num_calls_initializer_list_constructor_;
351 // Reset all counters in the current thread to 0.
352 static void ResetCounters();
353#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
354
355 private:
357 friend std::ostream& operator<<(std::ostream& ostr,
358 const LinearExpression& expression);
359 friend QuadraticExpression;
360
361 // Invariants:
362 // * storage() == v.storage()for each v in terms_;
363 // * storage() == nullptr, if terms_ is empty.
364 VariableMap<double> terms_;
365 double offset_ = 0.0;
366};
367
368// Returns the sum of the elements of items as a LinearExpression.
369//
370// Specifically, letting
371// (i_1, i_2, ..., i_n) = items
372// returns
373// i_1 + i_2 + ... + i_n.
374//
375// Example:
376// const Variable a = ...;
377// const Variable b = ...;
378// const std::vector<Variable> vars = {a, b, a};
379// Sum(vars)
380// => 2.0 * a + b
381// Note, instead of:
382// LinearExpression expr(3.0);
383// expr += Sum(items);
384// Prefer:
385// expr.AddSum(items);
386//
387// See LinearExpression::AddSum() for a precise contract on the type Iterable.
388//
389// If the inner product cannot be represented as a LinearExpression, consider
390// instead QuadraticExpression::Sum().
391template <typename Iterable>
392inline LinearExpression Sum(const Iterable& items);
393
394// Returns the inner product of left and right as a LinearExpression.
395//
396// Specifically, letting
397// (l_1, l_2 ..., l_n) = left,
398// (r_1, r_2, ..., r_n) = right,
399// returns
400// l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n.
401//
402// Example:
403// const Variable a = ...;
404// const Variable b = ...;
405// const std::vector<Variable> left = {a, b};
406// const std::vector<double> right = {10.0, 2.0};
407// InnerProduct(left, right);
408// -=> 10.0 * a + 2.0 * b
409// Note, instead of:
410// LinearExpression expr(3.0);
411// expr += InnerProduct(left, right);
412// Prefer:
413// expr.AddInnerProduct(left, right);
414//
415// Requires that left and right have equal size, see
416// LinearExpression::AddInnerProduct for a precise contract on template types.
417//
418// If the inner product cannot be represented as a LinearExpression, consider
419// instead QuadraticExpression::InnerProduct().
420template <typename LeftIterable, typename RightIterable>
421inline LinearExpression InnerProduct(const LeftIterable& left,
422 const RightIterable& right);
423
424std::ostream& operator<<(std::ostream& ostr,
425 const LinearExpression& expression);
426
427// We intentionally pass one of the LinearExpression argument by value so
428// that we don't make unnecessary copies of temporary objects by using the move
429// constructor and the returned values optimization (RVO).
431inline LinearExpression operator+(Variable lhs, double rhs);
432inline LinearExpression operator+(double lhs, Variable rhs);
434inline LinearExpression operator+(const LinearTerm& lhs, double rhs);
435inline LinearExpression operator+(double lhs, const LinearTerm& rhs);
436inline LinearExpression operator+(const LinearTerm& lhs, Variable rhs);
437inline LinearExpression operator+(Variable lhs, const LinearTerm& rhs);
438inline LinearExpression operator+(const LinearTerm& lhs, const LinearTerm& rhs);
439inline LinearExpression operator+(LinearExpression lhs, double rhs);
440inline LinearExpression operator+(double lhs, LinearExpression rhs);
446 const LinearExpression& rhs);
447inline LinearExpression operator-(Variable lhs, double rhs);
448inline LinearExpression operator-(double lhs, Variable rhs);
450inline LinearExpression operator-(const LinearTerm& lhs, double rhs);
451inline LinearExpression operator-(double lhs, const LinearTerm& rhs);
452inline LinearExpression operator-(const LinearTerm& lhs, Variable rhs);
453inline LinearExpression operator-(Variable lhs, const LinearTerm& rhs);
454inline LinearExpression operator-(const LinearTerm& lhs, const LinearTerm& rhs);
455inline LinearExpression operator-(LinearExpression lhs, double rhs);
456inline LinearExpression operator-(double lhs, LinearExpression rhs);
462 const LinearExpression& rhs);
463inline LinearExpression operator*(LinearExpression lhs, double rhs);
464inline LinearExpression operator*(double lhs, LinearExpression rhs);
465inline LinearExpression operator/(LinearExpression lhs, double rhs);
466
467// A LinearExpression with a lower bound.
469 // Users are not expected to use this constructor. Instead, they should build
470 // this object using overloads of the >= and <= operators. For example, `x + y
471 // >= 3`.
473 double lower_bound);
476};
477
478// A LinearExpression with an upper bound.
480 // Users are not expected to use this constructor. Instead they should build
481 // this object using overloads of the >= and <= operators. For example, `x + y
482 // <= 3`.
484 double upper_bound);
487};
488
489// A LinearExpression with upper and lower bounds.
491 // Users are not expected to use this constructor. Instead they should build
492 // this object using overloads of the >=, <=, and == operators. For example,
493 // `3 <= x + y <= 3`.
495 double lower_bound, double upper_bound);
496 // Users are not expected to use this constructor. This implicit conversion
497 // will be used where a BoundedLinearExpression is expected and the user uses
498 // == comparison of two variables. For example `AddLinearConstraint(x == y);`.
499 inline BoundedLinearExpression( // NOLINT
501 inline BoundedLinearExpression( // NOLINT
502 LowerBoundedLinearExpression lb_expression);
503 inline BoundedLinearExpression( // NOLINT
504 UpperBoundedLinearExpression ub_expression);
505
506 // Returns the actual lower_bound after taking into account the linear
507 // expression offset.
508 inline double lower_bound_minus_offset() const;
509 // Returns the actual upper_bound after taking into account the linear
510 // expression offset.
511 inline double upper_bound_minus_offset() const;
512
516};
517
518std::ostream& operator<<(std::ostream& ostr,
519 const BoundedLinearExpression& bounded_expression);
520
521// We intentionally pass the LinearExpression argument by value so that we don't
522// make unnecessary copies of temporary objects by using the move constructor
523// and the returned values optimization (RVO).
525 double constant);
526inline LowerBoundedLinearExpression operator<=(double constant,
527 LinearExpression expression);
529 double constant);
530inline LowerBoundedLinearExpression operator<=(double constant,
531 const LinearTerm& term);
533 double constant);
534inline LowerBoundedLinearExpression operator<=(double constant,
535 Variable variable);
537 double constant);
538inline UpperBoundedLinearExpression operator>=(double constant,
539 LinearExpression expression);
541 double constant);
542inline UpperBoundedLinearExpression operator>=(double constant,
543 const LinearTerm& term);
545 double constant);
546inline UpperBoundedLinearExpression operator>=(double constant,
547 Variable variable);
548
549// We intentionally pass the UpperBoundedLinearExpression and
550// LowerBoundedLinearExpression arguments by value so that we don't
551// make unnecessary copies of temporary objects by using the move constructor
552// and the returned values optimization (RVO).
554 double rhs);
555inline BoundedLinearExpression operator>=(double lhs,
558 double rhs);
559inline BoundedLinearExpression operator<=(double lhs,
561// We intentionally pass one LinearExpression argument by value so that we don't
562// make unnecessary copies of temporary objects by using the move constructor
563// and the returned values optimization (RVO).
565 const LinearExpression& rhs);
567 const LinearExpression& rhs);
569 const LinearTerm& rhs);
571 const LinearTerm& rhs);
573 LinearExpression rhs);
575 LinearExpression rhs);
581 const LinearTerm& rhs);
583 const LinearTerm& rhs);
591 const LinearExpression& rhs);
593 const LinearTerm& rhs);
595 LinearExpression rhs);
601 const LinearTerm& rhs);
604inline BoundedLinearExpression operator==(const LinearTerm& lhs, double rhs);
605inline BoundedLinearExpression operator==(double lhs, const LinearTerm& rhs);
606inline BoundedLinearExpression operator==(Variable lhs, double rhs);
607inline BoundedLinearExpression operator==(double lhs, Variable rhs);
608
609// Id type used for quadratic terms, i.e. products of two variables.
610using QuadraticProductId = std::pair<VariableId, VariableId>;
611
612// Couples a QuadraticProductId with a ModelStorage, for use with IdMaps.
613// Namely, this key type satisfies the requirements stated in key_types.h.
614// Invariant:
615// * variable_ids_.first <= variable_ids_.second. The constructor will
616// silently correct this if not satisfied by the inputs.
617//
618// This type can be used as a key in ABSL hash containers.
619class QuadraticTermKey final : public ModelStorageItem {
620 public:
621 // NOTE: this definition is for use by IdMap; clients should not rely upon it.
623
624 // NOTE: This constructor will silently re-order the passed id so that, upon
625 // exiting the constructor, variable_ids_.first <= variable_ids_.second.
627 // NOTE: This constructor will CHECK fail if the variable models do not agree,
628 // i.e. first_variable.storage() != second_variable.storage(). It will also
629 // silently re-order the passed id so that, upon exiting the constructor,
630 // variable_ids_.first <= variable_ids_.second.
631 inline QuadraticTermKey(Variable first_variable, Variable second_variable);
632
633 inline QuadraticProductId typed_id() const;
634
635 // Returns the Variable with the smallest id.
636 Variable first() const { return Variable(storage(), variable_ids_.first); }
637
638 // Returns the Variable the largest id.
639 Variable second() const { return Variable(storage(), variable_ids_.second); }
640
641 template <typename H>
642 friend H AbslHashValue(H h, const QuadraticTermKey& key);
643
644 private:
645 QuadraticProductId variable_ids_;
646};
647
648inline std::ostream& operator<<(std::ostream& ostr,
649 const QuadraticTermKey& key);
650
651inline bool operator==(QuadraticTermKey lhs, QuadraticTermKey rhs);
652inline bool operator!=(QuadraticTermKey lhs, QuadraticTermKey rhs);
653
654// Represents a quadratic term in a sum: coefficient * variable_1 * variable_2.
655// Invariant:
656// * first_variable.storage() == second_variable.storage(). The constructor
657// will CHECK fail if not satisfied.
659 public:
660 QuadraticTerm() = delete;
661 // NOTE: This will CHECK fail if
662 // first_variable.storage() != second_variable.storage().
664 double coefficient);
665
666 inline double coefficient() const;
667 inline Variable first_variable() const;
668 inline Variable second_variable() const;
669
670 // This is useful for working with IdMaps
671 inline QuadraticTermKey GetKey() const;
672
673 inline QuadraticTerm& operator*=(double value);
674 inline QuadraticTerm& operator/=(double value);
675
676 private:
678 friend QuadraticTerm operator*(double lhs, QuadraticTerm rhs);
679 friend QuadraticTerm operator*(QuadraticTerm lhs, double rhs);
680 friend QuadraticTerm operator/(QuadraticTerm lhs, double rhs);
681
682 Variable first_variable_;
683 Variable second_variable_;
684 double coefficient_;
685};
686// We declare those operator overloads that result in a QuadraticTerm, stated in
687// lexicographic ordering based on lhs type, rhs type):
689inline QuadraticTerm operator*(double lhs, QuadraticTerm rhs);
694inline QuadraticTerm operator*(QuadraticTerm lhs, double rhs);
695inline QuadraticTerm operator/(QuadraticTerm lhs, double rhs);
696
697template <typename V>
698using QuadraticTermMap = absl::flat_hash_map<QuadraticTermKey, V>;
699
700// This class represents a sum of quadratic terms, linear terms, and constant
701// offset. For example: "3*x*y + 2*x + 1".
702//
703// Mixing terms involving variables from different ModelStorage objects will
704// lead to CHECK fails, including from the constructors.
705//
706// The type owns the associated data representing the terms, and so should
707// usually be passed by (const) reference to avoid unnecessary copies.
708//
709// Note for implementers: Care must be taken to ensure that
710// linear_terms_.storage() and quadratic_terms_.storage() do not disagree. That
711// is, it is forbidden that both are non-null and not equal. Use
712// CheckModelsAgree() and the initializer_list constructor to enforce this
713// invariant in any class or friend method.
715 public:
716 // For unit testing purpose, we define optional counters. We have to
717 // explicitly define the default constructor, copy constructor and assignment
718 // operators in that case. Else we use the defaults.
719#ifndef MATH_OPT_USE_EXPRESSION_COUNTERS
722#else // MATH_OPT_USE_EXPRESSION_COUNTERS
725#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
726 // Users should prefer the default constructor and operator overloads to build
727 // expressions.
728 inline QuadraticExpression(
729 std::initializer_list<QuadraticTerm> quadratic_terms,
730 std::initializer_list<LinearTerm> linear_terms, double offset);
731 inline QuadraticExpression(double offset); // NOLINT
732 inline QuadraticExpression(Variable variable); // NOLINT
733 inline QuadraticExpression(const LinearTerm& term); // NOLINT
734 inline QuadraticExpression(LinearExpression expr); // NOLINT
735 inline QuadraticExpression(const QuadraticTerm& term); // NOLINT
737 // A moved-from `LinearExpression` is the zero expression: it's not associated
738 // to a storage, has no terms and its offset is zero.
739 inline QuadraticExpression(QuadraticExpression&& other) noexcept;
740 inline QuadraticExpression& operator=(QuadraticExpression&& other) noexcept;
741
742 inline double offset() const;
743 inline const VariableMap<double>& linear_terms() const;
744 inline const QuadraticTermMap<double>& quadratic_terms() const;
745
746 inline QuadraticExpression& operator+=(double value);
747 inline QuadraticExpression& operator+=(Variable variable);
748 inline QuadraticExpression& operator+=(const LinearTerm& term);
750 inline QuadraticExpression& operator+=(const QuadraticTerm& term);
752 inline QuadraticExpression& operator-=(double value);
753 inline QuadraticExpression& operator-=(Variable variable);
754 inline QuadraticExpression& operator-=(const LinearTerm& term);
756 inline QuadraticExpression& operator-=(const QuadraticTerm& term);
758 inline QuadraticExpression& operator*=(double value);
759 inline QuadraticExpression& operator/=(double value);
760
761 // Adds each element of items to this.
762 //
763 // Specifically, letting
764 // (i_1, i_2, ..., i_n) = items
765 // adds
766 // i_1 + i_2 + ... + i_n
767 // to this.
768 //
769 // Example:
770 // const Variable a = ...;
771 // const Variable b = ...;
772 // const std::vector<Variable> vars = {a, b};
773 // const std::vector<QuadraticTerm> terms = {2 * a * b};
774 // QuadraticExpression expr = 8;
775 // expr.AddSum(vars);
776 // expr.AddSum(terms);
777 // Results in expr having the value 2 * a * b + a + b + 8.0.
778 //
779 // Compile time requirements:
780 // * Iterable is a sequence (an array or object with begin() and end()).
781 // * The type of an element of items is one of double, Variable, LinearTerm,
782 // LinearExpression, QuadraticTerm, or QuadraticExpression (or is
783 // implicitly convertible to one of these types, e.g. int).
784 //
785 // Note: The implementation is equivalent to:
786 // for(const auto item : items) {
787 // *this += item;
788 // }
789 template <typename Iterable>
790 inline void AddSum(const Iterable& items);
791
792 // Returns the sum of the elements of items.
793 //
794 // Specifically, letting
795 // (i_1, i_2, ..., i_n) = items
796 // returns
797 // i_1 + i_2 + ... + i_n.
798 //
799 // Example:
800 // const Variable a = ...;
801 // const Variable b = ...;
802 // const std::vector<QuadraticTerm> terms = {a * a, 2 * a * b, 3 * b * a};
803 // QuadraticExpression::Sum(vars)
804 // => a^2 + 5 a * b
805 // Note, instead of:
806 // QuadraticExpression expr(3.0);
807 // expr += QuadraticExpression::Sum(items);
808 // Prefer:
809 // expr.AddSum(items);
810 //
811 // See QuadraticExpression::AddSum() for a precise contract on the type
812 // Iterable.
813 template <typename Iterable>
814 static inline QuadraticExpression Sum(const Iterable& items);
815
816 // Adds the inner product of left and right to this.
817 //
818 // Specifically, letting
819 // (l_1, l_2 ..., l_n) = left,
820 // (r_1, r_2, ..., r_n) = right,
821 // adds
822 // l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n
823 // to this.
824 //
825 // Example:
826 // const Variable a = ...;
827 // const Variable b = ...;
828 // const std::vector<Variable> vars = {a, b};
829 // const std::vector<double> coeffs = {10.0, 2.0};
830 // QuadraticExpression expr = 3.0;
831 // expr.AddInnerProduct(coeffs, vars);
832 // expr.AddInnerProduct(vars, vars);
833 // Results in expr having the value a^2 + b^2 + 10.0 * a + 2.0 * b + 3.0.
834 //
835 // Compile time requirements:
836 // * LeftIterable and RightIterable are both sequences (arrays or objects
837 // with begin() and end())
838 // * For both left and right, their elements are of type double, Variable,
839 // LinearTerm, LinearExpression, QuadraticTerm, or QuadraticExpression (or
840 // is implicitly convertible to one of these types, e.g. int).
841 // Runtime requirements (or CHECK fails):
842 // * The inner product value, and its constitutive intermediate terms, can be
843 // represented as a QuadraticExpression (potentially through an implicit
844 // conversion).
845 // * left and right have an equal number of elements.
846 //
847 // Note: The implementation is equivalent to the following pseudocode:
848 // for(const auto& [l, r] : zip(left, right)) {
849 // *this += l * r;
850 // }
851 // In particular, the multiplication will be performed on the types of the
852 // elements in left and right (take care with low precision types), but the
853 // addition will always use double precision.
854 template <typename LeftIterable, typename RightIterable>
855 inline void AddInnerProduct(const LeftIterable& left,
856 const RightIterable& right);
857
858 // Returns the inner product of left and right.
859 //
860 // Specifically, letting
861 // (l_1, l_2 ..., l_n) = left,
862 // (r_1, r_2, ..., r_n) = right,
863 // returns
864 // l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n.
865 //
866 // Example:
867 // const Variable a = ...;
868 // const Variable b = ...;
869 // const std::vector<Variable> left = {a, a};
870 // const std::vector<Variable> left = {a, b};
871 // QuadraticExpression::InnerProduct(left, right);
872 // -=> a^2 + a * b
873 // Note, instead of:
874 // QuadraticExpression expr(3.0);
875 // expr += QuadraticExpression::InnerProduct(left, right);
876 // Prefer:
877 // expr.AddInnerProduct(left, right);
878 //
879 // Requires that left and right have equal size, see
880 // QuadraticExpression::AddInnerProduct() for a precise contract on template
881 // types.
882 template <typename LeftIterable, typename RightIterable>
883 static inline QuadraticExpression InnerProduct(const LeftIterable& left,
884 const RightIterable& right);
885
886 // Compute the numeric value of this expression when variables are substituted
887 // by their values in variable_values.
888 //
889 // Will CHECK fail if a variable in linear_terms() or quadratic_terms() is
890 // missing from variables_values.
891 double Evaluate(const VariableMap<double>& variable_values) const;
892
893 // Compute the numeric value of this expression when variables are substituted
894 // by their values in variable_values, or zero if missing from the map.
895 //
896 // This function won't check that the variables in the input map are indeed in
897 // the same model as the ones of the expression.
899 const VariableMap<double>& variable_values) const;
900
901#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
902 static thread_local int num_calls_default_constructor_;
903 static thread_local int num_calls_copy_constructor_;
904 static thread_local int num_calls_move_constructor_;
905 static thread_local int num_calls_initializer_list_constructor_;
906 static thread_local int num_calls_linear_expression_constructor_;
907 // Reset all counters in the current thread to 0.
908 static void ResetCounters();
909#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
910
911 private:
913 friend std::ostream& operator<<(std::ostream& ostr,
914 const QuadraticExpression& expr);
915
916 // Invariants:
917 // * storage() == v.storage() for each v in linear_terms_;
918 // * storage() == v.storage() for each v in quadratic_terms_;
919 // * storage() == nullptr, if both terms_ and quadratic_terms_ are empty.
920 QuadraticTermMap<double> quadratic_terms_;
921 VariableMap<double> linear_terms_;
922 double offset_ = 0.0;
923};
924
925// We have 6 types that we must consider arithmetic among:
926// 1. double (scalar value)
927// 2. Variable (affine value)
928// 3. LinearTerm (affine value)
929// 4. LinearExpression (affine value)
930// 5. QuadraticTerm (quadratic value)
931// 6. QuadraticExpression (quadratic value)
932// We care only about those methods that result in a QuadraticExpression. For
933// example, multiplying a linear value with a linear value, or adding a scalar
934// to a quadratic value. The single unary method is:
936
937// The binary methods, listed in lexicographic order based on
938// (operator, lhs type #, rhs type #), with the type #s are listed above, are:
939inline QuadraticExpression operator+(double lhs, const QuadraticTerm& rhs);
944 const QuadraticTerm& rhs);
948 const QuadraticTerm& rhs);
951inline QuadraticExpression operator+(const QuadraticTerm& lhs, double rhs);
954 const LinearTerm& rhs);
956 LinearExpression rhs);
958 const QuadraticTerm& rhs);
964 const LinearTerm& rhs);
966 const LinearExpression& rhs);
968 const QuadraticTerm& rhs);
970 const QuadraticExpression& rhs);
971
972inline QuadraticExpression operator-(double lhs, const QuadraticTerm& rhs);
977 const QuadraticTerm& rhs);
981 const QuadraticTerm& rhs);
984inline QuadraticExpression operator-(const QuadraticTerm& lhs, double rhs);
987 const LinearTerm& rhs);
989 LinearExpression rhs);
991 const QuadraticTerm& rhs);
997 const LinearTerm& rhs);
999 const LinearExpression& rhs);
1001 const QuadraticTerm& rhs);
1003 const QuadraticExpression& rhs);
1004
1005inline QuadraticExpression operator*(double lhs, QuadraticExpression rhs);
1008 const LinearExpression& rhs);
1011 LinearTerm rhs);
1013 const LinearExpression& rhs);
1014inline QuadraticExpression operator*(QuadraticExpression lhs, double rhs);
1015
1016inline QuadraticExpression operator/(QuadraticExpression lhs, double rhs);
1017
1018// A QuadraticExpression with a lower bound.
1020 // Users are not expected to use this constructor. Instead, they should build
1021 // this object using overloads of the >= and <= operators. For example, `x * y
1022 // >= 3`.
1024 double lower_bound);
1025 // Users are not expected to explicitly use the following constructor.
1026 inline LowerBoundedQuadraticExpression( // NOLINT
1027 LowerBoundedLinearExpression lb_expression);
1028
1031};
1032
1033// A QuadraticExpression with an upper bound.
1035 // Users are not expected to use this constructor. Instead, they should build
1036 // this object using overloads of the >= and <= operators. For example, `x * y
1037 // <= 3`.
1039 double upper_bound);
1040 // Users are not expected to explicitly use the following constructor.
1041 inline UpperBoundedQuadraticExpression( // NOLINT
1042 UpperBoundedLinearExpression ub_expression);
1043
1046};
1047
1048// A QuadraticExpression with upper and lower bounds.
1050 // Users are not expected to use this constructor. Instead, they should build
1051 // this object using overloads of the >=, <=, and == operators. For example,
1052 // `3 <= x * y <= 3`.
1054 double lower_bound, double upper_bound);
1055
1056 // Users are not expected to explicitly use the following constructors.
1057 inline BoundedQuadraticExpression( // NOLINT
1058 internal::VariablesEquality var_equality);
1059 inline BoundedQuadraticExpression( // NOLINT
1060 LowerBoundedLinearExpression lb_expression);
1061 inline BoundedQuadraticExpression( // NOLINT
1062 UpperBoundedLinearExpression ub_expression);
1063 inline BoundedQuadraticExpression( // NOLINT
1064 BoundedLinearExpression bounded_expression);
1065 inline BoundedQuadraticExpression( // NOLINT
1066 LowerBoundedQuadraticExpression lb_expression);
1067 inline BoundedQuadraticExpression( // NOLINT
1068 UpperBoundedQuadraticExpression ub_expression);
1069
1070 // Returns the actual lower_bound after taking into account the quadratic
1071 // expression offset.
1072 inline double lower_bound_minus_offset() const;
1073 // Returns the actual upper_bound after taking into account the quadratic
1074 // expression offset.
1075 inline double upper_bound_minus_offset() const;
1076
1080};
1081
1082std::ostream& operator<<(std::ostream& ostr,
1083 const BoundedQuadraticExpression& bounded_expression);
1084
1085// We intentionally pass the QuadraticExpression argument by value so that we
1086// don't make unnecessary copies of temporary objects by using the move
1087// constructor and the returned values optimization (RVO).
1089 double rhs);
1091 double rhs);
1095 QuadraticTerm rhs);
1096
1100 QuadraticTerm rhs);
1102 double rhs);
1104 double rhs);
1105
1106// We intentionally pass the UpperBoundedQuadraticExpression and
1107// LowerBoundedQuadraticExpression arguments by value so that we don't
1108// make unnecessary copies of temporary objects by using the move constructor
1109// and the returned values optimization (RVO).
1111 UpperBoundedQuadraticExpression lhs, double rhs);
1113 double lhs, LowerBoundedQuadraticExpression rhs);
1115 LowerBoundedQuadraticExpression lhs, double rhs);
1117 double lhs, UpperBoundedQuadraticExpression rhs);
1118// We intentionally pass one QuadraticExpression argument by value so that we
1119// don't make unnecessary copies of temporary objects by using the move
1120// constructor and the returned values optimization (RVO).
1121
1122// Comparisons with lhs = QuadraticExpression
1124 const QuadraticExpression& rhs);
1126 QuadraticTerm rhs);
1128 const LinearExpression& rhs);
1130 LinearTerm rhs);
1132 Variable rhs);
1134 const QuadraticExpression& rhs);
1136 QuadraticTerm rhs);
1138 const LinearExpression& rhs);
1140 LinearTerm rhs);
1142 Variable rhs);
1144 const QuadraticExpression& rhs);
1146 QuadraticTerm rhs);
1148 const LinearExpression& rhs);
1150 LinearTerm rhs);
1152 Variable rhs);
1154 double rhs);
1155// Comparisons with lhs = QuadraticTerm
1159 QuadraticTerm rhs);
1161 LinearExpression rhs);
1167 QuadraticTerm rhs);
1169 LinearExpression rhs);
1175 QuadraticTerm rhs);
1177 LinearExpression rhs);
1181// Comparisons with lhs = LinearExpression
1185 QuadraticTerm rhs);
1189 QuadraticTerm rhs);
1193 QuadraticTerm rhs);
1194// Comparisons with lhs = LinearTerm
1204// Comparisons with lhs = Variable
1214// Comparisons with lhs = Double
1216inline BoundedQuadraticExpression operator==(double lhs,
1218
1221// Inline function implementations /////////////////////////////////////////////
1224
1226// Variable
1228
1229double Variable::lower_bound() const {
1230 return storage()->variable_lower_bound(typed_id());
1231}
1232
1233double Variable::upper_bound() const {
1234 return storage()->variable_upper_bound(typed_id());
1236
1237bool Variable::is_integer() const {
1238 return storage()->is_variable_integer(typed_id());
1240
1241absl::string_view Variable::name() const {
1242 if (storage()->has_variable(typed_id())) {
1243 return storage()->variable_name(typed_id());
1244 }
1245 return "[variable deleted from model]";
1246}
1249 return LinearExpression({LinearTerm(*this, -1.0)}, 0.0);
1250}
1251
1253// LinearTerm
1254////////////////////////////////////////////////////////////////////////////////
1255
1256LinearTerm::LinearTerm(Variable variable, const double coefficient)
1257 : variable(std::move(variable)), coefficient(coefficient) {}
1258
1261}
1262
1263LinearTerm& LinearTerm::operator*=(const double d) {
1265 return *this;
1266}
1268LinearTerm& LinearTerm::operator/=(const double d) {
1269 coefficient /= d;
1270 return *this;
1272
1273LinearTerm operator*(const double coefficient, LinearTerm term) {
1274 term *= coefficient;
1275 return term;
1277
1278LinearTerm operator*(LinearTerm term, const double coefficient) {
1279 term *= coefficient;
1280 return term;
1282
1283LinearTerm operator*(const double coefficient, Variable variable) {
1284 return LinearTerm(std::move(variable), coefficient);
1285}
1287LinearTerm operator*(Variable variable, const double coefficient) {
1288 return LinearTerm(std::move(variable), coefficient);
1289}
1290
1291LinearTerm operator/(LinearTerm term, const double coefficient) {
1292 term /= coefficient;
1293 return term;
1294}
1296LinearTerm operator/(Variable variable, const double coefficient) {
1297 return LinearTerm(std::move(variable), 1 / coefficient);
1298}
1301// LinearExpression
1303
1307 terms_(std::move(other.terms_)),
1308 offset_(std::exchange(other.offset_, 0.0)) {
1309 other.terms_.clear();
1310#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
1311 ++num_calls_move_constructor_;
1312#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
1313}
1316 LinearExpression&& other) noexcept {
1318 static_cast<ModelStorageItemContainer&&>(other));
1319 terms_ = std::move(other.terms_);
1320 other.terms_.clear();
1321 offset_ = std::exchange(other.offset_, 0.0);
1322 return *this;
1323}
1324
1325LinearExpression::LinearExpression(std::initializer_list<LinearTerm> terms,
1326 const double offset)
1327 : offset_(offset) {
1328#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
1329 ++num_calls_initializer_list_constructor_;
1330#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
1331 for (const auto& term : terms) {
1332 SetOrCheckStorage(term.variable);
1333 // The same variable may appear multiple times in the input list; we must
1334 // accumulate the coefficients.
1335 terms_[term.variable] += term.coefficient;
1336 }
1337}
1338
1340 : LinearExpression({}, offset) {}
1341
1343 : LinearExpression({LinearTerm(variable, 1.0)}, 0.0) {}
1344
1346 : LinearExpression({term}, 0.0) {}
1347
1349 expr.offset_ = -expr.offset_;
1350 for (auto& term : expr.terms_) {
1351 term.second = -term.second;
1353 return expr;
1354}
1356LinearExpression operator+(const Variable lhs, const double rhs) {
1357 return LinearTerm(lhs, 1.0) + rhs;
1359
1360LinearExpression operator+(const double lhs, const Variable rhs) {
1361 return lhs + LinearTerm(rhs, 1.0);
1362}
1363
1364LinearExpression operator+(const Variable lhs, const Variable rhs) {
1365 return LinearTerm(lhs, 1.0) + LinearTerm(rhs, 1.0);
1367
1368LinearExpression operator+(const LinearTerm& lhs, const double rhs) {
1369 return LinearExpression({lhs}, rhs);
1371
1372LinearExpression operator+(const double lhs, const LinearTerm& rhs) {
1373 return LinearExpression({rhs}, lhs);
1375
1376LinearExpression operator+(const LinearTerm& lhs, const Variable rhs) {
1377 return lhs + LinearTerm(rhs, 1.0);
1379
1380LinearExpression operator+(const Variable lhs, const LinearTerm& rhs) {
1381 return LinearTerm(lhs, 1.0) + rhs;
1383
1384LinearExpression operator+(const LinearTerm& lhs, const LinearTerm& rhs) {
1385 return LinearExpression({lhs, rhs}, 0);
1387
1388LinearExpression operator+(LinearExpression lhs, const double rhs) {
1389 lhs += rhs;
1390 return lhs;
1391}
1392
1393LinearExpression operator+(const double lhs, LinearExpression rhs) {
1394 rhs += lhs;
1395 return rhs;
1396}
1397
1399 return std::move(lhs) + LinearTerm(rhs, 1.0);
1400}
1401
1402LinearExpression operator+(const Variable lhs, LinearExpression rhs) {
1403 return LinearTerm(lhs, 1.0) + std::move(rhs);
1404}
1405
1406LinearExpression operator+(LinearExpression lhs, const LinearTerm& rhs) {
1407 lhs += rhs;
1408 return lhs;
1409}
1410
1411LinearExpression operator+(LinearTerm lhs, LinearExpression rhs) {
1412 rhs += lhs;
1413 return rhs;
1414}
1415
1417 lhs += rhs;
1418 return lhs;
1419}
1420
1421LinearExpression operator-(const Variable lhs, const double rhs) {
1422 return LinearTerm(lhs, 1.0) - rhs;
1423}
1424
1425LinearExpression operator-(const double lhs, const Variable rhs) {
1426 return lhs - LinearTerm(rhs, 1.0);
1427}
1428
1429LinearExpression operator-(const Variable lhs, const Variable rhs) {
1430 return LinearTerm(lhs, 1.0) - LinearTerm(rhs, 1.0);
1432
1433LinearExpression operator-(const LinearTerm& lhs, const double rhs) {
1434 return LinearExpression({lhs}, -rhs);
1436
1437LinearExpression operator-(const double lhs, const LinearTerm& rhs) {
1438 return LinearExpression({-rhs}, lhs);
1440
1441LinearExpression operator-(const LinearTerm& lhs, const Variable rhs) {
1442 return lhs - LinearTerm(rhs, 1.0);
1444
1445LinearExpression operator-(const Variable lhs, const LinearTerm& rhs) {
1446 return LinearTerm(lhs, 1.0) - rhs;
1448
1449LinearExpression operator-(const LinearTerm& lhs, const LinearTerm& rhs) {
1450 return LinearExpression({lhs, -rhs}, 0);
1452
1453LinearExpression operator-(LinearExpression lhs, const double rhs) {
1454 lhs -= rhs;
1455 return lhs;
1456}
1457
1458LinearExpression operator-(const double lhs, LinearExpression rhs) {
1459 auto ret = -std::move(rhs);
1460 ret += lhs;
1461 return ret;
1462}
1465 return std::move(lhs) - LinearTerm(rhs, 1.0);
1466}
1467
1469 return LinearTerm(lhs, 1.0) - std::move(rhs);
1470}
1471
1472LinearExpression operator-(LinearExpression lhs, const LinearTerm& rhs) {
1473 lhs -= rhs;
1474 return lhs;
1475}
1476
1477LinearExpression operator-(LinearTerm lhs, LinearExpression rhs) {
1478 auto ret = -std::move(rhs);
1479 ret += lhs;
1480 return ret;
1481}
1484 lhs -= rhs;
1485 return lhs;
1486}
1488LinearExpression operator*(LinearExpression lhs, const double rhs) {
1489 lhs *= rhs;
1490 return lhs;
1491}
1492
1494 rhs *= lhs;
1495 return rhs;
1496}
1497
1499 lhs /= rhs;
1500 return lhs;
1501}
1502
1504 // Here we know that each key in other.terms_ has already been checked and
1505 // thus we don't need to compare in the loop. Of course this only applies if
1506 // the other has terms.
1507 if (!other.terms_.empty()) {
1509 for (const auto& [v, coeff] : other.terms_) {
1510 terms_[v] += coeff;
1511 }
1512 }
1513 offset_ += other.offset_;
1514 return *this;
1515}
1516
1519 terms_[term.variable] += term.coefficient;
1520 return *this;
1521}
1522
1523LinearExpression& LinearExpression::operator+=(const Variable variable) {
1524 SetOrCheckStorage(variable);
1525 return *this += LinearTerm(variable, 1.0);
1526}
1529 offset_ += value;
1530 return *this;
1531}
1532
1534 // See operator+=.
1535 if (!other.terms_.empty()) {
1536 SetOrCheckStorage(other);
1537 for (const auto& [v, coeff] : other.terms_) {
1538 terms_[v] -= coeff;
1539 }
1540 }
1541 offset_ -= other.offset_;
1542 return *this;
1544
1547 terms_[term.variable] -= term.coefficient;
1548 return *this;
1549}
1550
1551LinearExpression& LinearExpression::operator-=(const Variable variable) {
1552 SetOrCheckStorage(variable);
1553 return *this -= LinearTerm(variable, 1.0);
1554}
1557 offset_ -= value;
1558 return *this;
1559}
1560
1562 offset_ *= value;
1563 for (auto& term : terms_) {
1564 term.second *= value;
1565 }
1566 return *this;
1567}
1568
1570 offset_ /= value;
1571 for (auto& term : terms_) {
1572 term.second /= value;
1573 }
1574 return *this;
1575}
1576
1577template <typename Iterable>
1578void LinearExpression::AddSum(const Iterable& items) {
1579 for (const auto& item : items) {
1580 *this += item;
1581 }
1582}
1583
1584template <typename Iterable>
1585LinearExpression LinearExpression::Sum(const Iterable& items) {
1586 LinearExpression result;
1587 result.AddSum(items);
1588 return result;
1589}
1590
1591template <typename Iterable>
1592LinearExpression Sum(const Iterable& items) {
1593 return LinearExpression::Sum(items);
1594}
1596namespace internal {
1597
1598template <typename LeftIterable, typename RightIterable, typename Expression>
1599void AddInnerProduct(const LeftIterable& left, const RightIterable& right,
1600 Expression& expr) {
1601 using std::begin;
1602 using std::end;
1603 auto l = begin(left);
1604 auto r = begin(right);
1605 const auto l_end = end(left);
1606 const auto r_end = end(right);
1607 for (; l != l_end && r != r_end; ++l, ++r) {
1608 expr += (*l) * (*r);
1610 CHECK(l == l_end)
1611 << "left had more elements than right, sizes should be equal";
1612 CHECK(r == r_end)
1613 << "right had more elements than left, sizes should be equal";
1614}
1615
1616} // namespace internal
1617
1618template <typename LeftIterable, typename RightIterable>
1619void LinearExpression::AddInnerProduct(const LeftIterable& left,
1620 const RightIterable& right) {
1621 internal::AddInnerProduct(left, right, *this);
1622}
1623
1624template <typename LeftIterable, typename RightIterable>
1625LinearExpression LinearExpression::InnerProduct(const LeftIterable& left,
1626 const RightIterable& right) {
1627 LinearExpression result;
1628 result.AddInnerProduct(left, right);
1629 return result;
1630}
1631
1632template <typename LeftIterable, typename RightIterable>
1633LinearExpression InnerProduct(const LeftIterable& left,
1634 const RightIterable& right) {
1636}
1637
1638const VariableMap<double>& LinearExpression::terms() const { return terms_; }
1639
1640double LinearExpression::offset() const { return offset_; }
1641
1643// VariablesEquality
1645
1646namespace internal {
1647
1649 : lhs(std::move(lhs)), rhs(std::move(rhs)) {}
1651inline VariablesEquality::operator bool() const {
1652 return lhs.typed_id() == rhs.typed_id() && lhs.storage() == rhs.storage();
1653}
1654
1655} // namespace internal
1656
1657internal::VariablesEquality operator==(const Variable& lhs,
1658 const Variable& rhs) {
1659 return internal::VariablesEquality(lhs, rhs);
1661
1662bool operator!=(const Variable& lhs, const Variable& rhs) {
1663 return !(lhs == rhs);
1664}
1665
1666
1667// LowerBoundedLinearExpression
1668// UpperBoundedLinearExpression
1673 LinearExpression expression, const double lower_bound)
1674 : expression(std::move(expression)), lower_bound(lower_bound) {}
1675
1676UpperBoundedLinearExpression::UpperBoundedLinearExpression(
1677 LinearExpression expression, const double upper_bound)
1678 : expression(std::move(expression)), upper_bound(upper_bound) {}
1679
1680BoundedLinearExpression::BoundedLinearExpression(LinearExpression expression,
1681 const double lower_bound,
1682 const double upper_bound)
1683 : expression(std::move(expression)),
1684 lower_bound(lower_bound),
1685 upper_bound(upper_bound) {}
1689 : expression({{eq.lhs, 1.0}, {eq.rhs, -1.0}}, 0.0),
1690 lower_bound(0.0),
1691 upper_bound(0.0) {}
1692
1695 : expression(std::move(lb_expression.expression)),
1696 lower_bound(lb_expression.lower_bound),
1697 upper_bound(std::numeric_limits<double>::infinity()) {}
1698
1700 UpperBoundedLinearExpression ub_expression)
1701 : expression(std::move(ub_expression.expression)),
1702 lower_bound(-std::numeric_limits<double>::infinity()),
1703 upper_bound(ub_expression.upper_bound) {}
1704
1706 return lower_bound - expression.offset();
1708
1710 return upper_bound - expression.offset();
1711}
1712
1714 const double constant) {
1715 return LowerBoundedLinearExpression(std::move(expression), constant);
1716}
1717
1718LowerBoundedLinearExpression operator<=(const double constant,
1720 return LowerBoundedLinearExpression(std::move(expression), constant);
1721}
1722
1724 const double constant) {
1725 return LowerBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1726}
1728LowerBoundedLinearExpression operator<=(const double constant,
1729 const LinearTerm& term) {
1730 return LowerBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1731}
1734 const double constant) {
1735 return LinearTerm(variable, 1.0) >= constant;
1736}
1738LowerBoundedLinearExpression operator<=(const double constant,
1739 const Variable variable) {
1740 return constant <= LinearTerm(variable, 1.0);
1741}
1744 const double constant) {
1745 return UpperBoundedLinearExpression(std::move(expression), constant);
1746}
1748UpperBoundedLinearExpression operator>=(const double constant,
1749 LinearExpression expression) {
1750 return UpperBoundedLinearExpression(std::move(expression), constant);
1751}
1754 const double constant) {
1755 return UpperBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1756}
1758UpperBoundedLinearExpression operator>=(const double constant,
1759 const LinearTerm& term) {
1760 return UpperBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1761}
1764 const double constant) {
1765 return LinearTerm(variable, 1.0) <= constant;
1766}
1768UpperBoundedLinearExpression operator>=(const double constant,
1769 const Variable variable) {
1770 return constant >= LinearTerm(variable, 1.0);
1771}
1774 const double rhs) {
1775 return BoundedLinearExpression(std::move(lhs.expression),
1776 /*lower_bound=*/lhs.lower_bound,
1777 /*upper_bound=*/rhs);
1778}
1779
1780BoundedLinearExpression operator>=(const double lhs,
1781 LowerBoundedLinearExpression rhs) {
1782 return BoundedLinearExpression(std::move(rhs.expression),
1783 /*lower_bound=*/rhs.lower_bound,
1784 /*upper_bound=*/lhs);
1785}
1786
1788 const double rhs) {
1789 return BoundedLinearExpression(std::move(lhs.expression),
1790 /*lower_bound=*/rhs,
1791 /*upper_bound=*/lhs.upper_bound);
1792}
1793
1796 return BoundedLinearExpression(std::move(rhs.expression),
1797 /*lower_bound=*/lhs,
1798 /*upper_bound=*/rhs.upper_bound);
1799}
1800
1802 const LinearExpression& rhs) {
1803 lhs -= rhs;
1805 std::move(lhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1806 /*upper_bound=*/0.0);
1807}
1810 const LinearExpression& rhs) {
1811 lhs -= rhs;
1813 std::move(lhs), /*lower_bound=*/0.0,
1814 /*upper_bound=*/std::numeric_limits<double>::infinity());
1816
1817BoundedLinearExpression operator<=(LinearExpression lhs,
1818 const LinearTerm& rhs) {
1819 lhs -= rhs;
1820 return BoundedLinearExpression(
1821 std::move(lhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1822 /*upper_bound=*/0.0);
1824
1825BoundedLinearExpression operator>=(LinearExpression lhs,
1826 const LinearTerm& rhs) {
1827 lhs -= rhs;
1828 return BoundedLinearExpression(
1829 std::move(lhs), /*lower_bound=*/0.0,
1830 /*upper_bound=*/std::numeric_limits<double>::infinity());
1832
1833BoundedLinearExpression operator<=(const LinearTerm& lhs,
1834 LinearExpression rhs) {
1835 rhs -= lhs;
1836 return BoundedLinearExpression(
1837 std::move(rhs), /*lower_bound=*/0.0,
1838 /*upper_bound=*/std::numeric_limits<double>::infinity());
1840
1841BoundedLinearExpression operator>=(const LinearTerm& lhs,
1842 LinearExpression rhs) {
1843 rhs -= lhs;
1844 return BoundedLinearExpression(
1845 std::move(rhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1846 /*upper_bound=*/0.0);
1848
1849BoundedLinearExpression operator<=(LinearExpression lhs, const Variable rhs) {
1850 return std::move(lhs) <= LinearTerm(rhs, 1.0);
1851}
1852
1853BoundedLinearExpression operator>=(LinearExpression lhs, const Variable rhs) {
1854 return std::move(lhs) >= LinearTerm(rhs, 1.0);
1856
1857BoundedLinearExpression operator<=(const Variable lhs, LinearExpression rhs) {
1858 return LinearTerm(lhs, 1.0) <= std::move(rhs);
1859}
1860
1861BoundedLinearExpression operator>=(const Variable lhs, LinearExpression rhs) {
1862 return LinearTerm(lhs, 1.0) >= std::move(rhs);
1864
1865BoundedLinearExpression operator<=(const LinearTerm& lhs,
1866 const LinearTerm& rhs) {
1868 LinearExpression({lhs, -rhs}, 0.0),
1869 /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1870 /*upper_bound=*/0.0);
1872
1873BoundedLinearExpression operator>=(const LinearTerm& lhs,
1874 const LinearTerm& rhs) {
1876 LinearExpression({lhs, -rhs}, 0.0), /*lower_bound=*/0.0,
1877 /*upper_bound=*/std::numeric_limits<double>::infinity());
1878}
1881 return lhs <= LinearTerm(rhs, 1.0);
1882}
1883
1884BoundedLinearExpression operator>=(const LinearTerm& lhs, const Variable rhs) {
1885 return lhs >= LinearTerm(rhs, 1.0);
1886}
1889 return LinearTerm(lhs, 1.0) <= rhs;
1890}
1891
1892BoundedLinearExpression operator>=(const Variable lhs, const LinearTerm& rhs) {
1893 return LinearTerm(lhs, 1.0) >= rhs;
1895
1896BoundedLinearExpression operator<=(const Variable lhs, const Variable rhs) {
1897 return LinearTerm(lhs, 1.0) <= LinearTerm(rhs, 1.0);
1899
1900BoundedLinearExpression operator>=(const Variable lhs, const Variable rhs) {
1901 return LinearTerm(lhs, 1.0) >= LinearTerm(rhs, 1.0);
1903
1904BoundedLinearExpression operator==(LinearExpression lhs,
1905 const LinearExpression& rhs) {
1906 lhs -= rhs;
1907 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1908 /*upper_bound=*/0.0);
1909}
1913 lhs -= rhs;
1914 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1915 /*upper_bound=*/0.0);
1916}
1917
1919 LinearExpression rhs) {
1920 rhs -= lhs;
1921 return BoundedLinearExpression(std::move(rhs), /*lower_bound=*/0.0,
1922 /*upper_bound=*/0.0);
1923}
1924
1926 return std::move(lhs) == LinearTerm(rhs, 1.0);
1927}
1928
1929BoundedLinearExpression operator==(const Variable lhs, LinearExpression rhs) {
1930 return LinearTerm(lhs, 1.0) == std::move(rhs);
1931}
1934 lhs -= rhs;
1935 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1936 /*upper_bound=*/0.0);
1937}
1938
1940 rhs -= lhs;
1941 return BoundedLinearExpression(std::move(rhs), /*lower_bound=*/0.0,
1942 /*upper_bound=*/0.0);
1944
1945BoundedLinearExpression operator==(const LinearTerm& lhs,
1946 const LinearTerm& rhs) {
1948 /*lower_bound=*/0.0,
1949 /*upper_bound=*/0.0);
1950}
1951
1952BoundedLinearExpression operator==(const LinearTerm& lhs, const Variable rhs) {
1953 return lhs == LinearTerm(rhs, 1.0);
1954}
1955
1956BoundedLinearExpression operator==(const Variable lhs, const LinearTerm& rhs) {
1957 return LinearTerm(lhs, 1.0) == rhs;
1958}
1960BoundedLinearExpression operator==(const LinearTerm& lhs, const double rhs) {
1961 return BoundedLinearExpression(LinearExpression({lhs}, -rhs),
1962 /*lower_bound=*/0.0, /*upper_bound=*/0.0);
1963}
1964
1965BoundedLinearExpression operator==(const double lhs, const LinearTerm& rhs) {
1967 /*lower_bound=*/0.0, /*upper_bound=*/0.0);
1968}
1969
1970BoundedLinearExpression operator==(const Variable lhs, const double rhs) {
1971 return LinearTerm(lhs, 1.0) == rhs;
1972}
1973
1974BoundedLinearExpression operator==(const double lhs, const Variable rhs) {
1975 return lhs == LinearTerm(rhs, 1.0);
1976}
1977
1978
1979// QuadraticTermKey
1981
1983 const QuadraticProductId id)
1984 : ModelStorageItem(storage), variable_ids_(id) {
1985 if (variable_ids_.first > variable_ids_.second) {
1986 // See https://en.cppreference.com/w/cpp/named_req/Swappable for details.
1987 using std::swap;
1988 swap(variable_ids_.first, variable_ids_.second);
1989 }
1990}
1991
1992QuadraticTermKey::QuadraticTermKey(const Variable first_variable,
1993 const Variable second_variable)
1994 : QuadraticTermKey(first_variable.storage(), {first_variable.typed_id(),
1995 second_variable.typed_id()}) {
1996 CHECK_EQ(first_variable.storage(), second_variable.storage())
1997 << internal::kObjectsFromOtherModelStorage;
1999
2000QuadraticProductId QuadraticTermKey::typed_id() const { return variable_ids_; }
2001
2002template <typename H>
2003H AbslHashValue(H h, const QuadraticTermKey& key) {
2004 return H::combine(std::move(h), key.typed_id().first.value(),
2005 key.typed_id().second.value(), key.storage());
2006}
2007
2008std::ostream& operator<<(std::ostream& ostr, const QuadraticTermKey& key) {
2009 ostr << "(" << Variable(key.storage(), key.typed_id().first) << ", "
2010 << Variable(key.storage(), key.typed_id().second) << ")";
2011 return ostr;
2012}
2013
2014bool operator==(const QuadraticTermKey lhs, const QuadraticTermKey rhs) {
2015 return lhs.storage() == rhs.storage() && lhs.typed_id() == rhs.typed_id();
2017
2018bool operator!=(const QuadraticTermKey lhs, const QuadraticTermKey rhs) {
2019 return !(lhs == rhs);
2020}
2021
2023// QuadraticTerm (no arithmetic)
2024////////////////////////////////////////////////////////////////////////////////
2025
2026QuadraticTerm::QuadraticTerm(Variable first_variable, Variable second_variable,
2027 const double coefficient)
2028 : first_variable_(std::move(first_variable)),
2029 second_variable_(std::move(second_variable)),
2030 coefficient_(coefficient) {
2031 CHECK_EQ(first_variable_.storage(), second_variable_.storage())
2033}
2035double QuadraticTerm::coefficient() const { return coefficient_; }
2036Variable QuadraticTerm::first_variable() const { return first_variable_; }
2037Variable QuadraticTerm::second_variable() const { return second_variable_; }
2038
2039QuadraticTermKey QuadraticTerm::GetKey() const {
2040 return QuadraticTermKey(
2041 first_variable_.storage(),
2042 std::make_pair(first_variable_.typed_id(), second_variable_.typed_id()));
2043}
2046// QuadraticExpression (no arithmetic)
2048
2051 static_cast<ModelStorageItemContainer&&>(other)),
2052 quadratic_terms_(std::move(other.quadratic_terms_)),
2053 linear_terms_(std::move(other.linear_terms_)),
2054 offset_(std::exchange(other.offset_, 0.0)) {
2055 other.quadratic_terms_.clear();
2056 other.linear_terms_.clear();
2057#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
2058 ++num_calls_move_constructor_;
2059#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
2060}
2061
2063 QuadraticExpression&& other) noexcept {
2065 static_cast<ModelStorageItemContainer&&>(other));
2066 quadratic_terms_ = std::move(other.quadratic_terms_);
2067 other.quadratic_terms_.clear();
2068 linear_terms_ = std::move(other.linear_terms_);
2069 other.linear_terms_.clear();
2070 offset_ = std::exchange(other.offset_, 0.0);
2071 return *this;
2072}
2073
2075 const std::initializer_list<QuadraticTerm> quadratic_terms,
2076 const std::initializer_list<LinearTerm> linear_terms, const double offset)
2077 : offset_(offset) {
2078#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
2079 ++num_calls_initializer_list_constructor_;
2080#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
2081 for (const LinearTerm& term : linear_terms) {
2082 SetOrCheckStorage(term.variable);
2083 linear_terms_[term.variable] += term.coefficient;
2084 }
2085 for (const QuadraticTerm& term : quadratic_terms) {
2086 const QuadraticTermKey key = term.GetKey();
2087 SetOrCheckStorage(key);
2088 quadratic_terms_[key] += term.coefficient();
2089 }
2090}
2091
2093 : QuadraticExpression({}, {}, offset) {}
2096 : QuadraticExpression({}, {LinearTerm(variable, 1.0)}, 0.0) {}
2097
2098QuadraticExpression::QuadraticExpression(const LinearTerm& term)
2099 : QuadraticExpression({}, {term}, 0.0) {}
2100
2102 : ModelStorageItemContainer(expr.storage()),
2103 linear_terms_(std::move(expr.terms_)),
2104 offset_(expr.offset_) {
2105#ifdef MATH_OPT_USE_EXPRESSION_COUNTERS
2106 ++num_calls_linear_expression_constructor_;
2107#endif // MATH_OPT_USE_EXPRESSION_COUNTERS
2108}
2109
2111 : QuadraticExpression({term}, {}, 0.0) {}
2113double QuadraticExpression::offset() const { return offset_; }
2114
2116 return linear_terms_;
2117}
2120 return quadratic_terms_;
2122
2124// Arithmetic operators (non-member).
2125//
2126// These are NOT required to explicitly CHECK that the underlying model storages
2127// agree between linear_terms_ and quadratic_terms_ unless they are a friend of
2128// QuadraticExpression. As much as possible, defer to the assignment operators
2129// and the initializer list constructor for QuadraticExpression.
2130////////////////////////////////////////////////////////////////////////////////
2131
2132// ----------------------------- Addition (+) ----------------------------------
2134QuadraticExpression operator+(const double lhs, const QuadraticTerm& rhs) {
2135 return QuadraticExpression({rhs}, {}, lhs);
2136}
2137
2138QuadraticExpression operator+(const double lhs, QuadraticExpression rhs) {
2139 rhs += lhs;
2140 return rhs;
2141}
2142
2143QuadraticExpression operator+(const Variable lhs, const QuadraticTerm& rhs) {
2144 return QuadraticExpression({rhs}, {LinearTerm(lhs, 1.0)}, 0.0);
2145}
2146
2148 rhs += LinearTerm(lhs, 1.0);
2149 return rhs;
2150}
2151
2152QuadraticExpression operator+(const LinearTerm& lhs, const QuadraticTerm& rhs) {
2153 return QuadraticExpression({rhs}, {lhs}, 0.0);
2154}
2155
2157 rhs += lhs;
2158 return rhs;
2159}
2162 QuadraticExpression expr(std::move(lhs));
2163 expr += rhs;
2164 return expr;
2166
2167QuadraticExpression operator+(const LinearExpression& lhs,
2168 QuadraticExpression rhs) {
2169 rhs += lhs;
2170 return rhs;
2171}
2172
2173QuadraticExpression operator+(const QuadraticTerm& lhs, const double rhs) {
2174 return QuadraticExpression({lhs}, {}, rhs);
2175}
2176
2177QuadraticExpression operator+(const QuadraticTerm& lhs, const Variable rhs) {
2178 return QuadraticExpression({lhs}, {LinearTerm(rhs, 1.0)}, 0.0);
2179}
2180
2181QuadraticExpression operator+(const QuadraticTerm& lhs, const LinearTerm& rhs) {
2182 return QuadraticExpression({lhs}, {rhs}, 0.0);
2184
2185QuadraticExpression operator+(const QuadraticTerm& lhs, LinearExpression rhs) {
2186 QuadraticExpression expr(std::move(rhs));
2187 expr += lhs;
2188 return expr;
2190
2191QuadraticExpression operator+(const QuadraticTerm& lhs,
2192 const QuadraticTerm& rhs) {
2193 return QuadraticExpression({lhs, rhs}, {}, 0.0);
2194}
2198 rhs += lhs;
2199 return rhs;
2200}
2201
2202QuadraticExpression operator+(QuadraticExpression lhs, const double rhs) {
2203 lhs += rhs;
2204 return lhs;
2205}
2206
2208 lhs += LinearTerm(rhs, 1.0);
2209 return lhs;
2210}
2211
2212QuadraticExpression operator+(QuadraticExpression lhs, const LinearTerm& rhs) {
2213 lhs += rhs;
2214 return lhs;
2215}
2216
2217QuadraticExpression operator+(QuadraticExpression lhs,
2218 const LinearExpression& rhs) {
2219 lhs += rhs;
2220 return lhs;
2221}
2222
2223QuadraticExpression operator+(QuadraticExpression lhs,
2224 const QuadraticTerm& rhs) {
2225 lhs += rhs;
2226 return lhs;
2227}
2228
2230 const QuadraticExpression& rhs) {
2231 lhs += rhs;
2232 return lhs;
2233}
2235// --------------------------- Subtraction (-) ---------------------------------
2236
2237// NOTE: A friend of QuadraticTerm, but does not touch variables
2239 term.coefficient_ *= -1.0;
2240 return term;
2241}
2242
2243// NOTE: A friend of QuadraticExpression, but does not touch variables
2244QuadraticExpression operator-(QuadraticExpression expr) {
2245 expr.offset_ = -expr.offset_;
2246 for (auto& term : expr.linear_terms_) {
2247 term.second = -term.second;
2248 }
2249 for (auto& term : expr.quadratic_terms_) {
2250 term.second = -term.second;
2252 return expr;
2253}
2254
2255QuadraticExpression operator-(const double lhs, const QuadraticTerm& rhs) {
2256 return QuadraticExpression({-rhs}, {}, lhs);
2257}
2258
2259QuadraticExpression operator-(const double lhs, QuadraticExpression rhs) {
2260 auto expr = -std::move(rhs);
2261 expr += lhs;
2262 return expr;
2263}
2264
2265QuadraticExpression operator-(const Variable lhs, const QuadraticTerm& rhs) {
2266 return QuadraticExpression({-rhs}, {LinearTerm(lhs, 1.0)}, 0.0);
2267}
2268
2269QuadraticExpression operator-(const Variable lhs, QuadraticExpression rhs) {
2270 return LinearTerm(lhs, 1.0) - std::move(rhs);
2271}
2272
2273QuadraticExpression operator-(const LinearTerm& lhs, const QuadraticTerm& rhs) {
2274 return QuadraticExpression({-rhs}, {lhs}, 0.0);
2275}
2276
2278 auto expr = -std::move(rhs);
2279 expr += lhs;
2280 return expr;
2282
2283QuadraticExpression operator-(LinearExpression lhs, const QuadraticTerm& rhs) {
2284 QuadraticExpression expr(std::move(lhs));
2285 expr -= rhs;
2286 return expr;
2288
2289QuadraticExpression operator-(const LinearExpression& lhs,
2290 QuadraticExpression rhs) {
2291 auto expr = -std::move(rhs);
2292 expr += lhs;
2293 return expr;
2294}
2296QuadraticExpression operator-(const QuadraticTerm& lhs, const double rhs) {
2297 return QuadraticExpression({lhs}, {}, -rhs);
2298}
2300QuadraticExpression operator-(const QuadraticTerm& lhs, const Variable rhs) {
2301 return QuadraticExpression({lhs}, {LinearTerm(rhs, -1.0)}, 0.0);
2302}
2303
2304QuadraticExpression operator-(const QuadraticTerm& lhs, const LinearTerm& rhs) {
2305 return QuadraticExpression({lhs}, {-rhs}, 0.0);
2306}
2307
2309 QuadraticExpression expr(-std::move(rhs));
2310 expr += lhs;
2311 return expr;
2312}
2313
2314QuadraticExpression operator-(const QuadraticTerm& lhs,
2315 const QuadraticTerm& rhs) {
2316 return QuadraticExpression({lhs, -rhs}, {}, 0.0);
2317}
2321 rhs *= -1.0;
2322 rhs += lhs;
2323 return rhs;
2324}
2325
2327 lhs -= rhs;
2328 return lhs;
2329}
2331// NOTE: Out-of-order for compilation purposes
2333 lhs -= rhs;
2334 return lhs;
2335}
2338 lhs -= LinearTerm(rhs, 1.0);
2339 return lhs;
2340}
2342// NOTE: operator-(QuadraticExpression, const LinearTerm) appears above
2343
2345 const LinearExpression& rhs) {
2346 lhs -= rhs;
2347 return lhs;
2349
2350QuadraticExpression operator-(QuadraticExpression lhs,
2351 const QuadraticTerm& rhs) {
2352 lhs -= rhs;
2353 return lhs;
2355
2356QuadraticExpression operator-(QuadraticExpression lhs,
2357 const QuadraticExpression& rhs) {
2358 lhs -= rhs;
2359 return lhs;
2360}
2361
2362// ---------------------------- Multiplication (*) -----------------------------
2363
2364// NOTE: A friend of QuadraticTerm, but does not touch variables
2365QuadraticTerm operator*(const double lhs, QuadraticTerm rhs) {
2366 rhs.coefficient_ *= lhs;
2367 return rhs;
2368}
2369
2370QuadraticExpression operator*(const double lhs, QuadraticExpression rhs) {
2371 rhs *= lhs;
2372 return rhs;
2373}
2374
2375QuadraticTerm operator*(Variable lhs, Variable rhs) {
2376 return QuadraticTerm(std::move(lhs), std::move(rhs), 1.0);
2377}
2380 return QuadraticTerm(std::move(lhs), std::move(rhs.variable),
2381 rhs.coefficient);
2382}
2383
2384QuadraticExpression operator*(Variable lhs, const LinearExpression& rhs) {
2385 QuadraticExpression expr;
2386 for (const auto& [var, coeff] : rhs.terms()) {
2387 expr += QuadraticTerm(lhs, var, coeff);
2388 }
2389 if (rhs.offset() != 0) {
2390 expr += LinearTerm(std::move(lhs), rhs.offset());
2391 }
2392 return expr;
2393}
2394
2395QuadraticTerm operator*(LinearTerm lhs, Variable rhs) {
2396 return QuadraticTerm(std::move(lhs.variable), std::move(rhs),
2397 lhs.coefficient);
2398}
2399
2400QuadraticTerm operator*(LinearTerm lhs, LinearTerm rhs) {
2401 return QuadraticTerm(std::move(lhs.variable), std::move(rhs.variable),
2402 lhs.coefficient * rhs.coefficient);
2403}
2404
2405QuadraticExpression operator*(LinearTerm lhs, const LinearExpression& rhs) {
2407 for (const auto& [var, coeff] : rhs.terms()) {
2408 expr += QuadraticTerm(lhs.variable, var, lhs.coefficient * coeff);
2409 }
2410 if (rhs.offset() != 0) {
2411 expr += LinearTerm(std::move(lhs.variable), lhs.coefficient * rhs.offset());
2412 }
2413 return expr;
2414}
2415
2418 for (const auto& [var, coeff] : lhs.terms()) {
2419 expr += QuadraticTerm(var, rhs, coeff);
2420 }
2421 if (lhs.offset() != 0) {
2422 expr += LinearTerm(std::move(rhs), lhs.offset());
2423 }
2424 return expr;
2425}
2426
2429 for (const auto& [var, coeff] : lhs.terms()) {
2430 expr += QuadraticTerm(var, rhs.variable, coeff * rhs.coefficient);
2431 }
2432 if (lhs.offset() != 0) {
2433 expr += LinearTerm(std::move(rhs.variable), lhs.offset() * rhs.coefficient);
2434 }
2435 return expr;
2436}
2437
2439 const LinearExpression& rhs) {
2440 QuadraticExpression expr = lhs.offset() * rhs.offset();
2441 if (rhs.offset() != 0) {
2442 for (const auto& [var, coeff] : lhs.terms()) {
2443 expr += LinearTerm(var, coeff * rhs.offset());
2444 }
2445 }
2446 if (lhs.offset() != 0) {
2447 for (const auto& [var, coeff] : rhs.terms()) {
2448 expr += LinearTerm(var, lhs.offset() * coeff);
2450 }
2451 for (const auto& [lhs_var, lhs_coeff] : lhs.terms()) {
2452 for (const auto& [rhs_var, rhs_coeff] : rhs.terms()) {
2453 expr += QuadraticTerm(lhs_var, rhs_var, lhs_coeff * rhs_coeff);
2454 }
2455 }
2456 return expr;
2457}
2458
2459// NOTE: A friend of QuadraticTerm, but does not touch variables
2460QuadraticTerm operator*(QuadraticTerm lhs, const double rhs) {
2461 lhs.coefficient_ *= rhs;
2462 return lhs;
2463}
2464
2465QuadraticExpression operator*(QuadraticExpression lhs, const double rhs) {
2466 lhs *= rhs;
2467 return lhs;
2468}
2469
2470// ------------------------------- Division (/) --------------------------------
2471
2472// NOTE: A friend of QuadraticTerm, but does not touch variables
2473QuadraticTerm operator/(QuadraticTerm lhs, const double rhs) {
2474 lhs.coefficient_ /= rhs;
2475 return lhs;
2476}
2477
2478QuadraticExpression operator/(QuadraticExpression lhs, const double rhs) {
2479 lhs /= rhs;
2480 return lhs;
2481}
2484// In-place arithmetic operators.
2485//
2486// These must guarantee that the underlying model storages for linear_terms_ and
2487// quadratic_terms_ agree upon exit of the function, using CheckModelsAgree(),
2488// the list initializer constructor for QuadraticExpression, or similar logic.
2490
2492 offset_ += value;
2493 // NOTE: Not touching terms, no need to check models
2494 return *this;
2499 linear_terms_[variable] += 1;
2500 return *this;
2501}
2502
2503QuadraticExpression& QuadraticExpression::operator+=(const LinearTerm& term) {
2504 SetOrCheckStorage(term.variable);
2505 linear_terms_[term.variable] += term.coefficient;
2506 return *this;
2507}
2508
2509QuadraticExpression& QuadraticExpression::operator+=(
2510 const LinearExpression& expr) {
2511 offset_ += expr.offset();
2512 // See comment in LinearExpression::operator+=.
2513 if (!expr.terms().empty()) {
2514 SetOrCheckStorage(expr);
2515 for (const auto& [v, coeff] : expr.terms()) {
2516 linear_terms_[v] += coeff;
2517 }
2518 }
2519 return *this;
2520}
2526 quadratic_terms_[key] += term.coefficient();
2527 return *this;
2528}
2529
2531 const QuadraticExpression& expr) {
2532 offset_ += expr.offset();
2533 // See comment in LinearExpression::operator+=.
2534 if (!expr.linear_terms().empty() || !expr.quadratic_terms().empty()) {
2535 SetOrCheckStorage(expr);
2536 for (const auto& [v, coeff] : expr.linear_terms()) {
2537 linear_terms_[v] += coeff;
2538 }
2539 for (const auto& [k, coeff] : expr.quadratic_terms()) {
2540 quadratic_terms_[k] += coeff;
2541 }
2542 }
2543 return *this;
2544}
2545
2547 offset_ -= value;
2548 // NOTE: Not touching terms, no need to check models
2549 return *this;
2550}
2551
2553 SetOrCheckStorage(variable);
2554 linear_terms_[variable] -= 1;
2555 return *this;
2556}
2557
2560 linear_terms_[term.variable] -= term.coefficient;
2561 return *this;
2562}
2563
2564QuadraticExpression& QuadraticExpression::operator-=(
2565 const LinearExpression& expr) {
2566 offset_ -= expr.offset();
2567 // See comment in LinearExpression::operator+=.
2568 if (!expr.terms().empty()) {
2569 SetOrCheckStorage(expr);
2570 for (const auto& [v, coeff] : expr.terms()) {
2571 linear_terms_[v] -= coeff;
2572 }
2573 }
2574 return *this;
2575}
2581 quadratic_terms_[key] -= term.coefficient();
2582 return *this;
2583}
2584
2586 const QuadraticExpression& expr) {
2587 offset_ -= expr.offset();
2588 // See comment in LinearExpression::operator+=.
2589 if (!expr.linear_terms().empty() || !expr.quadratic_terms().empty()) {
2590 SetOrCheckStorage(expr);
2591 for (const auto& [v, coeff] : expr.linear_terms()) {
2592 linear_terms_[v] -= coeff;
2593 }
2594 for (const auto& [k, coeff] : expr.quadratic_terms()) {
2595 quadratic_terms_[k] -= coeff;
2596 }
2597 }
2598 return *this;
2599}
2600
2602 coefficient_ *= value;
2603 // NOTE: Not touching variables in term, just modifying coefficient, so no
2604 // need to check that models agree.
2605 return *this;
2606}
2607
2609 offset_ *= value;
2610 for (auto& term : linear_terms_) {
2611 term.second *= value;
2612 }
2613 for (auto& term : quadratic_terms_) {
2614 term.second *= value;
2615 }
2616 // NOTE: Not adding/removing/altering variables in expression, just modifying
2617 // coefficients, so no need to check that models agree.
2618 return *this;
2619}
2620
2621QuadraticTerm& QuadraticTerm::operator/=(const double value) {
2622 coefficient_ /= value;
2623 // NOTE: Not touching variables in term, just modifying coefficient, so no
2624 // need to check that models agree.
2625 return *this;
2626}
2627
2629 offset_ /= value;
2630 for (auto& term : linear_terms_) {
2631 term.second /= value;
2633 for (auto& term : quadratic_terms_) {
2634 term.second /= value;
2635 }
2636 // NOTE: Not adding/removing/altering variables in expression, just modifying
2637 // coefficients, so no need to check that models agree.
2638 return *this;
2639}
2640
2641template <typename Iterable>
2642void QuadraticExpression::AddSum(const Iterable& items) {
2643 for (const auto& item : items) {
2644 *this += item;
2646}
2647
2648template <typename Iterable>
2649QuadraticExpression QuadraticExpression::Sum(const Iterable& items) {
2650 QuadraticExpression result;
2651 result.AddSum(items);
2652 return result;
2653}
2654
2655template <typename LeftIterable, typename RightIterable>
2656void QuadraticExpression::AddInnerProduct(const LeftIterable& left,
2657 const RightIterable& right) {
2658 internal::AddInnerProduct(left, right, *this);
2659}
2660
2661template <typename LeftIterable, typename RightIterable>
2662QuadraticExpression QuadraticExpression::InnerProduct(
2663 const LeftIterable& left, const RightIterable& right) {
2664 QuadraticExpression result;
2665 result.AddInnerProduct(left, right);
2666 return result;
2667}
2668
2670// LowerBoundedQuadraticExpression
2671// UpperBoundedQuadraticExpression
2672// BoundedQuadraticExpression
2673////////////////////////////////////////////////////////////////////////////////
2674
2676 QuadraticExpression expression, const double lower_bound)
2677 : expression(std::move(expression)), lower_bound(lower_bound) {}
2679 LowerBoundedLinearExpression lb_expression)
2680 : expression(std::move(lb_expression.expression)),
2681 lower_bound(lb_expression.lower_bound) {}
2682
2684 QuadraticExpression expression, const double upper_bound)
2685 : expression(std::move(expression)), upper_bound(upper_bound) {}
2687 UpperBoundedLinearExpression ub_expression)
2688 : expression(std::move(ub_expression.expression)),
2689 upper_bound(ub_expression.upper_bound) {}
2690
2692 QuadraticExpression expression, const double lower_bound,
2693 const double upper_bound)
2694 : expression(std::move(expression)),
2695 lower_bound(lower_bound),
2696 upper_bound(upper_bound) {}
2698 internal::VariablesEquality var_equality)
2699 : lower_bound(0), upper_bound(0) {
2700 expression += var_equality.lhs;
2705 : expression(std::move(lb_expression.expression)),
2706 lower_bound(lb_expression.lower_bound),
2707 upper_bound(std::numeric_limits<double>::infinity()) {}
2710 : expression(std::move(ub_expression.expression)),
2711 lower_bound(-std::numeric_limits<double>::infinity()),
2712 upper_bound(ub_expression.upper_bound) {}
2714 BoundedLinearExpression bounded_expression)
2715 : expression(std::move(bounded_expression.expression)),
2716 lower_bound(bounded_expression.lower_bound),
2717 upper_bound(bounded_expression.upper_bound) {}
2719 LowerBoundedQuadraticExpression lb_expression)
2720 : expression(std::move(lb_expression.expression)),
2721 lower_bound(lb_expression.lower_bound),
2722 upper_bound(std::numeric_limits<double>::infinity()) {}
2724 UpperBoundedQuadraticExpression ub_expression)
2725 : expression(std::move(ub_expression.expression)),
2726 lower_bound(-std::numeric_limits<double>::infinity()),
2727 upper_bound(ub_expression.upper_bound) {}
2728
2734 return upper_bound - expression.offset();
2735}
2736
2738 const double rhs) {
2739 return LowerBoundedQuadraticExpression(std::move(lhs), rhs);
2740}
2742 const double rhs) {
2743 return LowerBoundedQuadraticExpression(lhs, rhs);
2746 QuadraticExpression rhs) {
2747 return LowerBoundedQuadraticExpression(std::move(rhs), lhs);
2748}
2750 const QuadraticTerm rhs) {
2751 return LowerBoundedQuadraticExpression(rhs, lhs);
2752}
2753
2756 return UpperBoundedQuadraticExpression(std::move(rhs), lhs);
2757}
2759 const QuadraticTerm rhs) {
2760 return UpperBoundedQuadraticExpression(rhs, lhs);
2761}
2763 const double rhs) {
2764 return UpperBoundedQuadraticExpression(std::move(lhs), rhs);
2765}
2766UpperBoundedQuadraticExpression operator<=(const QuadraticTerm lhs,
2767 const double rhs) {
2768 return UpperBoundedQuadraticExpression(lhs, rhs);
2769}
2770
2772 const double rhs) {
2773 return BoundedQuadraticExpression(std::move(lhs.expression), rhs,
2774 lhs.upper_bound);
2776BoundedQuadraticExpression operator>=(const double lhs,
2777 LowerBoundedQuadraticExpression rhs) {
2778 return BoundedQuadraticExpression(std::move(rhs.expression), rhs.lower_bound,
2779 lhs);
2781BoundedQuadraticExpression operator<=(LowerBoundedQuadraticExpression lhs,
2782 const double rhs) {
2783 return BoundedQuadraticExpression(std::move(lhs.expression), lhs.lower_bound,
2784 rhs);
2785}
2786BoundedQuadraticExpression operator<=(const double lhs,
2787 UpperBoundedQuadraticExpression rhs) {
2788 return BoundedQuadraticExpression(std::move(rhs.expression), lhs,
2789 rhs.upper_bound);
2790}
2791
2793 const QuadraticExpression& rhs) {
2794 lhs -= rhs;
2795 return BoundedQuadraticExpression(std::move(lhs), 0,
2796 std::numeric_limits<double>::infinity());
2798BoundedQuadraticExpression operator>=(QuadraticExpression lhs,
2799 const QuadraticTerm rhs) {
2800 lhs -= rhs;
2801 return BoundedQuadraticExpression(std::move(lhs), 0,
2802 std::numeric_limits<double>::infinity());
2803}
2804BoundedQuadraticExpression operator>=(QuadraticExpression lhs,
2805 const LinearExpression& rhs) {
2806 lhs -= rhs;
2807 return BoundedQuadraticExpression(std::move(lhs), 0,
2808 std::numeric_limits<double>::infinity());
2809}
2810BoundedQuadraticExpression operator>=(QuadraticExpression lhs,
2811 const LinearTerm rhs) {
2812 lhs -= rhs;
2813 return BoundedQuadraticExpression(std::move(lhs), 0,
2814 std::numeric_limits<double>::infinity());
2815}
2816BoundedQuadraticExpression operator>=(QuadraticExpression lhs,
2817 const Variable rhs) {
2818 lhs -= rhs;
2819 return BoundedQuadraticExpression(std::move(lhs), 0,
2820 std::numeric_limits<double>::infinity());
2821}
2822BoundedQuadraticExpression operator<=(QuadraticExpression lhs,
2823 const QuadraticExpression& rhs) {
2824 lhs -= rhs;
2826 std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2827}
2828BoundedQuadraticExpression operator<=(QuadraticExpression lhs,
2829 const QuadraticTerm rhs) {
2830 lhs -= rhs;
2832 std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2833}
2834BoundedQuadraticExpression operator<=(QuadraticExpression lhs,
2835 const LinearExpression& rhs) {
2836 lhs -= rhs;
2838 std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2839}
2840BoundedQuadraticExpression operator<=(QuadraticExpression lhs,
2841 const LinearTerm rhs) {
2842 lhs -= rhs;
2844 std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2845}
2846BoundedQuadraticExpression operator<=(QuadraticExpression lhs,
2847 const Variable rhs) {
2848 lhs -= rhs;
2850 std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2851}
2852BoundedQuadraticExpression operator==(QuadraticExpression lhs,
2853 const QuadraticExpression& rhs) {
2854 lhs -= rhs;
2855 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2856}
2857BoundedQuadraticExpression operator==(QuadraticExpression lhs,
2858 const QuadraticTerm rhs) {
2859 lhs -= rhs;
2860 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2861}
2862BoundedQuadraticExpression operator==(QuadraticExpression lhs,
2863 const LinearExpression& rhs) {
2864 lhs -= rhs;
2865 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2867BoundedQuadraticExpression operator==(QuadraticExpression lhs,
2868 const LinearTerm rhs) {
2869 lhs -= rhs;
2870 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2871}
2873 const Variable rhs) {
2874 lhs -= rhs;
2875 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2876}
2877BoundedQuadraticExpression operator==(QuadraticExpression lhs,
2878 const double rhs) {
2879 lhs -= rhs;
2880 return BoundedQuadraticExpression(std::move(lhs), 0, 0);
2881}
2882
2884 QuadraticExpression rhs) {
2885 rhs -= lhs;
2887 std::move(rhs), -std::numeric_limits<double>::infinity(), 0);
2889BoundedQuadraticExpression operator>=(const QuadraticTerm lhs,
2890 const QuadraticTerm rhs) {
2891 return BoundedQuadraticExpression(
2892 rhs - lhs, -std::numeric_limits<double>::infinity(), 0);
2894BoundedQuadraticExpression operator>=(const QuadraticTerm lhs,
2895 LinearExpression rhs) {
2896 return BoundedQuadraticExpression(
2897 std::move(rhs) - lhs, -std::numeric_limits<double>::infinity(), 0);
2899BoundedQuadraticExpression operator>=(const QuadraticTerm lhs,
2900 const LinearTerm rhs) {
2901 return BoundedQuadraticExpression(
2902 rhs - lhs, -std::numeric_limits<double>::infinity(), 0);
2904BoundedQuadraticExpression operator>=(const QuadraticTerm lhs,
2905 const Variable rhs) {
2906 return BoundedQuadraticExpression(
2907 rhs - lhs, -std::numeric_limits<double>::infinity(), 0);
2908}
2910 QuadraticExpression rhs) {
2911 rhs -= lhs;
2912 return BoundedQuadraticExpression(std::move(rhs), 0,
2913 std::numeric_limits<double>::infinity());
2914}
2916 const QuadraticTerm rhs) {
2917 return BoundedQuadraticExpression(rhs - lhs, 0,
2918 std::numeric_limits<double>::infinity());
2919}
2921 LinearExpression rhs) {
2922 return BoundedQuadraticExpression(std::move(rhs) - lhs, 0,
2923 std::numeric_limits<double>::infinity());
2924}
2926 const LinearTerm rhs) {
2927 return BoundedQuadraticExpression(rhs - lhs, 0,
2928 std::numeric_limits<double>::infinity());
2929}
2931 const Variable rhs) {
2932 return BoundedQuadraticExpression(rhs - lhs, 0,
2933 std::numeric_limits<double>::infinity());
2934}
2936 QuadraticExpression rhs) {
2937 rhs -= lhs;
2938 return BoundedQuadraticExpression(std::move(rhs), 0, 0);
2939}
2940BoundedQuadraticExpression operator==(const QuadraticTerm lhs,
2941 const QuadraticTerm rhs) {
2942 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
2943}
2944BoundedQuadraticExpression operator==(const QuadraticTerm lhs,
2945 LinearExpression rhs) {
2946 return BoundedQuadraticExpression(std::move(rhs) - lhs, 0, 0);
2947}
2948BoundedQuadraticExpression operator==(const QuadraticTerm lhs,
2949 const LinearTerm rhs) {
2950 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
2952BoundedQuadraticExpression operator==(const QuadraticTerm lhs,
2953 const Variable rhs) {
2954 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
2955}
2957 const double rhs) {
2958 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
2959}
2960
2962 QuadraticExpression rhs) {
2963 rhs -= lhs;
2965 std::move(rhs), -std::numeric_limits<double>::infinity(), 0);
2967BoundedQuadraticExpression operator>=(LinearExpression lhs,
2968 const QuadraticTerm rhs) {
2969 return BoundedQuadraticExpression(
2970 rhs - std::move(lhs), -std::numeric_limits<double>::infinity(), 0);
2971}
2972BoundedQuadraticExpression operator<=(const LinearExpression& lhs,
2973 QuadraticExpression rhs) {
2974 rhs -= lhs;
2975 return BoundedQuadraticExpression(std::move(rhs), 0,
2976 std::numeric_limits<double>::infinity());
2977}
2979 const QuadraticTerm rhs) {
2980 return BoundedQuadraticExpression(rhs - std::move(lhs), 0,
2981 std::numeric_limits<double>::infinity());
2983BoundedQuadraticExpression operator==(const LinearExpression& lhs,
2984 QuadraticExpression rhs) {
2985 rhs -= lhs;
2986 return BoundedQuadraticExpression(std::move(rhs), 0, 0);
2988BoundedQuadraticExpression operator==(LinearExpression lhs,
2989 const QuadraticTerm rhs) {
2990 return BoundedQuadraticExpression(rhs - std::move(lhs), 0, 0);
2991}
2992// LinearTerm --
2994 QuadraticExpression rhs) {
2995 rhs -= lhs;
2997 std::move(rhs), -std::numeric_limits<double>::infinity(), 0);
2999BoundedQuadraticExpression operator>=(const LinearTerm lhs,
3000 const QuadraticTerm rhs) {
3001 return BoundedQuadraticExpression(
3002 rhs - lhs, -std::numeric_limits<double>::infinity(), 0);
3003}
3005 QuadraticExpression rhs) {
3006 rhs -= lhs;
3007 return BoundedQuadraticExpression(std::move(rhs), 0,
3008 std::numeric_limits<double>::infinity());
3010BoundedQuadraticExpression operator<=(const LinearTerm lhs,
3011 const QuadraticTerm rhs) {
3012 return BoundedQuadraticExpression(rhs - lhs, 0,
3013 std::numeric_limits<double>::infinity());
3015BoundedQuadraticExpression operator==(const LinearTerm lhs,
3016 QuadraticExpression rhs) {
3017 rhs -= lhs;
3018 return BoundedQuadraticExpression(std::move(rhs), 0, 0);
3020BoundedQuadraticExpression operator==(const LinearTerm lhs,
3021 const QuadraticTerm rhs) {
3022 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
3023}
3024// Variable --
3026 QuadraticExpression rhs) {
3027 rhs -= lhs;
3029 std::move(rhs), -std::numeric_limits<double>::infinity(), 0);
3031BoundedQuadraticExpression operator>=(const Variable lhs,
3032 const QuadraticTerm rhs) {
3033 return BoundedQuadraticExpression(
3034 rhs - lhs, -std::numeric_limits<double>::infinity(), 0);
3035}
3037 QuadraticExpression rhs) {
3038 rhs -= lhs;
3039 return BoundedQuadraticExpression(std::move(rhs), 0,
3040 std::numeric_limits<double>::infinity());
3042BoundedQuadraticExpression operator<=(const Variable lhs,
3043 const QuadraticTerm rhs) {
3044 return BoundedQuadraticExpression(rhs - lhs, 0,
3045 std::numeric_limits<double>::infinity());
3047BoundedQuadraticExpression operator==(const Variable lhs,
3048 QuadraticExpression rhs) {
3049 rhs -= lhs;
3050 return BoundedQuadraticExpression(std::move(rhs), 0, 0);
3052BoundedQuadraticExpression operator==(const Variable lhs,
3053 const QuadraticTerm rhs) {
3054 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
3055}
3056
3057// Double --
3058BoundedQuadraticExpression operator==(const double lhs,
3059 QuadraticExpression rhs) {
3060 rhs -= lhs;
3061 return BoundedQuadraticExpression(std::move(rhs), 0, 0);
3063BoundedQuadraticExpression operator==(const double lhs,
3064 const QuadraticTerm rhs) {
3065 return BoundedQuadraticExpression(rhs - lhs, 0, 0);
3066}
3067
3068} // namespace math_opt
3069} // namespace operations_research
3070
3071#endif // OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
double EvaluateWithDefaultZero(const VariableMap< double > &variable_values) const
static LinearExpression InnerProduct(const LeftIterable &left, const RightIterable &right)
friend LinearExpression operator-(LinearExpression expr)
double Evaluate(const VariableMap< double > &variable_values) const
const VariableMap< double > & terms() const
Returns the terms in this expression.
LinearExpression & operator-=(const LinearExpression &other)
friend std::ostream & operator<<(std::ostream &ostr, const LinearExpression &expression)
LinearExpression & operator+=(const LinearExpression &other)
void AddInnerProduct(const LeftIterable &left, const RightIterable &right)
LinearExpression & operator=(const LinearExpression &other)=default
LinearExpression(const LinearExpression &other)=default
static LinearExpression Sum(const Iterable &items)
ModelStorageElement(ModelStorageCPtr storage, IdType id)
ModelStorageItemContainer(const NullableModelStorageCPtr storage=nullptr)
ModelStorageItemContainer & operator=(const ModelStorageItemContainer &other)=default
void AddInnerProduct(const LeftIterable &left, const RightIterable &right)
const QuadraticTermMap< double > & quadratic_terms() const
static RightIterable QuadraticExpression InnerProduct(const LeftIterable &left, const RightIterable &right)
friend std::ostream & operator<<(std::ostream &ostr, const QuadraticExpression &expr)
double EvaluateWithDefaultZero(const VariableMap< double > &variable_values) const
QuadraticExpression(const QuadraticExpression &other)=default
static QuadraticExpression Sum(const Iterable &items)
double Evaluate(const VariableMap< double > &variable_values) const
friend QuadraticExpression operator-(QuadraticExpression expr)
QuadraticExpression & operator=(const QuadraticExpression &other)=default
Variable first() const
Returns the Variable with the smallest id.
QuadraticTermKey(ModelStorageCPtr storage, QuadraticProductId id)
Variable second() const
Returns the Variable the largest id.
friend H AbslHashValue(H h, const QuadraticTermKey &key)
friend QuadraticTerm operator*(double lhs, QuadraticTerm rhs)
-------------------------— Multiplication (*) --------------------------—
friend QuadraticTerm operator-(QuadraticTerm term)
------------------------— Subtraction (-) ------------------------------—
QuadraticTermKey GetKey() const
This is useful for working with IdMaps.
friend QuadraticTerm operator/(QuadraticTerm lhs, double rhs)
----------------------------— Division (/) -----------------------------—
ModelStorageElement(ModelStorageCPtr storage, IdType id)
constexpr absl::string_view kObjectsFromOtherModelStorage
Definition key_types.h:157
void AddInnerProduct(const LeftIterable &left, const RightIterable &right, Expression &expr)
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
absl::flat_hash_map< Variable, V > VariableMap
absl::Nonnull< const ModelStorage * > ModelStorageCPtr
LinearExpression Sum(const Iterable &items)
LinearExpression operator+(Variable lhs, double rhs)
absl::flat_hash_map< QuadraticTermKey, V > QuadraticTermMap
LinearTerm operator*(double coefficient, LinearTerm term)
bool operator==(const SecondOrderConeConstraint &lhs, const SecondOrderConeConstraint &rhs)
bool operator!=(const SecondOrderConeConstraint &lhs, const SecondOrderConeConstraint &rhs)
std::ostream & operator<<(std::ostream &ostr, const SecondOrderConeConstraint &constraint)
LowerBoundedLinearExpression operator>=(LinearExpression expression, double constant)
RightIterable LinearExpression InnerProduct(const LeftIterable &left, const RightIterable &right)
LowerBoundedLinearExpression operator<=(double constant, LinearExpression expression)
LinearTerm operator/(LinearTerm term, double coefficient)
LinearExpression operator-(LinearExpression expr)
std::pair< VariableId, VariableId > QuadraticProductId
Id type used for quadratic terms, i.e. products of two variables.
In SWIG mode, we don't want anything besides these top-level includes.
LinearRange operator==(const LinearExpr &lhs, const LinearExpr &rhs)
H AbslHashValue(H h, const StrongIndex< StrongIndexName > &i)
– ABSL HASHING SUPPORT --------------------------------------------------—
ClosedInterval::Iterator end(ClosedInterval interval)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
ClosedInterval::Iterator begin(ClosedInterval interval)
STL namespace.
A LinearExpression with upper and lower bounds.
BoundedLinearExpression(LinearExpression expression, double lower_bound, double upper_bound)
A QuadraticExpression with upper and lower bounds.
BoundedQuadraticExpression(QuadraticExpression expression, double lower_bound, double upper_bound)
A term in an sum of variables multiplied by coefficients.
LinearTerm(Variable variable, double coefficient)
LowerBoundedLinearExpression(LinearExpression expression, double lower_bound)
LowerBoundedQuadraticExpression(QuadraticExpression expression, double lower_bound)
UpperBoundedLinearExpression(LinearExpression expression, double upper_bound)
UpperBoundedQuadraticExpression(QuadraticExpression expression, double upper_bound)