1 // Copyright 2010-2021 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 // An object oriented wrapper for variables in IndexedModel with support for
15 // arithmetic operations to build linear expressions and express linear
16 // constraints.
17 //
18 // Types are:
19 // - Variable: a reference to a variable of an IndexedModel.
20 //
21 // - LinearExpression: a weighted sum of variables with an optional offset;
22 // something like `3*x + 2*y + 5`.
23 //
24 // - LinearTerm: a term of a linear expression, something like `2*x`. It is
25 // used as an intermediate in the arithmetic operations that builds linear
26 // expressions.
27 //
28 // - (Lower|Upper)BoundedLinearExpression: two classes representing the result
29 // of the comparison of a LinearExpression with a constant. For example `3*x
30 // + 2*y + 5 >= 3`.
31 //
32 // - BoundedLinearExpression: the result of the comparison of a linear
33 // expression with two bounds, an upper bound and a lower bound. For example
34 // `2 <= 3*x + 2*y + 5 <= 3`; or `4 >= 3*x + 2*y + 5 >= 1`.
35 //
36 // - VariablesEquality: the result of comparing two Variable instances with
37 // the == operator. For example `a == b`. This intermediate class support
38 // implicit conversion to both bool and BoundedLinearExpression types. This
39 // enables using variables as key of maps (using the conversion to bool)
40 // without preventing adding constraints of variable equality.
41 //
42 // The basic arithmetic operators are overloaded for those types so that we can
43 // write math expressions with variables to build linear expressions. The >=, <=
44 // and == comparison operators are overloaded to produce BoundedLinearExpression
45 // that can be used to build constraints.
46 //
47 // For example we can have:
48 // const Variable x = ...;
49 // const Variable y = ...;
50 // const LinearExpression expr = 2 * x + 3 * y - 2;
51 // const BoundedLinearExpression bounded_expr = 1 <= 2 * x + 3 * y - 2 <= 10;
52 //
53 // To making working with containers of doubles/Variables/LinearExpressions
54 // easier, the template methods Sum() and InnerProduct() are provided, e.g.
55 // const std::vector<int> ints = ...;
56 // const std::vector<double> doubles = ...;
57 // const std::vector<Variable> vars = ...;
58 // const std::vector<LinearTerm> terms = ...;
59 // const std::vector<LinearExpression> exprs = ...;
60 // const LinearExpression s1 = Sum(ints);
61 // const LinearExpression s2 = Sum(doubles);
62 // const LinearExpression s3 = Sum(vars);
63 // const LinearExpression s4 = Sum(terms);
64 // const LinearExpression s5 = Sum(exprs);
65 // const LinearExpression p1 = InnerProduct(ints, vars);
66 // const LinearExpression p2 = InnerProduct(terms, doubles);
67 // const LinearExpression p3 = InnerProduct(doubles, exprs);
68 // These methods work on any iterable type (defining begin() and end()). For
69 // InnerProduct, the inputs must be of equal size, and a compile time error will
70 // be generated unless at least one input is a container of a type implicitly
71 // convertible to double.
72 //
73 // Pre C++20, avoid the use of std::accumulate and std::inner_product with
74 // LinearExpression, they cause a quadratic blowup in running time.
75 //
76 // While there is some complexity in the source, users typically should not need
77 // to look at types other than Variable and LinearExpression too closely. Their
78 // code usually will only refer to those types.
79 #ifndef OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
80 #define OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
81
82 #include <stdint.h>
83
84 #include <initializer_list>
85 #include <iterator>
86 #include <limits>
87 #include <string>
88 #include <utility>
89
90 #include "ortools/base/logging.h"
91 #include "absl/container/flat_hash_map.h"
92 #include "ortools/base/int_type.h"
93 #include "ortools/math_opt/core/indexed_model.h"
94 #include "ortools/math_opt/cpp/id_map.h" // IWYU pragma: export
95
96 namespace operations_research {
97 namespace math_opt {
98
99 // A value type that references a variable from IndexedModel. Usually this type
100 // is passed by copy.
101 class Variable {
102 public:
103 // The typed integer used for ids.
104 using IdType = VariableId;
105
106 // Usually users will obtain variables using MathOpt::AddVariable(). There
107 // should be little for users to build this object from an IndexedModel.
108 inline Variable(IndexedModel* model, VariableId id);
109
110 // Each call to AddVariable will produce Variables id() increasing by one,
111 // starting at zero. Deleted ids are NOT reused. Thus, if no variables are
112 // deleted, the ids in the model will be consecutive.
113 inline int64_t id() const;
114
115 inline VariableId typed_id() const;
116 inline IndexedModel* model() const;
117
118 inline double lower_bound() const;
119 inline double upper_bound() const;
120 inline bool is_integer() const;
121 inline const std::string& name() const;
122
123 inline void set_lower_bound(double lower_bound) const;
124 inline void set_upper_bound(double upper_bound) const;
125 inline void set_is_integer(bool is_integer) const;
126 inline void set_integer() const;
127 inline void set_continuous() const;
128
129 template <typename H>
130 friend H AbslHashValue(H h, const Variable& variable);
131 friend std::ostream& operator<<(std::ostream& ostr, const Variable& variable);
132
133 private:
134 IndexedModel* model_;
135 VariableId id_;
136 };
137
138 // Implements the API of std::unordered_map<Variable, V>, but forbids Variables
139 // from different models in the same map.
140 template <typename V>
141 using VariableMap = IdMap<Variable, V>;
142
143 inline std::ostream& operator<<(std::ostream& ostr, const Variable& variable);
144
145 // A term in an sum of variables multiplied by coefficients.
146 struct LinearTerm {
147 // Usually this constructor is never called explicitly by users. Instead it
148 // will be implicitly used when writing linear expression. For example `x +
149 // 2*y` will automatically use this constructor to build a LinearTerm from `x`
150 // and the overload of the operator* will also automatically create the one
151 // from `2*y`.
152 inline LinearTerm(Variable variable, double coefficient);
153 inline LinearTerm operator-() const;
154 inline LinearTerm& operator*=(double d);
155 inline LinearTerm& operator/=(double d);
156 Variable variable;
157 double coefficient;
158 };
159
160 inline LinearTerm operator*(double coefficient, LinearTerm term);
161 inline LinearTerm operator*(LinearTerm term, double coefficient);
162 inline LinearTerm operator*(double coefficient, Variable variable);
163 inline LinearTerm operator*(Variable variable, double coefficient);
164 inline LinearTerm operator/(LinearTerm term, double coefficient);
165 inline LinearTerm operator/(Variable variable, double coefficient);
166
167 // This class represents a sum of variables multiplied by coefficient and an
168 // optional offset constant. For example: "3*x + 2*y + 5".
169 //
170 // All operations, including constructor, will raise an assertion if the
171 // operands involve variables from different MathOpt objects.
172 //
173 // Contrary to Variable type, expressions owns the linear expression their
174 // represent. Hence they are usually passed by reference to prevent unnecessary
175 // copies.
176 //
177 // TODO(b/169415098): add a function to remove zero terms.
178 // TODO(b/169415834): study if exact zeros should be automatically removed.
179 // TODO(b/169415103): add tests that some expressions don't compile.
180 class LinearExpression {
181 public:
182 // For unit testing purpose, we define optional counters. We have to
183 // explicitly define default constructors in that case.
184 #ifndef USE_LINEAR_EXPRESSION_COUNTERS
185 LinearExpression() = default;
186 #else // USE_LINEAR_EXPRESSION_COUNTERS
187 LinearExpression();
188 LinearExpression(const LinearExpression& other);
189 LinearExpression(LinearExpression&& other);
190 LinearExpression& operator=(const LinearExpression& other);
191 #endif // USE_LINEAR_EXPRESSION_COUNTERS
192 // Usually users should use the overloads of operators to build linear
193 // expressions. For example, assuming `x` and `y` are Variable, then `x + 2*y
194 // + 5` will build a LinearExpression automatically.
195 inline LinearExpression(std::initializer_list<LinearTerm> terms,
196 double offset);
197 inline LinearExpression(double offset); // NOLINT
198 inline LinearExpression(Variable variable); // NOLINT
199 inline LinearExpression(const LinearTerm& term); // NOLINT
200
201 inline LinearExpression& operator+=(const LinearExpression& other);
202 inline LinearExpression& operator+=(const LinearTerm& term);
203 inline LinearExpression& operator+=(Variable variable);
204 inline LinearExpression& operator+=(double value);
205 inline LinearExpression& operator-=(const LinearExpression& other);
206 inline LinearExpression& operator-=(const LinearTerm& term);
207 inline LinearExpression& operator-=(Variable variable);
208 inline LinearExpression& operator-=(double value);
209 inline LinearExpression& operator*=(double value);
210 inline LinearExpression& operator/=(double value);
211
212 // Adds each element of items to this.
213 //
214 // Specifically, letting
215 // (i_1, i_2, ..., i_n) = items
216 // adds
217 // i_1 + i_2 + ... + i_n
218 // to this.
219 //
220 // Example:
221 // Variable a = ...;
222 // Variable b = ...;
223 // const std::vector<Variable> vars = {a, b};
224 // LinearExpression expr(8.0);
225 // expr.AddSum(vars);
226 // Results in expr having the value a + b + 8.0.
227 //
228 // Compile time requirements:
229 // * Iterable is a sequence (an array or object with begin() and end()).
230 // * The type of an element of items is one of double, Variable, LinearTerm
231 // or LinearExpression (or is implicitly convertible to one of these types,
232 // e.g. int).
233 //
234 // Note: The implementation is equivalent to:
235 // for(const auto item : items) {
236 // *this += item;
237 // }
238 template <typename Iterable>
239 inline void AddSum(const Iterable& items);
240
241 // Adds the inner product of left and right to this.
242 //
243 // Specifically, letting
244 // (l_1, l_2 ..., l_n) = left,
245 // (r_1, r_2, ..., r_n) = right,
246 // adds
247 // l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n
248 // to this.
249 //
250 // Example:
251 // Variable a = ...;
252 // Variable b = ...;
253 // const std::vector<Variable> left = {a, b};
254 // const std::vector<double> right = {10.0, 2.0};
255 // LinearExpression expr(3.0);
256 // expr.AddInnerProduct(left, right)
257 // Results in expr having the value 10.0 * a + 2.0 * b + 3.0.
258 //
259 // Compile time requirements:
260 // * LeftIterable and RightIterable are both sequences (arrays or objects
261 // with begin() and end())
262 // * For both left and right, their elements a type of either double,
263 // Variable, LinearTerm or LinearExpression (or type implicitly convertible
264 // to one of these types, e.g. int).
265 // * At least one of left or right has elements with type double (or a type
266 // implicitly convertible, e.g. int).
267 // Runtime requirements (or CHECK fails):
268 // * left and right have an equal number of elements.
269 //
270 // Note: The implementation is equivalent to:
271 // for(const auto& [l, r] : zip(left, right)) {
272 // *this += l * r;
273 // }
274 // In particular, the multiplication will be performed on the types of the
275 // elements in left and right (take care with low precision types), but the
276 // addition will always use double precision.
277 template <typename LeftIterable, typename RightIterable>
278 inline void AddInnerProduct(const LeftIterable& left,
279 const RightIterable& right);
280
281 // Returns the terms in this expression.
282 inline const VariableMap<double>& terms() const;
283 inline double offset() const;
284
285 // Compute the numeric value of this expression when variables are substituted
286 // by their values in variable_values.
287 //
288 // Will CHECK fail the underlying model is different or if a variable in
289 // terms() is missing from variables_values.
290 double Evaluate(const VariableMap<double>& variable_values) const;
291
292 // Compute the numeric value of this expression when variables are substituted
293 // by their values in variable_values, or zero if missing from the map.
294 //
295 // Will CHECK fail the underlying model is different.
296 double EvaluateWithDefaultZero(
297 const VariableMap<double>& variable_values) const;
298
299 inline IndexedModel* model() const;
300 inline const absl::flat_hash_map<VariableId, double>& raw_terms() const;
301
302 #ifdef USE_LINEAR_EXPRESSION_COUNTERS
303 static thread_local int num_calls_default_constructor_;
304 static thread_local int num_calls_copy_constructor_;
305 static thread_local int num_calls_move_constructor_;
306 static thread_local int num_calls_initializer_list_constructor_;
307 // Reset all counters in the current thread to 0.
308 static void ResetCounters();
309 #endif // USE_LINEAR_EXPRESSION_COUNTERS
310
311 private:
312 friend LinearExpression operator-(LinearExpression expr);
313 friend std::ostream& operator<<(std::ostream& ostr,
314 const LinearExpression& expression);
315
316 VariableMap<double> terms_;
317 double offset_ = 0.0;
318 };
319
320 // Returns the sum of the elements of items.
321 //
322 // Specifically, letting
323 // (i_1, i_2, ..., i_n) = items
324 // returns
325 // i_1 + i_2 + ... + i_n.
326 //
327 // Example:
328 // Variable a = ...;
329 // Variable b = ...;
330 // const std::vector<Variable> vars = {a, b, a};
331 // Sum(vars)
332 // => 2.0 * a + b
333 // Note, instead of:
334 // LinearExpression expr(3.0);
335 // expr += Sum(items);
336 // Prefer:
337 // expr.AddSum(items);
338 //
339 // See LinearExpression::AddSum() for a precise contract on the type Iterable.
340 template <typename Iterable>
341 inline LinearExpression Sum(const Iterable& items);
342
343 // Returns the inner product of left and right.
344 //
345 // Specifically, letting
346 // (l_1, l_2 ..., l_n) = left,
347 // (r_1, r_2, ..., r_n) = right,
348 // returns
349 // l_1 * r_1 + l_2 * r_2 + ... + l_n * r_n.
350 //
351 // Example:
352 // Variable a = ...;
353 // Variable b = ...;
354 // const std::vector<Variable> left = {a, b};
355 // const std::vector<double> right = {10.0, 2.0};
356 // InnerProduct(left, right);
357 // -=> 10.0 * a + 2.0 * b
358 // Note, instead of:
359 // LinearExpression expr(3.0);
360 // expr += InnerProduct(left, right);
361 // Prefer:
362 // expr.AddInnerProduct(left, right);
363 //
364 // Requires that left and right have equal size, see
365 // LinearExpression::AddInnerProduct for a precise contract on template types.
366 template <typename LeftIterable, typename RightIterable>
367 inline LinearExpression InnerProduct(const LeftIterable& left,
368 const RightIterable& right);
369
370 std::ostream& operator<<(std::ostream& ostr,
371 const LinearExpression& expression);
372
373 // We intentionally pass one of the LinearExpression argument by value so
374 // that we don't make unnecessary copies of temporary objects by using the move
375 // constructor and the returned values optimization (RVO).
376 inline LinearExpression operator-(LinearExpression expr);
377 inline LinearExpression operator+(Variable lhs, double rhs);
378 inline LinearExpression operator+(double lhs, Variable rhs);
379 inline LinearExpression operator+(Variable lhs, Variable rhs);
380 inline LinearExpression operator+(const LinearTerm& lhs, double rhs);
381 inline LinearExpression operator+(double lhs, const LinearTerm& rhs);
382 inline LinearExpression operator+(const LinearTerm& lhs, Variable rhs);
383 inline LinearExpression operator+(Variable lhs, const LinearTerm& rhs);
384 inline LinearExpression operator+(const LinearTerm& lhs, const LinearTerm& rhs);
385 inline LinearExpression operator+(LinearExpression lhs, double rhs);
386 inline LinearExpression operator+(double lhs, LinearExpression rhs);
387 inline LinearExpression operator+(LinearExpression lhs, Variable rhs);
388 inline LinearExpression operator+(Variable lhs, LinearExpression rhs);
389 inline LinearExpression operator+(LinearExpression lhs, const LinearTerm& rhs);
390 inline LinearExpression operator+(LinearTerm lhs, LinearExpression rhs);
391 inline LinearExpression operator+(LinearExpression lhs,
392 const LinearExpression& rhs);
393 inline LinearExpression operator-(Variable lhs, double rhs);
394 inline LinearExpression operator-(double lhs, Variable rhs);
395 inline LinearExpression operator-(Variable lhs, Variable rhs);
396 inline LinearExpression operator-(const LinearTerm& lhs, double rhs);
397 inline LinearExpression operator-(double lhs, const LinearTerm& rhs);
398 inline LinearExpression operator-(const LinearTerm& lhs, Variable rhs);
399 inline LinearExpression operator-(Variable lhs, const LinearTerm& rhs);
400 inline LinearExpression operator-(const LinearTerm& lhs, const LinearTerm& rhs);
401 inline LinearExpression operator-(LinearExpression lhs, double rhs);
402 inline LinearExpression operator-(double lhs, LinearExpression rhs);
403 inline LinearExpression operator-(LinearExpression lhs, Variable rhs);
404 inline LinearExpression operator-(Variable lhs, LinearExpression rhs);
405 inline LinearExpression operator-(LinearExpression lhs, const LinearTerm& rhs);
406 inline LinearExpression operator-(LinearTerm lhs, LinearExpression rhs);
407 inline LinearExpression operator-(LinearExpression lhs,
408 const LinearExpression& rhs);
409 inline LinearExpression operator*(LinearExpression lhs, double rhs);
410 inline LinearExpression operator*(double lhs, LinearExpression rhs);
411 inline LinearExpression operator/(LinearExpression lhs, double rhs);
412
413 namespace internal {
414
415 // The result of the equality comparison between two Variable.
416 //
417 // We use an object here to delay the evaluation of equality so that we can use
418 // the operator== in two use-cases:
419 //
420 // 1. when the user want to test that two Variable values references the same
421 // variable. This is supported by having this object support implicit
422 // conversion to bool.
423 //
424 // 2. when the user want to use the equality to create a constraint of equality
425 // between two variables.
426 struct VariablesEquality {
427 // Users are not expected to call this constructor. Instead they should only
428 // use the overload of `operator==` that returns this when comparing two
429 // Variable. For example `x == y`.
430 inline VariablesEquality(Variable lhs, Variable rhs);
431 inline operator bool() const; // NOLINT
432 Variable lhs;
433 Variable rhs;
434 };
435
436 } // namespace internal
437
438 inline internal::VariablesEquality operator==(const Variable& lhs,
439 const Variable& rhs);
440 inline bool operator!=(const Variable& lhs, const Variable& rhs);
441
442 // A LinearExpression with a lower bound.
443 struct LowerBoundedLinearExpression {
444 // Users are not expected to use this constructor. Instead they should build
445 // this object using the overloads of >= and <= operators. For example `x + y
446 // >= 3`.
447 inline LowerBoundedLinearExpression(LinearExpression expression,
448 double lower_bound);
449 LinearExpression expression;
450 double lower_bound;
451 };
452
453 // A LinearExpression with an upper bound.
454 struct UpperBoundedLinearExpression {
455 // Users are not expected to use this constructor. Instead they should build
456 // this object using the overloads of >= and <= operators. For example `x + y
457 // <= 3`.
458 inline UpperBoundedLinearExpression(LinearExpression expression,
459 double upper_bound);
460 LinearExpression expression;
461 double upper_bound;
462 };
463
464 // A LinearExpression with upper and lower bounds.
465 struct BoundedLinearExpression {
466 // Users are not expected to use this constructor. Instead they should build
467 // this object using the overloads of >= and <= operators. For example `3 <= x
468 // + y <= 3`.
469 inline BoundedLinearExpression(LinearExpression expression,
470 double lower_bound, double upper_bound);
471 // Users are not expected to use this constructor. This implicit conversion
472 // will be used where a BoundedLinearExpression is expected and the user uses
473 // == comparison of two variables. For example `AddLinearConstraint(x == y);`.
474 inline BoundedLinearExpression( // NOLINT
475 const internal::VariablesEquality& eq);
476 inline BoundedLinearExpression( // NOLINT
477 LowerBoundedLinearExpression lb_expression);
478 inline BoundedLinearExpression( // NOLINT
479 UpperBoundedLinearExpression ub_expression);
480
481 // Returns the actual lower_bound after taking into account the linear
482 // expression offset.
483 inline double lower_bound_minus_offset() const;
484 // Returns the actual upper_bound after taking into account the linear
485 // expression offset.
486 inline double upper_bound_minus_offset() const;
487
488 LinearExpression expression;
489 double lower_bound;
490 double upper_bound;
491 };
492
493 std::ostream& operator<<(std::ostream& ostr,
494 const BoundedLinearExpression& bounded_expression);
495
496 // We intentionally pass the LinearExpression argument by value so that we don't
497 // make unnecessary copies of temporary objects by using the move constructor
498 // and the returned values optimization (RVO).
499 inline LowerBoundedLinearExpression operator>=(LinearExpression expression,
500 double constant);
501 inline LowerBoundedLinearExpression operator<=(double constant,
502 LinearExpression expression);
503 inline LowerBoundedLinearExpression operator>=(const LinearTerm& term,
504 double constant);
505 inline LowerBoundedLinearExpression operator<=(double constant,
506 const LinearTerm& term);
507 inline LowerBoundedLinearExpression operator>=(Variable variable,
508 double constant);
509 inline LowerBoundedLinearExpression operator<=(double constant,
510 Variable variable);
511 inline UpperBoundedLinearExpression operator<=(LinearExpression expression,
512 double constant);
513 inline UpperBoundedLinearExpression operator>=(double constant,
514 LinearExpression expression);
515 inline UpperBoundedLinearExpression operator<=(const LinearTerm& term,
516 double constant);
517 inline UpperBoundedLinearExpression operator>=(double constant,
518 const LinearTerm& term);
519 inline UpperBoundedLinearExpression operator<=(Variable variable,
520 double constant);
521 inline UpperBoundedLinearExpression operator>=(double constant,
522 Variable variable);
523
524 // We intentionally pass the UpperBoundedLinearExpression and
525 // LowerBoundedLinearExpression arguments by value so that we don't
526 // make unnecessary copies of temporary objects by using the move constructor
527 // and the returned values optimization (RVO).
528 inline BoundedLinearExpression operator<=(LowerBoundedLinearExpression lhs,
529 double rhs);
530 inline BoundedLinearExpression operator>=(double lhs,
531 LowerBoundedLinearExpression rhs);
532 inline BoundedLinearExpression operator>=(UpperBoundedLinearExpression lhs,
533 double rhs);
534 inline BoundedLinearExpression operator<=(double lhs,
535 UpperBoundedLinearExpression rhs);
536 // We intentionally pass one LinearExpression argument by value so that we don't
537 // make unnecessary copies of temporary objects by using the move constructor
538 // and the returned values optimization (RVO).
539 inline BoundedLinearExpression operator<=(LinearExpression lhs,
540 const LinearExpression& rhs);
541 inline BoundedLinearExpression operator>=(LinearExpression lhs,
542 const LinearExpression& rhs);
543 inline BoundedLinearExpression operator<=(LinearExpression lhs,
544 const LinearTerm& rhs);
545 inline BoundedLinearExpression operator>=(LinearExpression lhs,
546 const LinearTerm& rhs);
547 inline BoundedLinearExpression operator<=(const LinearTerm& lhs,
548 LinearExpression rhs);
549 inline BoundedLinearExpression operator>=(const LinearTerm& lhs,
550 LinearExpression rhs);
551 inline BoundedLinearExpression operator<=(LinearExpression lhs, Variable rhs);
552 inline BoundedLinearExpression operator>=(LinearExpression lhs, Variable rhs);
553 inline BoundedLinearExpression operator<=(Variable lhs, LinearExpression rhs);
554 inline BoundedLinearExpression operator>=(Variable lhs, LinearExpression rhs);
555 inline BoundedLinearExpression operator<=(const LinearTerm& lhs,
556 const LinearTerm& rhs);
557 inline BoundedLinearExpression operator>=(const LinearTerm& lhs,
558 const LinearTerm& rhs);
559 inline BoundedLinearExpression operator<=(const LinearTerm& lhs, Variable rhs);
560 inline BoundedLinearExpression operator>=(const LinearTerm& lhs, Variable rhs);
561 inline BoundedLinearExpression operator<=(Variable lhs, const LinearTerm& rhs);
562 inline BoundedLinearExpression operator>=(Variable lhs, const LinearTerm& rhs);
563 inline BoundedLinearExpression operator<=(Variable lhs, Variable rhs);
564 inline BoundedLinearExpression operator>=(Variable lhs, Variable rhs);
565 inline BoundedLinearExpression operator==(LinearExpression lhs,
566 const LinearExpression& rhs);
567 inline BoundedLinearExpression operator==(LinearExpression lhs,
568 const LinearTerm& rhs);
569 inline BoundedLinearExpression operator==(const LinearTerm& lhs,
570 LinearExpression rhs);
571 inline BoundedLinearExpression operator==(LinearExpression lhs, Variable rhs);
572 inline BoundedLinearExpression operator==(Variable lhs, LinearExpression rhs);
573 inline BoundedLinearExpression operator==(LinearExpression lhs, double rhs);
574 inline BoundedLinearExpression operator==(double lhs, LinearExpression rhs);
575 inline BoundedLinearExpression operator==(const LinearTerm& lhs,
576 const LinearTerm& rhs);
577 inline BoundedLinearExpression operator==(const LinearTerm& lhs, Variable rhs);
578 inline BoundedLinearExpression operator==(Variable lhs, const LinearTerm& rhs);
579 inline BoundedLinearExpression operator==(const LinearTerm& lhs, double rhs);
580 inline BoundedLinearExpression operator==(double lhs, const LinearTerm& rhs);
581 inline BoundedLinearExpression operator==(Variable lhs, double rhs);
582 inline BoundedLinearExpression operator==(double lhs, Variable rhs);
583
584 ////////////////////////////////////////////////////////////////////////////////
585 // Inline function implementations
586 ////////////////////////////////////////////////////////////////////////////////
587
588 ////////////////////////////////////////////////////////////////////////////////
589 // Variable
590 ////////////////////////////////////////////////////////////////////////////////
591
Variable(IndexedModel * const model,const VariableId id)592 Variable::Variable(IndexedModel* const model, const VariableId id)
593 : model_(model), id_(id) {
594 DCHECK(model != nullptr);
595 }
596
id()597 int64_t Variable::id() const { return id_.value(); }
598
typed_id()599 VariableId Variable::typed_id() const { return id_; }
600
model()601 IndexedModel* Variable::model() const { return model_; }
602
lower_bound()603 double Variable::lower_bound() const {
604 return model_->variable_lower_bound(id_);
605 }
upper_bound()606 double Variable::upper_bound() const {
607 return model_->variable_upper_bound(id_);
608 }
is_integer()609 bool Variable::is_integer() const { return model_->is_variable_integer(id_); }
name()610 const std::string& Variable::name() const { return model_->variable_name(id_); }
611
set_lower_bound(const double lower_bound)612 void Variable::set_lower_bound(const double lower_bound) const {
613 model_->set_variable_lower_bound(id_, lower_bound);
614 }
set_upper_bound(const double upper_bound)615 void Variable::set_upper_bound(const double upper_bound) const {
616 model_->set_variable_upper_bound(id_, upper_bound);
617 }
set_is_integer(const bool is_integer)618 void Variable::set_is_integer(const bool is_integer) const {
619 model_->set_variable_is_integer(id_, is_integer);
620 }
set_integer()621 void Variable::set_integer() const { set_is_integer(true); }
set_continuous()622 void Variable::set_continuous() const { set_is_integer(false); }
623
624 template <typename H>
AbslHashValue(H h,const Variable & variable)625 H AbslHashValue(H h, const Variable& variable) {
626 return H::combine(std::move(h), variable.id_.value(), variable.model_);
627 }
628
629 std::ostream& operator<<(std::ostream& ostr, const Variable& variable) {
630 // TODO(b/170992529): handle the case of empty variable name and quoting when
631 // the variable name contains invalid characters.
632 ostr << variable.name();
633 return ostr;
634 }
635
636 ////////////////////////////////////////////////////////////////////////////////
637 // LinearTerm
638 ////////////////////////////////////////////////////////////////////////////////
639
LinearTerm(Variable variable,const double coefficient)640 LinearTerm::LinearTerm(Variable variable, const double coefficient)
641 : variable(std::move(variable)), coefficient(coefficient) {}
642
643 LinearTerm LinearTerm::operator-() const {
644 return LinearTerm(variable, -coefficient);
645 }
646
647 LinearTerm& LinearTerm::operator*=(const double d) {
648 coefficient *= d;
649 return *this;
650 }
651
652 LinearTerm& LinearTerm::operator/=(const double d) {
653 coefficient /= d;
654 return *this;
655 }
656
657 LinearTerm operator*(const double coefficient, LinearTerm term) {
658 term *= coefficient;
659 return term;
660 }
661
662 LinearTerm operator*(LinearTerm term, const double coefficient) {
663 term *= coefficient;
664 return term;
665 }
666
667 LinearTerm operator*(const double coefficient, Variable variable) {
668 return LinearTerm(std::move(variable), coefficient);
669 }
670
671 LinearTerm operator*(Variable variable, const double coefficient) {
672 return LinearTerm(std::move(variable), coefficient);
673 }
674
675 LinearTerm operator/(LinearTerm term, const double coefficient) {
676 term /= coefficient;
677 return term;
678 }
679
680 LinearTerm operator/(Variable variable, const double coefficient) {
681 return LinearTerm(std::move(variable), 1 / coefficient);
682 }
683
684 ////////////////////////////////////////////////////////////////////////////////
685 // LinearExpression
686 ////////////////////////////////////////////////////////////////////////////////
687
LinearExpression(std::initializer_list<LinearTerm> terms,const double offset)688 LinearExpression::LinearExpression(std::initializer_list<LinearTerm> terms,
689 const double offset)
690 : offset_(offset) {
691 #ifdef USE_LINEAR_EXPRESSION_COUNTERS
692 ++num_calls_initializer_list_constructor_;
693 #endif // USE_LINEAR_EXPRESSION_COUNTERS
694 for (const auto& term : terms) {
695 // The same variable may appear multiple times in the input list; we must
696 // accumulate the coefficients.
697 terms_[term.variable] += term.coefficient;
698 }
699 }
700
LinearExpression(double offset)701 LinearExpression::LinearExpression(double offset)
702 : LinearExpression({}, offset) {}
703
LinearExpression(Variable variable)704 LinearExpression::LinearExpression(Variable variable)
705 : LinearExpression({LinearTerm(variable, 1.0)}, 0.0) {}
706
LinearExpression(const LinearTerm & term)707 LinearExpression::LinearExpression(const LinearTerm& term)
708 : LinearExpression({term}, 0.0) {}
709
710 LinearExpression operator-(LinearExpression expr) {
711 expr.offset_ = -expr.offset_;
712 for (auto term : expr.terms_) {
713 term.second = -term.second;
714 }
715 return expr;
716 }
717
718 LinearExpression operator+(const Variable lhs, const double rhs) {
719 return LinearTerm(lhs, 1.0) + rhs;
720 }
721
722 LinearExpression operator+(const double lhs, const Variable rhs) {
723 return lhs + LinearTerm(rhs, 1.0);
724 }
725
726 LinearExpression operator+(const Variable lhs, const Variable rhs) {
727 return LinearTerm(lhs, 1.0) + LinearTerm(rhs, 1.0);
728 }
729
730 LinearExpression operator+(const LinearTerm& lhs, const double rhs) {
731 return LinearExpression({lhs}, rhs);
732 }
733
734 LinearExpression operator+(const double lhs, const LinearTerm& rhs) {
735 return LinearExpression({rhs}, lhs);
736 }
737
738 LinearExpression operator+(const LinearTerm& lhs, const Variable rhs) {
739 return lhs + LinearTerm(rhs, 1.0);
740 }
741
742 LinearExpression operator+(const Variable lhs, const LinearTerm& rhs) {
743 return LinearTerm(lhs, 1.0) + rhs;
744 }
745
746 LinearExpression operator+(const LinearTerm& lhs, const LinearTerm& rhs) {
747 return LinearExpression({lhs, rhs}, 0);
748 }
749
750 LinearExpression operator+(LinearExpression lhs, const double rhs) {
751 lhs += rhs;
752 return lhs;
753 }
754
755 LinearExpression operator+(const double lhs, LinearExpression rhs) {
756 rhs += lhs;
757 return rhs;
758 }
759
760 LinearExpression operator+(LinearExpression lhs, const Variable rhs) {
761 return std::move(lhs) + LinearTerm(rhs, 1.0);
762 }
763
764 LinearExpression operator+(const Variable lhs, LinearExpression rhs) {
765 return LinearTerm(lhs, 1.0) + std::move(rhs);
766 }
767
768 LinearExpression operator+(LinearExpression lhs, const LinearTerm& rhs) {
769 lhs += rhs;
770 return lhs;
771 }
772
773 LinearExpression operator+(LinearTerm lhs, LinearExpression rhs) {
774 rhs += lhs;
775 return rhs;
776 }
777
778 LinearExpression operator+(LinearExpression lhs, const LinearExpression& rhs) {
779 lhs += rhs;
780 return lhs;
781 }
782
783 LinearExpression operator-(const Variable lhs, const double rhs) {
784 return LinearTerm(lhs, 1.0) - rhs;
785 }
786
787 LinearExpression operator-(const double lhs, const Variable rhs) {
788 return lhs - LinearTerm(rhs, 1.0);
789 }
790
791 LinearExpression operator-(const Variable lhs, const Variable rhs) {
792 return LinearTerm(lhs, 1.0) - LinearTerm(rhs, 1.0);
793 }
794
795 LinearExpression operator-(const LinearTerm& lhs, const double rhs) {
796 return LinearExpression({lhs}, -rhs);
797 }
798
799 LinearExpression operator-(const double lhs, const LinearTerm& rhs) {
800 return LinearExpression({-rhs}, lhs);
801 }
802
803 LinearExpression operator-(const LinearTerm& lhs, const Variable rhs) {
804 return lhs - LinearTerm(rhs, 1.0);
805 }
806
807 LinearExpression operator-(const Variable lhs, const LinearTerm& rhs) {
808 return LinearTerm(lhs, 1.0) - rhs;
809 }
810
811 LinearExpression operator-(const LinearTerm& lhs, const LinearTerm& rhs) {
812 return LinearExpression({lhs, -rhs}, 0);
813 }
814
815 LinearExpression operator-(LinearExpression lhs, const double rhs) {
816 lhs -= rhs;
817 return lhs;
818 }
819
820 LinearExpression operator-(const double lhs, LinearExpression rhs) {
821 auto ret = -std::move(rhs);
822 ret += lhs;
823 return ret;
824 }
825
826 LinearExpression operator-(LinearExpression lhs, const Variable rhs) {
827 return std::move(lhs) - LinearTerm(rhs, 1.0);
828 }
829
830 LinearExpression operator-(const Variable lhs, LinearExpression rhs) {
831 return LinearTerm(lhs, 1.0) - std::move(rhs);
832 }
833
834 LinearExpression operator-(LinearExpression lhs, const LinearTerm& rhs) {
835 lhs -= rhs;
836 return lhs;
837 }
838
839 LinearExpression operator-(LinearTerm lhs, LinearExpression rhs) {
840 auto ret = -std::move(rhs);
841 ret += lhs;
842 return ret;
843 }
844
845 LinearExpression operator-(LinearExpression lhs, const LinearExpression& rhs) {
846 lhs -= rhs;
847 return lhs;
848 }
849
850 LinearExpression operator*(LinearExpression lhs, const double rhs) {
851 lhs *= rhs;
852 return lhs;
853 }
854
855 LinearExpression operator*(const double lhs, LinearExpression rhs) {
856 rhs *= lhs;
857 return rhs;
858 }
859
860 LinearExpression operator/(LinearExpression lhs, const double rhs) {
861 lhs /= rhs;
862 return lhs;
863 }
864
865 LinearExpression& LinearExpression::operator+=(const LinearExpression& other) {
866 terms_.Add(other.terms_);
867 offset_ += other.offset_;
868 return *this;
869 }
870
871 LinearExpression& LinearExpression::operator+=(const LinearTerm& term) {
872 terms_[term.variable] += term.coefficient;
873 return *this;
874 }
875
876 LinearExpression& LinearExpression::operator+=(const Variable variable) {
877 return *this += LinearTerm(variable, 1.0);
878 }
879
880 LinearExpression& LinearExpression::operator+=(const double value) {
881 offset_ += value;
882 return *this;
883 }
884
885 LinearExpression& LinearExpression::operator-=(const LinearExpression& other) {
886 terms_.Subtract(other.terms_);
887 offset_ -= other.offset_;
888 return *this;
889 }
890
891 LinearExpression& LinearExpression::operator-=(const LinearTerm& term) {
892 terms_[term.variable] -= term.coefficient;
893 return *this;
894 }
895
896 LinearExpression& LinearExpression::operator-=(const Variable variable) {
897 return *this -= LinearTerm(variable, 1.0);
898 }
899
900 LinearExpression& LinearExpression::operator-=(const double value) {
901 offset_ -= value;
902 return *this;
903 }
904
905 LinearExpression& LinearExpression::operator*=(const double value) {
906 offset_ *= value;
907 for (auto term : terms_) {
908 term.second *= value;
909 }
910 return *this;
911 }
912
913 LinearExpression& LinearExpression::operator/=(const double value) {
914 offset_ /= value;
915 for (auto term : terms_) {
916 term.second /= value;
917 }
918 return *this;
919 }
920
921 template <typename Iterable>
AddSum(const Iterable & items)922 void LinearExpression::AddSum(const Iterable& items) {
923 for (const auto& item : items) {
924 *this += item;
925 }
926 }
927
928 template <typename Iterable>
Sum(const Iterable & items)929 LinearExpression Sum(const Iterable& items) {
930 LinearExpression result;
931 result.AddSum(items);
932 return result;
933 }
934
935 template <typename LeftIterable, typename RightIterable>
AddInnerProduct(const LeftIterable & left,const RightIterable & right)936 void LinearExpression::AddInnerProduct(const LeftIterable& left,
937 const RightIterable& right) {
938 using std::begin;
939 using std::end;
940 auto l = begin(left);
941 auto r = begin(right);
942 auto l_end = end(left);
943 auto r_end = end(right);
944 for (; l != l_end && r != r_end; ++l, ++r) {
945 *this += (*l) * (*r);
946 }
947 CHECK(l == l_end)
948 << "left had more elements than right, sizes should be equal";
949 CHECK(r == r_end)
950 << "right had more elements than left, sizes should be equal";
951 }
952
953 template <typename LeftIterable, typename RightIterable>
InnerProduct(const LeftIterable & left,const RightIterable & right)954 LinearExpression InnerProduct(const LeftIterable& left,
955 const RightIterable& right) {
956 LinearExpression result;
957 result.AddInnerProduct(left, right);
958 return result;
959 }
960
terms()961 const VariableMap<double>& LinearExpression::terms() const { return terms_; }
962
offset()963 double LinearExpression::offset() const { return offset_; }
964
model()965 IndexedModel* LinearExpression::model() const { return terms_.model(); }
966
raw_terms()967 const absl::flat_hash_map<VariableId, double>& LinearExpression::raw_terms()
968 const {
969 return terms_.raw_map();
970 }
971
972 ////////////////////////////////////////////////////////////////////////////////
973 // VariablesEquality
974 ////////////////////////////////////////////////////////////////////////////////
975
976 namespace internal {
977
VariablesEquality(Variable lhs,Variable rhs)978 VariablesEquality::VariablesEquality(Variable lhs, Variable rhs)
979 : lhs(std::move(lhs)), rhs(std::move(rhs)) {}
980
981 inline VariablesEquality::operator bool() const {
982 return lhs.typed_id() == rhs.typed_id() && lhs.model() == rhs.model();
983 }
984
985 } // namespace internal
986
987 internal::VariablesEquality operator==(const Variable& lhs,
988 const Variable& rhs) {
989 return internal::VariablesEquality(lhs, rhs);
990 }
991
992 bool operator!=(const Variable& lhs, const Variable& rhs) {
993 return !(lhs == rhs);
994 }
995
996 /////////////////////////////////////////////////////////////////////////////////
997 // LowerBoundedLinearExpression
998 // UpperBoundedLinearExpression
999 // BoundedLinearExpression
1000 ////////////////////////////////////////////////////////////////////////////////
1001
LowerBoundedLinearExpression(LinearExpression expression,const double lower_bound)1002 LowerBoundedLinearExpression::LowerBoundedLinearExpression(
1003 LinearExpression expression, const double lower_bound)
1004 : expression(std::move(expression)), lower_bound(lower_bound) {}
1005
UpperBoundedLinearExpression(LinearExpression expression,const double upper_bound)1006 UpperBoundedLinearExpression::UpperBoundedLinearExpression(
1007 LinearExpression expression, const double upper_bound)
1008 : expression(std::move(expression)), upper_bound(upper_bound) {}
1009
BoundedLinearExpression(LinearExpression expression,const double lower_bound,const double upper_bound)1010 BoundedLinearExpression::BoundedLinearExpression(LinearExpression expression,
1011 const double lower_bound,
1012 const double upper_bound)
1013 : expression(std::move(expression)),
1014 lower_bound(lower_bound),
1015 upper_bound(upper_bound) {}
1016
BoundedLinearExpression(const internal::VariablesEquality & eq)1017 BoundedLinearExpression::BoundedLinearExpression(
1018 const internal::VariablesEquality& eq)
1019 : expression({{eq.lhs, 1.0}, {eq.rhs, -1.0}}, 0.0),
1020 lower_bound(0.0),
1021 upper_bound(0.0) {}
1022
BoundedLinearExpression(LowerBoundedLinearExpression lb_expression)1023 BoundedLinearExpression::BoundedLinearExpression(
1024 LowerBoundedLinearExpression lb_expression)
1025 : expression(std::move(lb_expression.expression)),
1026 lower_bound(lb_expression.lower_bound),
1027 upper_bound(std::numeric_limits<double>::infinity()) {}
1028
BoundedLinearExpression(UpperBoundedLinearExpression ub_expression)1029 BoundedLinearExpression::BoundedLinearExpression(
1030 UpperBoundedLinearExpression ub_expression)
1031 : expression(std::move(ub_expression.expression)),
1032 lower_bound(-std::numeric_limits<double>::infinity()),
1033 upper_bound(ub_expression.upper_bound) {}
1034
lower_bound_minus_offset()1035 double BoundedLinearExpression::lower_bound_minus_offset() const {
1036 return lower_bound - expression.offset();
1037 }
1038
upper_bound_minus_offset()1039 double BoundedLinearExpression::upper_bound_minus_offset() const {
1040 return upper_bound - expression.offset();
1041 }
1042
1043 LowerBoundedLinearExpression operator>=(LinearExpression expression,
1044 const double constant) {
1045 return LowerBoundedLinearExpression(std::move(expression), constant);
1046 }
1047
1048 LowerBoundedLinearExpression operator<=(const double constant,
1049 LinearExpression expression) {
1050 return LowerBoundedLinearExpression(std::move(expression), constant);
1051 }
1052
1053 LowerBoundedLinearExpression operator>=(const LinearTerm& term,
1054 const double constant) {
1055 return LowerBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1056 }
1057
1058 LowerBoundedLinearExpression operator<=(const double constant,
1059 const LinearTerm& term) {
1060 return LowerBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1061 }
1062
1063 LowerBoundedLinearExpression operator>=(const Variable variable,
1064 const double constant) {
1065 return LinearTerm(variable, 1.0) >= constant;
1066 }
1067
1068 LowerBoundedLinearExpression operator<=(const double constant,
1069 const Variable variable) {
1070 return constant <= LinearTerm(variable, 1.0);
1071 }
1072
1073 UpperBoundedLinearExpression operator<=(LinearExpression expression,
1074 const double constant) {
1075 return UpperBoundedLinearExpression(std::move(expression), constant);
1076 }
1077
1078 UpperBoundedLinearExpression operator>=(const double constant,
1079 LinearExpression expression) {
1080 return UpperBoundedLinearExpression(std::move(expression), constant);
1081 }
1082
1083 UpperBoundedLinearExpression operator<=(const LinearTerm& term,
1084 const double constant) {
1085 return UpperBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1086 }
1087
1088 UpperBoundedLinearExpression operator>=(const double constant,
1089 const LinearTerm& term) {
1090 return UpperBoundedLinearExpression(LinearExpression({term}, 0.0), constant);
1091 }
1092
1093 UpperBoundedLinearExpression operator<=(const Variable variable,
1094 const double constant) {
1095 return LinearTerm(variable, 1.0) <= constant;
1096 }
1097
1098 UpperBoundedLinearExpression operator>=(const double constant,
1099 const Variable variable) {
1100 return constant >= LinearTerm(variable, 1.0);
1101 }
1102
1103 BoundedLinearExpression operator<=(LowerBoundedLinearExpression lhs,
1104 const double rhs) {
1105 return BoundedLinearExpression(std::move(lhs.expression),
1106 /*lower_bound=*/lhs.lower_bound,
1107 /*upper_bound=*/rhs);
1108 }
1109
1110 BoundedLinearExpression operator>=(const double lhs,
1111 LowerBoundedLinearExpression rhs) {
1112 return BoundedLinearExpression(std::move(rhs.expression),
1113 /*lower_bound=*/rhs.lower_bound,
1114 /*upper_bound=*/lhs);
1115 }
1116
1117 BoundedLinearExpression operator>=(UpperBoundedLinearExpression lhs,
1118 const double rhs) {
1119 return BoundedLinearExpression(std::move(lhs.expression),
1120 /*lower_bound=*/rhs,
1121 /*upper_bound=*/lhs.upper_bound);
1122 }
1123
1124 BoundedLinearExpression operator<=(const double lhs,
1125 UpperBoundedLinearExpression rhs) {
1126 return BoundedLinearExpression(std::move(rhs.expression),
1127 /*lower_bound=*/lhs,
1128 /*upper_bound=*/rhs.upper_bound);
1129 }
1130
1131 BoundedLinearExpression operator<=(LinearExpression lhs,
1132 const LinearExpression& rhs) {
1133 lhs -= rhs;
1134 return BoundedLinearExpression(
1135 std::move(lhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1136 /*upper_bound=*/0.0);
1137 }
1138
1139 BoundedLinearExpression operator>=(LinearExpression lhs,
1140 const LinearExpression& rhs) {
1141 lhs -= rhs;
1142 return BoundedLinearExpression(
1143 std::move(lhs), /*lower_bound=*/0.0,
1144 /*upper_bound=*/std::numeric_limits<double>::infinity());
1145 }
1146
1147 BoundedLinearExpression operator<=(LinearExpression lhs,
1148 const LinearTerm& rhs) {
1149 lhs -= rhs;
1150 return BoundedLinearExpression(
1151 std::move(lhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1152 /*upper_bound=*/0.0);
1153 }
1154
1155 BoundedLinearExpression operator>=(LinearExpression lhs,
1156 const LinearTerm& rhs) {
1157 lhs -= rhs;
1158 return BoundedLinearExpression(
1159 std::move(lhs), /*lower_bound=*/0.0,
1160 /*upper_bound=*/std::numeric_limits<double>::infinity());
1161 }
1162
1163 BoundedLinearExpression operator<=(const LinearTerm& lhs,
1164 LinearExpression rhs) {
1165 rhs -= lhs;
1166 return BoundedLinearExpression(
1167 std::move(rhs), /*lower_bound=*/0.0,
1168 /*upper_bound=*/std::numeric_limits<double>::infinity());
1169 }
1170
1171 BoundedLinearExpression operator>=(const LinearTerm& lhs,
1172 LinearExpression rhs) {
1173 rhs -= lhs;
1174 return BoundedLinearExpression(
1175 std::move(rhs), /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1176 /*upper_bound=*/0.0);
1177 }
1178
1179 BoundedLinearExpression operator<=(LinearExpression lhs, const Variable rhs) {
1180 return std::move(lhs) <= LinearTerm(rhs, 1.0);
1181 }
1182
1183 BoundedLinearExpression operator>=(LinearExpression lhs, const Variable rhs) {
1184 return std::move(lhs) >= LinearTerm(rhs, 1.0);
1185 }
1186
1187 BoundedLinearExpression operator<=(const Variable lhs, LinearExpression rhs) {
1188 return LinearTerm(lhs, 1.0) <= std::move(rhs);
1189 }
1190
1191 BoundedLinearExpression operator>=(const Variable lhs, LinearExpression rhs) {
1192 return LinearTerm(lhs, 1.0) >= std::move(rhs);
1193 }
1194
1195 BoundedLinearExpression operator<=(const LinearTerm& lhs,
1196 const LinearTerm& rhs) {
1197 return BoundedLinearExpression(
1198 LinearExpression({lhs, -rhs}, 0.0),
1199 /*lower_bound=*/-std::numeric_limits<double>::infinity(),
1200 /*upper_bound=*/0.0);
1201 }
1202
1203 BoundedLinearExpression operator>=(const LinearTerm& lhs,
1204 const LinearTerm& rhs) {
1205 return BoundedLinearExpression(
1206 LinearExpression({lhs, -rhs}, 0.0), /*lower_bound=*/0.0,
1207 /*upper_bound=*/std::numeric_limits<double>::infinity());
1208 }
1209
1210 BoundedLinearExpression operator<=(const LinearTerm& lhs, const Variable rhs) {
1211 return lhs <= LinearTerm(rhs, 1.0);
1212 }
1213
1214 BoundedLinearExpression operator>=(const LinearTerm& lhs, const Variable rhs) {
1215 return lhs >= LinearTerm(rhs, 1.0);
1216 }
1217
1218 BoundedLinearExpression operator<=(const Variable lhs, const LinearTerm& rhs) {
1219 return LinearTerm(lhs, 1.0) <= rhs;
1220 }
1221
1222 BoundedLinearExpression operator>=(const Variable lhs, const LinearTerm& rhs) {
1223 return LinearTerm(lhs, 1.0) >= rhs;
1224 }
1225
1226 BoundedLinearExpression operator<=(const Variable lhs, const Variable rhs) {
1227 return LinearTerm(lhs, 1.0) <= LinearTerm(rhs, 1.0);
1228 }
1229
1230 BoundedLinearExpression operator>=(const Variable lhs, const Variable rhs) {
1231 return LinearTerm(lhs, 1.0) >= LinearTerm(rhs, 1.0);
1232 }
1233
1234 BoundedLinearExpression operator==(LinearExpression lhs,
1235 const LinearExpression& rhs) {
1236 lhs -= rhs;
1237 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1238 /*upper_bound=*/0.0);
1239 }
1240
1241 BoundedLinearExpression operator==(LinearExpression lhs,
1242 const LinearTerm& rhs) {
1243 lhs -= rhs;
1244 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1245 /*upper_bound=*/0.0);
1246 }
1247
1248 BoundedLinearExpression operator==(const LinearTerm& lhs,
1249 LinearExpression rhs) {
1250 rhs -= lhs;
1251 return BoundedLinearExpression(std::move(rhs), /*lower_bound=*/0.0,
1252 /*upper_bound=*/0.0);
1253 }
1254
1255 BoundedLinearExpression operator==(LinearExpression lhs, const Variable rhs) {
1256 return std::move(lhs) == LinearTerm(rhs, 1.0);
1257 }
1258
1259 BoundedLinearExpression operator==(const Variable lhs, LinearExpression rhs) {
1260 return LinearTerm(lhs, 1.0) == std::move(rhs);
1261 }
1262
1263 BoundedLinearExpression operator==(LinearExpression lhs, const double rhs) {
1264 lhs -= rhs;
1265 return BoundedLinearExpression(std::move(lhs), /*lower_bound=*/0.0,
1266 /*upper_bound=*/0.0);
1267 }
1268
1269 BoundedLinearExpression operator==(const double lhs, LinearExpression rhs) {
1270 rhs -= lhs;
1271 return BoundedLinearExpression(std::move(rhs), /*lower_bound=*/0.0,
1272 /*upper_bound=*/0.0);
1273 }
1274
1275 BoundedLinearExpression operator==(const LinearTerm& lhs,
1276 const LinearTerm& rhs) {
1277 return BoundedLinearExpression(LinearExpression({lhs, -rhs}, 0.0),
1278 /*lower_bound=*/0.0,
1279 /*upper_bound=*/0.0);
1280 }
1281
1282 BoundedLinearExpression operator==(const LinearTerm& lhs, const Variable rhs) {
1283 return lhs == LinearTerm(rhs, 1.0);
1284 }
1285
1286 BoundedLinearExpression operator==(const Variable lhs, const LinearTerm& rhs) {
1287 return LinearTerm(lhs, 1.0) == rhs;
1288 }
1289
1290 BoundedLinearExpression operator==(const LinearTerm& lhs, const double rhs) {
1291 return BoundedLinearExpression(LinearExpression({lhs}, -rhs),
1292 /*lower_bound=*/0.0, /*upper_bound=*/0.0);
1293 }
1294
1295 BoundedLinearExpression operator==(const double lhs, const LinearTerm& rhs) {
1296 return BoundedLinearExpression(LinearExpression({rhs}, -lhs),
1297 /*lower_bound=*/0.0, /*upper_bound=*/0.0);
1298 }
1299
1300 BoundedLinearExpression operator==(const Variable lhs, const double rhs) {
1301 return LinearTerm(lhs, 1.0) == rhs;
1302 }
1303
1304 BoundedLinearExpression operator==(const double lhs, const Variable rhs) {
1305 return lhs == LinearTerm(rhs, 1.0);
1306 }
1307
1308 } // namespace math_opt
1309 } // namespace operations_research
1310
1311 #endif // OR_TOOLS_MATH_OPT_CPP_VARIABLE_AND_EXPRESSIONS_H_
1312