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
23namespace operations_research {
24namespace 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.
129double ComputeActivity(
130 const LinearConstraint& constraint,
132
133// Returns sqrt(sum square(coeff)).
134double ComputeL2Norm(const LinearConstraint& constraint);
135
136// Returns the maximum absolute value of the coefficients.
137IntegerValue 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.
141double 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.
146void DivideByGCD(LinearConstraint* constraint);
147
148// Removes the entries with a coefficient of zero.
149void RemoveZeroTerms(LinearConstraint* constraint);
150
151// Makes all coefficients positive by transforming a variable to its negation.
152void MakeAllCoefficientsPositive(LinearConstraint* constraint);
153
154// Makes all variables "positive" by transforming a variable to its negation.
155void 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.
167void CanonicalizeConstraint(LinearConstraint* ct);
168
169// Returns false if duplicate variables are found in ct.
170bool 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).
187IntegerValue 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).
193IntegerValue 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).
205IntegerValue GetCoefficient(const IntegerVariable var,
206 const LinearExpression& expr);
207IntegerValue 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
void CleanTermsAndFillConstraint(std::vector< std::pair< IntegerVariable, IntegerValue > > *terms, LinearConstraint *constraint)
bool VariableIsPositive(IntegerVariable i)
Definition: integer.h:130
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)
IntegerValue LinExprUpperBound(const LinearExpression &expr, const IntegerTrail &integer_trail)
void DivideByGCD(LinearConstraint *constraint)
double ComputeActivity(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &values)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
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)