Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
linear_constraint.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#ifndef OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
15#define OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
16
17#include <algorithm>
18#include <cstdint>
19#include <cstring>
20#include <memory>
21#include <ostream>
22#include <string>
23#include <utility>
24#include <vector>
25
26#include "absl/base/attributes.h"
27#include "absl/log/check.h"
28#include "absl/strings/str_cat.h"
29#include "absl/types/span.h"
31#include "ortools/sat/integer.h"
33#include "ortools/sat/model.h"
37
38namespace operations_research {
39namespace sat {
40
41// One linear constraint on a set of Integer variables.
42// Important: there should be no duplicate variables.
43//
44// We also assume that we never have integer overflow when evaluating such
45// constraint at the ROOT node. This should be enforced by the checker for user
46// given constraints, and we must enforce it ourselves for the newly created
47// constraint. See ValidateLinearConstraintForOverflow().
49 IntegerValue lb;
50 IntegerValue ub;
51
52 // Rather than using two std::vector<> this class is optimized for memory
53 // consumption, given that most of our LinearConstraint are constructed once
54 // and for all.
55 //
56 // It is however up to clients to maintain the invariants that both vars
57 // and coeffs are properly allocated and of size num_terms.
58 //
59 // Also note that we did not add a copy constructor, to make sure that this is
60 // moved as often as possible. This allowed to optimize a few call site and so
61 // far we never copy this.
62 int num_terms = 0;
63 std::unique_ptr<IntegerVariable[]> vars;
64 std::unique_ptr<IntegerValue[]> coeffs;
65
66 LinearConstraint() = default;
67 LinearConstraint(IntegerValue _lb, IntegerValue _ub) : lb(_lb), ub(_ub) {}
68
69 // Compute the normalized violation of the constraint.
70 // For a cut, this is the usual definition of its efficacy.
73 const;
74
75 // Resize the LinearConstraint to have space for num_terms. We always
76 // re-allocate if the size is different to always be tight in memory.
77 void resize(int size) {
78 if (size == num_terms) return;
79 IntegerVariable* tmp_vars = new IntegerVariable[size];
80 IntegerValue* tmp_coeffs = new IntegerValue[size];
81 const int to_copy = std::min(size, num_terms);
82 if (to_copy > 0) {
83 memcpy(tmp_vars, vars.get(), sizeof(IntegerVariable) * to_copy);
84 memcpy(tmp_coeffs, coeffs.get(), sizeof(IntegerValue) * to_copy);
85 }
86 num_terms = size;
87 vars.reset(tmp_vars);
88 coeffs.reset(tmp_coeffs);
89 }
90
91 std::string DebugString() const {
92 std::string result;
93 if (lb.value() > kMinIntegerValue) {
94 absl::StrAppend(&result, lb.value(), " <= ");
95 }
96 for (int i = 0; i < num_terms; ++i) {
97 absl::StrAppend(&result, i > 0 ? " " : "",
99 }
100 if (ub.value() < kMaxIntegerValue) {
101 absl::StrAppend(&result, " <= ", ub.value());
102 }
103 return result;
104 }
105
106 bool IsEqualIgnoringBounds(const LinearConstraint& other) const {
107 if (this->num_terms != other.num_terms) return false;
108 if (this->num_terms == 0) return true;
109 if (memcmp(this->vars.get(), other.vars.get(),
110 sizeof(IntegerVariable) * this->num_terms)) {
111 return false;
112 }
113 if (memcmp(this->coeffs.get(), other.coeffs.get(),
114 sizeof(IntegerValue) * this->num_terms)) {
115 return false;
116 }
117 return true;
118 }
119
120 bool operator==(const LinearConstraint& other) const {
121 if (this->lb != other.lb) return false;
122 if (this->ub != other.ub) return false;
123 return IsEqualIgnoringBounds(other);
124 }
125
126 absl::Span<const IntegerVariable> VarsAsSpan() const {
127 return absl::MakeSpan(vars.get(), num_terms);
128 }
129
130 absl::Span<const IntegerValue> CoeffsAsSpan() const {
131 return absl::MakeSpan(coeffs.get(), num_terms);
132 }
133};
134
135inline std::ostream& operator<<(std::ostream& os, const LinearConstraint& ct) {
136 os << ct.DebugString();
137 return os;
138}
139
140// Helper struct to model linear expression for lin_min/lin_max constraints. The
141// canonical expression should only contain positive coefficients.
143 std::vector<IntegerVariable> vars;
144 std::vector<IntegerValue> coeffs;
145 IntegerValue offset = IntegerValue(0);
146
147 // Return[s] the evaluation of the linear expression.
149 lp_values) const;
150
151 IntegerValue LevelZeroMin(IntegerTrail* integer_trail) const;
152
153 // Returns lower bound of linear expression using variable bounds of the
154 // variables in expression.
155 IntegerValue Min(const IntegerTrail& integer_trail) const;
156
157 // Returns upper bound of linear expression using variable bounds of the
158 // variables in expression.
159 IntegerValue Max(const IntegerTrail& integer_trail) const;
160
161 std::string DebugString() const;
162};
163
164// Returns the same expression in the canonical form (all positive
165// coefficients).
167
168// Makes sure that any of our future computation on this constraint will not
169// cause overflow. We use the level zero bounds and use the same definition as
170// in PossibleIntegerOverflow() in the cp_model.proto checker.
171//
172// Namely, the sum of positive terms, the sum of negative terms and their
173// difference shouldn't overflow. Note that we don't validate the rhs, but if
174// the bounds are properly relaxed, then this shouldn't cause any issues.
175//
176// Note(user): We should avoid doing this test too often as it can be slow. At
177// least do not do it more than once on each constraint.
179 const IntegerTrail& integer_trail);
180
181// Preserves canonicality.
183
184// Returns the same expression with positive variables.
186
187// Returns the coefficient of the variable in the expression. Works in linear
188// time.
189// Note: GetCoefficient(NegationOf(var, expr)) == -GetCoefficient(var, expr).
190IntegerValue GetCoefficient(IntegerVariable var, const LinearExpression& expr);
191IntegerValue GetCoefficientOfPositiveVar(IntegerVariable var,
192 const LinearExpression& expr);
193
194// Allow to build a LinearConstraint while making sure there is no duplicate
195// variables. Note that we do not simplify literal/variable that are currently
196// fixed here.
197//
198// All the functions manipulate a linear expression with an offset. The final
199// constraint bounds will include this offset.
200//
201// TODO(user): Rename to LinearExpressionBuilder?
203 public:
204 // We support "sticky" kMinIntegerValue for lb and kMaxIntegerValue for ub
205 // for one-sided constraints.
206 //
207 // Assumes that the 'model' has IntegerEncoder. The bounds can either be
208 // specified at construction or during the Build() call.
209 explicit LinearConstraintBuilder(const Model* model)
210 : encoder_(model->Get<IntegerEncoder>()), lb_(0), ub_(0) {}
212 : encoder_(encoder), lb_(0), ub_(0) {}
213 LinearConstraintBuilder(const Model* model, IntegerValue lb, IntegerValue ub)
214 : encoder_(model->Get<IntegerEncoder>()), lb_(lb), ub_(ub) {}
215 LinearConstraintBuilder(IntegerEncoder* encoder, IntegerValue lb,
216 IntegerValue ub)
217 : encoder_(encoder), lb_(lb), ub_(ub) {}
218
219 // Warning: this version without encoder cannot be used to add literals, so
220 // one shouldn't call AddLiteralTerm() on it. All other functions works.
221 //
222 // TODO(user): Have a subclass so we can enforce that a caller using
223 // AddLiteralTerm() must construct the Builder with an encoder.
224 LinearConstraintBuilder() : encoder_(nullptr), lb_(0), ub_(0) {}
225 LinearConstraintBuilder(IntegerValue lb, IntegerValue ub)
226 : encoder_(nullptr), lb_(lb), ub_(ub) {}
227
228 // Adds the corresponding term to the current linear expression.
229 void AddConstant(IntegerValue value);
230 void AddTerm(IntegerVariable var, IntegerValue coeff);
231 void AddTerm(AffineExpression expr, IntegerValue coeff);
232 void AddLinearExpression(const LinearExpression& expr);
233 void AddLinearExpression(const LinearExpression& expr, IntegerValue coeff);
234
235 // Add the corresponding decomposed products (obtained from
236 // TryToDecomposeProduct). The code assumes all literals to be in an
237 // exactly_one relation.
238 // It returns false if one literal does not have an integer view, as it
239 // actually calls AddLiteralTerm().
240 ABSL_MUST_USE_RESULT bool AddDecomposedProduct(
241 absl::Span<const LiteralValueValue> product);
242
243 // Add literal * coeff to the constraint. Returns false and do nothing if the
244 // given literal didn't have an integer view.
245 ABSL_MUST_USE_RESULT bool AddLiteralTerm(
246 Literal lit, IntegerValue coeff = IntegerValue(1));
247
248 // Add an under linearization of the product of two affine expressions.
249 // If at least one of them is fixed, then we add the exact product (which is
250 // linear). Otherwise, we use McCormick relaxation:
251 // left * right = (left_min + delta_left) * (right_min + delta_right) =
252 // left_min * right_min + delta_left * right_min +
253 // delta_right * left_min + delta_left * delta_right
254 // which is >= (by ignoring the quatratic term)
255 // right_min * left + left_min * right - right_min * left_min
256 //
257 // TODO(user): We could use (max - delta) instead of (min + delta) for each
258 // expression instead. This would depend on the LP value of the left and
259 // right.
261 IntegerTrail* integer_trail,
262 bool* is_quadratic = nullptr);
263
264 // Clears all added terms and constants. Keeps the original bounds.
265 void Clear() {
266 offset_ = IntegerValue(0);
267 terms_.clear();
268 }
269
270 // Reset the bounds passed at construction time.
271 void ResetBounds(IntegerValue lb, IntegerValue ub) {
272 lb_ = lb;
273 ub_ = ub;
274 }
275
276 // Builds and returns the corresponding constraint in a canonical form.
277 // All the IntegerVariable will be positive and appear in increasing index
278 // order.
279 //
280 // The bounds can be changed here or taken at construction.
281 //
282 // TODO(user): this doesn't invalidate the builder object, but if one wants
283 // to do a lot of dynamic editing to the constraint, then then underlying
284 // algorithm needs to be optimized for that.
286 LinearConstraint BuildConstraint(IntegerValue lb, IntegerValue ub);
287
288 // Similar to BuildConstraint() but make sure we don't overflow while we merge
289 // terms referring to the same variables.
290 bool BuildIntoConstraintAndCheckOverflow(IntegerValue lb, IntegerValue ub,
291 LinearConstraint* ct);
292
293 // Returns the linear expression part of the constraint only, without the
294 // bounds.
296
297 int NumTerms() const { return terms_.size(); }
298
299 private:
300 const IntegerEncoder* encoder_;
301 IntegerValue lb_;
302 IntegerValue ub_;
303
304 IntegerValue offset_ = IntegerValue(0);
305
306 // Initially we push all AddTerm() here, and during Build() we merge terms
307 // on the same variable.
308 std::vector<std::pair<IntegerVariable, IntegerValue>> terms_;
309};
310
311// Returns the activity of the given constraint. That is the current value of
312// the linear terms.
313double ComputeActivity(
314 const LinearConstraint& constraint,
316
317// Tests for possible overflow in the given linear constraint used for the
318// linear relaxation. This is a bit relaxed compared to what we require for
319// generic linear constraint that are used in our CP propagators.
320//
321// If this check pass, our constraint should be safe to use in our
322// simplification code, our cut computation, etc...
323bool PossibleOverflow(const IntegerTrail& integer_trail,
324 const LinearConstraint& constraint);
325
326// Returns sqrt(sum square(coeff)).
327double ComputeL2Norm(const LinearConstraint& constraint);
328
329// Returns the maximum absolute value of the coefficients.
330IntegerValue ComputeInfinityNorm(const LinearConstraint& constraint);
331
332// Returns the scalar product of given constraint coefficients. This method
333// assumes that the constraint variables are in sorted order.
334double ScalarProduct(const LinearConstraint& constraint1,
335 const LinearConstraint& constraint2);
336
337// Computes the GCD of the constraint coefficient, and divide them by it. This
338// also tighten the constraint bounds assuming all the variables are integer.
339void DivideByGCD(LinearConstraint* constraint);
340
341// Removes the entries with a coefficient of zero.
342void RemoveZeroTerms(LinearConstraint* constraint);
343
344// Makes all coefficients positive by transforming a variable to its negation.
345void MakeAllCoefficientsPositive(LinearConstraint* constraint);
346
347// Makes all variables "positive" by transforming a variable to its negation.
348void MakeAllVariablesPositive(LinearConstraint* constraint);
349
350// Returns false if duplicate variables are found in ct.
351bool NoDuplicateVariable(const LinearConstraint& ct);
352
353// Sorts and merges duplicate IntegerVariable in the given "terms".
354// Fills the given LinearConstraint or LinearExpression with the result.
356 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
357 LinearExpression* output) {
358 output->vars.clear();
359 output->coeffs.clear();
360
361 // Sort and add coeff of duplicate variables. Note that a variable and
362 // its negation will appear one after another in the natural order.
363 std::sort(terms->begin(), terms->end());
364 IntegerVariable previous_var = kNoIntegerVariable;
365 IntegerValue current_coeff(0);
366 for (const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
367 if (previous_var == entry.first) {
368 current_coeff += entry.second;
369 } else if (previous_var == NegationOf(entry.first)) {
370 current_coeff -= entry.second;
371 } else {
372 if (current_coeff != 0) {
373 output->vars.push_back(previous_var);
374 output->coeffs.push_back(current_coeff);
375 }
376 previous_var = entry.first;
377 current_coeff = entry.second;
378 }
379 }
380 if (current_coeff != 0) {
381 output->vars.push_back(previous_var);
382 output->coeffs.push_back(current_coeff);
383 }
384}
385
387 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
388 LinearConstraint* output) {
389 // Sort and add coeff of duplicate variables. Note that a variable and
390 // its negation will appear one after another in the natural order.
391 int new_size = 0;
392 output->resize(terms->size());
393 std::sort(terms->begin(), terms->end());
394 IntegerVariable previous_var = kNoIntegerVariable;
395 IntegerValue current_coeff(0);
396 for (const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
397 if (previous_var == entry.first) {
398 current_coeff += entry.second;
399 } else if (previous_var == NegationOf(entry.first)) {
400 current_coeff -= entry.second;
401 } else {
402 if (current_coeff != 0) {
403 output->vars[new_size] = previous_var;
404 output->coeffs[new_size] = current_coeff;
405 ++new_size;
406 }
407 previous_var = entry.first;
408 current_coeff = entry.second;
409 }
410 }
411 if (current_coeff != 0) {
412 output->vars[new_size] = previous_var;
413 output->coeffs[new_size] = current_coeff;
414 ++new_size;
415 }
416 output->resize(new_size);
417}
418
420 std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
421 LinearConstraint* output) {
422 // Sort and add coeff of duplicate variables. Note that a variable and
423 // its negation will appear one after another in the natural order.
424 int new_size = 0;
425 output->resize(terms->size());
426 std::sort(terms->begin(), terms->end());
427 IntegerVariable previous_var = kNoIntegerVariable;
428 int64_t current_coeff = 0;
429 for (const std::pair<IntegerVariable, IntegerValue>& entry : *terms) {
430 DCHECK(VariableIsPositive(entry.first));
431 if (previous_var == entry.first) {
432 if (AddIntoOverflow(entry.second.value(), &current_coeff)) {
433 return false;
434 }
435 } else {
436 if (current_coeff != 0) {
437 output->vars[new_size] = previous_var;
438 output->coeffs[new_size] = current_coeff;
439 ++new_size;
440 }
441 previous_var = entry.first;
442 current_coeff = entry.second.value();
443 }
444 }
445 if (current_coeff != 0) {
446 output->vars[new_size] = previous_var;
447 output->coeffs[new_size] = current_coeff;
448 ++new_size;
449 }
450 output->resize(new_size);
451 return true;
452}
453
454} // namespace sat
455} // namespace operations_research
456
457#endif // OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
void AddQuadraticLowerBound(AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff=IntegerValue(1))
void ResetBounds(IntegerValue lb, IntegerValue ub)
Reset the bounds passed at construction time.
LinearConstraintBuilder(IntegerEncoder *encoder, IntegerValue lb, IntegerValue ub)
void AddTerm(IntegerVariable var, IntegerValue coeff)
void AddLinearExpression(const LinearExpression &expr)
void AddConstant(IntegerValue value)
Adds the corresponding term to the current linear expression.
void Clear()
Clears all added terms and constants. Keeps the original bounds.
LinearConstraintBuilder(const Model *model, IntegerValue lb, IntegerValue ub)
LinearConstraint BuildConstraint(IntegerValue lb, IntegerValue ub)
LinearConstraintBuilder(IntegerValue lb, IntegerValue ub)
bool BuildIntoConstraintAndCheckOverflow(IntegerValue lb, IntegerValue ub, LinearConstraint *ct)
ABSL_MUST_USE_RESULT bool AddDecomposedProduct(absl::Span< const LiteralValueValue > product)
double ComputeActivity(const LinearConstraint &constraint, const util_intops::StrongVector< IntegerVariable, double > &values)
void DivideByGCD(LinearConstraint *constraint)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
double ComputeL2Norm(const LinearConstraint &ct)
Returns sqrt(sum square(coeff)).
void RemoveZeroTerms(LinearConstraint *constraint)
Removes the entries with a coefficient of zero.
IntegerValue ComputeInfinityNorm(const LinearConstraint &ct)
Returns the maximum absolute value of the coefficients.
std::string IntegerTermDebugString(IntegerVariable var, IntegerValue coeff)
std::vector< IntegerVariable > NegationOf(absl::Span< const IntegerVariable > vars)
Returns the vector of the negated variables.
Definition integer.cc:52
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
const IntegerVariable kNoIntegerVariable(-1)
bool PossibleOverflow(const IntegerTrail &integer_trail, const LinearConstraint &constraint)
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearExpression *output)
void MakeAllCoefficientsPositive(LinearConstraint *constraint)
Makes all coefficients positive by transforming a variable to its negation.
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
Definition cp_model.cc:89
LinearExpression CanonicalizeExpr(const LinearExpression &expr)
bool MergePositiveVariableTermsAndCheckForOverflow(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearConstraint *output)
LinearExpression PositiveVarExpr(const LinearExpression &expr)
Returns the same expression with positive variables.
IntegerValue GetCoefficient(const IntegerVariable var, const LinearExpression &expr)
void MakeAllVariablesPositive(LinearConstraint *constraint)
Makes all variables "positive" by transforming a variable to its negation.
IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var, const LinearExpression &expr)
bool ValidateLinearConstraintForOverflow(const LinearConstraint &constraint, const IntegerTrail &integer_trail)
bool NoDuplicateVariable(const LinearConstraint &ct)
Returns false if duplicate variables are found in ct.
bool VariableIsPositive(IntegerVariable i)
double ScalarProduct(const LinearConstraint &ct1, const LinearConstraint &ct2)
In SWIG mode, we don't want anything besides these top-level includes.
bool AddIntoOverflow(int64_t x, int64_t *y)
std::unique_ptr< IntegerValue[]> coeffs
std::unique_ptr< IntegerVariable[]> vars
absl::Span< const IntegerValue > CoeffsAsSpan() const
absl::Span< const IntegerVariable > VarsAsSpan() const
bool IsEqualIgnoringBounds(const LinearConstraint &other) const
bool operator==(const LinearConstraint &other) const
LinearConstraint(IntegerValue _lb, IntegerValue _ub)
double NormalizedViolation(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const
IntegerValue LevelZeroMin(IntegerTrail *integer_trail) const
IntegerValue Min(const IntegerTrail &integer_trail) const
double LpValue(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const
Return[s] the evaluation of the linear expression.
IntegerValue Max(const IntegerTrail &integer_trail) const