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