OR-Tools  8.2
linear_constraint.h
Go to the documentation of this file.
1 // Copyright 2010-2018 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 <vector>
18 
20 #include "ortools/sat/integer.h"
21 #include "ortools/sat/model.h"
22 
23 namespace operations_research {
24 namespace sat {
25 
26 // One linear constraint on a set of Integer variables.
27 // Important: there should be no duplicate variables.
28 //
29 // We also assume that we never have integer overflow when evaluating such
30 // constraint. This should be enforced by the checker for user given
31 // constraints, and we must enforce it ourselves for the newly created
32 // constraint. We requires:
33 // - sum_i max(0, max(c_i * lb_i, c_i * ub_i)) < kMaxIntegerValue.
34 // - sum_i min(0, min(c_i * lb_i, c_i * ub_i)) > kMinIntegerValue
35 // so that in whichever order we compute the sum, we have no overflow. Note
36 // that this condition invoves the bounds of the variables.
37 //
38 // TODO(user): Add DCHECKs for the no-overflow property? but we need access
39 // to the variable bounds.
41  IntegerValue lb;
42  IntegerValue ub;
43  std::vector<IntegerVariable> vars;
44  std::vector<IntegerValue> coeffs;
45 
47  LinearConstraint(IntegerValue _lb, IntegerValue _ub) : lb(_lb), ub(_ub) {}
48 
49  void AddTerm(IntegerVariable var, IntegerValue coeff) {
50  vars.push_back(var);
51  coeffs.push_back(coeff);
52  }
53 
54  void ClearTerms() {
55  vars.clear();
56  coeffs.clear();
57  }
58 
59  std::string DebugString() const {
60  std::string result;
61  if (lb.value() > kMinIntegerValue) {
62  absl::StrAppend(&result, lb.value(), " <= ");
63  }
64  for (int i = 0; i < vars.size(); ++i) {
65  const IntegerValue coeff =
66  VariableIsPositive(vars[i]) ? coeffs[i] : -coeffs[i];
67  absl::StrAppend(&result, i > 0 ? " " : "", coeff.value(), "*X",
68  vars[i].value() / 2);
69  }
70  if (ub.value() < kMaxIntegerValue) {
71  absl::StrAppend(&result, " <= ", ub.value());
72  }
73  return result;
74  }
75 
76  bool operator==(const LinearConstraint other) const {
77  if (this->lb != other.lb) return false;
78  if (this->ub != other.ub) return false;
79  if (this->vars != other.vars) return false;
80  if (this->coeffs != other.coeffs) return false;
81  return true;
82  }
83 };
84 
85 // Allow to build a LinearConstraint while making sure there is no duplicate
86 // variables. Note that we do not simplify literal/variable that are currently
87 // fixed here.
89  public:
90  // We support "sticky" kMinIntegerValue for lb and kMaxIntegerValue for ub
91  // for one-sided constraints.
92  //
93  // Assumes that the 'model' has IntegerEncoder.
94  LinearConstraintBuilder(const Model* model, IntegerValue lb, IntegerValue ub)
95  : encoder_(*model->Get<IntegerEncoder>()), lb_(lb), ub_(ub) {}
96 
97  // Adds var * coeff to the constraint.
98  void AddTerm(IntegerVariable var, IntegerValue coeff);
99  void AddTerm(AffineExpression expr, IntegerValue coeff);
100 
101  // Add value as a constant term to the linear equation.
102  void AddConstant(IntegerValue value);
103 
104  // Add literal * coeff to the constaint. Returns false and do nothing if the
105  // given literal didn't have an integer view.
106  ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff);
107 
108  // Builds and return the corresponding constraint in a canonical form.
109  // All the IntegerVariable will be positive and appear in increasing index
110  // order.
111  //
112  // TODO(user): this doesn't invalidate the builder object, but if one wants
113  // to do a lot of dynamic editing to the constraint, then then underlying
114  // algorithm needs to be optimized of that.
116 
117  private:
118  const IntegerEncoder& encoder_;
119  IntegerValue lb_;
120  IntegerValue ub_;
121 
122  // Initially we push all AddTerm() here, and during Build() we merge terms
123  // on the same variable.
124  std::vector<std::pair<IntegerVariable, IntegerValue>> terms_;
125 };
126 
127 // Returns the activity of the given constraint. That is the current value of
128 // the linear terms.
129 double ComputeActivity(
130  const LinearConstraint& constraint,
132 
133 // Returns sqrt(sum square(coeff)).
134 double ComputeL2Norm(const LinearConstraint& constraint);
135 
136 // Returns the maximum absolute value of the coefficients.
137 IntegerValue ComputeInfinityNorm(const LinearConstraint& constraint);
138 
139 // Returns the scalar product of given constraint coefficients. This method
140 // assumes that the constraint variables are in sorted order.
141 double ScalarProduct(const LinearConstraint& constraint1,
142  const LinearConstraint& constraint2);
143 
144 // Computes the GCD of the constraint coefficient, and divide them by it. This
145 // also tighten the constraint bounds assumming all the variables are integer.
146 void DivideByGCD(LinearConstraint* constraint);
147 
148 // Removes the entries with a coefficient of zero.
149 void RemoveZeroTerms(LinearConstraint* constraint);
150 
151 // Makes all coefficients positive by transforming a variable to its negation.
152 void MakeAllCoefficientsPositive(LinearConstraint* constraint);
153 
154 // Makes all variables "positive" by transforming a variable to its negation.
155 void MakeAllVariablesPositive(LinearConstraint* constraint);
156 
157 // Sorts and merges duplicate IntegerVariable in the given "terms".
158 // Fills the given LinearConstraint with the result.
160  std::vector<std::pair<IntegerVariable, IntegerValue>>* terms,
161  LinearConstraint* constraint);
162 
163 // Sorts the terms and makes all IntegerVariable positive. This assumes that a
164 // variable or its negation only appear once.
165 //
166 // Note that currently this allocates some temporary memory.
167 void CanonicalizeConstraint(LinearConstraint* ct);
168 
169 // Returns false if duplicate variables are found in ct.
170 bool NoDuplicateVariable(const LinearConstraint& ct);
171 
172 // Helper struct to model linear expression for lin_min/lin_max constraints. The
173 // canonical expression should only contain positive coefficients.
175  std::vector<IntegerVariable> vars;
176  std::vector<IntegerValue> coeffs;
177  IntegerValue offset = IntegerValue(0);
178 };
179 
180 // Returns the same expression in the canonical form (all positive
181 // coefficients).
183 
184 // Returns lower bound of linear expression using variable bounds of the
185 // variables in expression. Assumes Canonical expression (all positive
186 // coefficients).
187 IntegerValue LinExprLowerBound(const LinearExpression& expr,
188  const IntegerTrail& integer_trail);
189 
190 // Returns upper bound of linear expression using variable bounds of the
191 // variables in expression. Assumes Canonical expression (all positive
192 // coefficients).
193 IntegerValue LinExprUpperBound(const LinearExpression& expr,
194  const IntegerTrail& integer_trail);
195 
196 // Preserves canonicality.
198 
199 // Returns the same expression with positive variables.
201 
202 // Returns the coefficient of the variable in the expression. Works in linear
203 // time.
204 // Note: GetCoefficient(NegationOf(var, expr)) == -GetCoefficient(var, expr).
205 IntegerValue GetCoefficient(const IntegerVariable var,
206  const LinearExpression& expr);
207 IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var,
208  const LinearExpression& expr);
209 
210 } // namespace sat
211 } // namespace operations_research
212 
213 #endif // OR_TOOLS_SAT_LINEAR_CONSTRAINT_H_
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff)
LinearConstraintBuilder(const Model *model, IntegerValue lb, IntegerValue ub)
void AddTerm(IntegerVariable var, IntegerValue coeff)
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
IntegerValue LinExprLowerBound(const LinearExpression &expr, const IntegerTrail &integer_trail)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
void RemoveZeroTerms(LinearConstraint *constraint)
LinearExpression PositiveVarExpr(const LinearExpression &expr)
double ScalarProduct(const LinearConstraint &constraint1, const LinearConstraint &constraint2)
void MakeAllCoefficientsPositive(LinearConstraint *constraint)
LinearExpression CanonicalizeExpr(const LinearExpression &expr)
void CanonicalizeConstraint(LinearConstraint *ct)
bool NoDuplicateVariable(const LinearConstraint &ct)
double ComputeL2Norm(const LinearConstraint &constraint)
IntegerValue GetCoefficient(const IntegerVariable var, const LinearExpression &expr)
void MakeAllVariablesPositive(LinearConstraint *constraint)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.cc:27
IntegerValue GetCoefficientOfPositiveVar(const IntegerVariable var, const LinearExpression &expr)
IntegerValue ComputeInfinityNorm(const LinearConstraint &constraint)
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue >> *terms, LinearConstraint *constraint)
IntegerValue LinExprUpperBound(const LinearExpression &expr, const IntegerTrail &integer_trail)
bool VariableIsPositive(IntegerVariable i)
Definition: integer.h:130
void DivideByGCD(LinearConstraint *constraint)
double ComputeActivity(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &values)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool operator==(const LinearConstraint other) const
std::vector< IntegerVariable > vars
LinearConstraint(IntegerValue _lb, IntegerValue _ub)
void AddTerm(IntegerVariable var, IntegerValue coeff)