Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model_mapping.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_CP_MODEL_MAPPING_H_
15#define OR_TOOLS_SAT_CP_MODEL_MAPPING_H_
16
17#include <cstdint>
18#include <utility>
19#include <vector>
20
21#include "absl/container/flat_hash_set.h"
22#include "absl/log/check.h"
27#include "ortools/sat/integer.h"
30#include "ortools/sat/model.h"
33
34namespace operations_research {
35namespace sat {
36
37// For an optimization problem, this contains the internal integer objective
38// to minimize and information on how to display it correctly in the logs.
40 double scaling_factor = 1.0;
41 double offset = 0.0;
43
44 // The objective linear expression that should be equal to objective_var.
45 // If not all proto variable have an IntegerVariable view, then some vars
46 // will be set to kNoIntegerVariable. In practice, when this is used, we make
47 // sure there is a view though.
48 std::vector<IntegerVariable> vars;
49 std::vector<IntegerValue> coeffs;
50
51 // List of variable that when set to their lower bound should help getting a
52 // better objective. This is used by some search heuristic to preferably
53 // assign any of the variable here to their lower bound first.
54 absl::flat_hash_set<IntegerVariable> objective_impacting_variables;
55
56 double ScaleIntegerObjective(IntegerValue value) const {
57 return (ToDouble(value) + offset) * scaling_factor;
58 }
59
60 double ScaleObjective(double value) const {
61 return (value + offset) * scaling_factor;
62 }
63};
64
65// Holds the mapping between CpModel proto indices and the sat::model ones.
66//
67// This also holds some information used when loading a CpModel proto.
69 public:
70 // Returns true if the given CpModelProto variable reference refers to a
71 // Boolean variable. Such variable will always have an associated Literal(),
72 // but not always an associated Integer().
73 bool IsBoolean(int ref) const {
74 DCHECK_LT(PositiveRef(ref), booleans_.size());
75 return booleans_[PositiveRef(ref)] != kNoBooleanVariable;
76 }
77
78 bool IsInteger(int ref) const {
79 DCHECK_LT(PositiveRef(ref), integers_.size());
80 return integers_[PositiveRef(ref)] != kNoIntegerVariable;
81 }
82
83 sat::Literal Literal(int ref) const {
84 DCHECK(IsBoolean(ref));
85 return sat::Literal(booleans_[PositiveRef(ref)], RefIsPositive(ref));
86 }
87
88 IntegerVariable Integer(int ref) const {
89 DCHECK(IsInteger(ref));
90 const IntegerVariable var = integers_[PositiveRef(ref)];
91 return RefIsPositive(ref) ? var : NegationOf(var);
92 }
93
94 // TODO(user): We could "easily" create an intermediate variable for more
95 // complex linear expression. We could also identify duplicate expressions to
96 // not create two identical integer variable.
98 CHECK_LE(exp.vars().size(), 1);
99 if (exp.vars().empty()) {
100 return AffineExpression(IntegerValue(exp.offset()));
101 }
102 return AffineExpression(Integer(exp.vars(0)), IntegerValue(exp.coeffs(0)),
103 IntegerValue(exp.offset()));
104 }
105
106 IntervalVariable Interval(int i) const {
107 CHECK_GE(i, 0);
108 CHECK_LT(i, intervals_.size());
109 CHECK_NE(intervals_[i], kNoIntervalVariable);
110 return intervals_[i];
111 }
112
113 template <typename List>
114 std::vector<IntegerVariable> Integers(const List& list) const {
115 std::vector<IntegerVariable> result;
116 result.reserve(list.size());
117 for (const auto i : list) result.push_back(Integer(i));
118 return result;
119 }
120
121 template <typename ProtoIndices>
122 std::vector<sat::Literal> Literals(const ProtoIndices& indices) const {
123 std::vector<sat::Literal> result;
124 result.reserve(indices.size());
125 for (const int i : indices) result.push_back(CpModelMapping::Literal(i));
126 return result;
127 }
128
129 template <typename List>
130 std::vector<AffineExpression> Affines(const List& list) const {
131 std::vector<AffineExpression> result;
132 result.reserve(list.size());
133 for (const auto& i : list) result.push_back(Affine(i));
134 return result;
135 }
136
137 template <typename ProtoIndices>
138 std::vector<IntervalVariable> Intervals(const ProtoIndices& indices) const {
139 std::vector<IntervalVariable> result;
140 result.reserve(indices.size());
141 for (const int i : indices) result.push_back(Interval(i));
142 return result;
143 }
144
145 // Depending on the option, we will load constraints in stages. This is used
146 // to detect constraints that are already loaded. For instance the interval
147 // constraints and the linear constraint of size 1 (encodings) are usually
148 // loaded first.
150 return already_loaded_ct_.contains(ct);
151 }
152
153 // Returns true if the given constraint is a "half-encoding" constraint. That
154 // is, if it is of the form (b => size 1 linear) but there is no (<=) side in
155 // the model. Such constraint are detected while we extract integer encoding
156 // and are cached here so that we can deal properly with them during the
157 // linear relaxation.
159 return is_half_encoding_ct_.contains(ct);
160 }
161
162 // Note that both these functions returns positive reference or -1.
163 int GetProtoVariableFromBooleanVariable(BooleanVariable var) const {
164 if (var.value() >= reverse_boolean_map_.size()) return -1;
165 return reverse_boolean_map_[var];
166 }
167 int GetProtoVariableFromIntegerVariable(IntegerVariable var) const {
168 if (var.value() >= reverse_integer_map_.size()) return -1;
169 return reverse_integer_map_[var];
170 }
171
172 // This one should only be used when we have a mapping.
174 const int proto_var = GetProtoVariableFromBooleanVariable(lit.Variable());
175 DCHECK_NE(proto_var, -1);
176 return lit.IsPositive() ? proto_var : NegatedRef(proto_var);
177 }
178
179 const std::vector<IntegerVariable>& GetVariableMapping() const {
180 return integers_;
181 }
182
184 const LinearExpressionProto& expr_proto) const {
185 LinearExpression expr;
186 expr.vars = Integers(expr_proto.vars());
187 for (int j = 0; j < expr_proto.coeffs_size(); ++j) {
188 expr.coeffs.push_back(IntegerValue(expr_proto.coeffs(j)));
189 }
190 expr.offset = IntegerValue(expr_proto.offset());
191 return CanonicalizeExpr(expr);
192 }
193
194 // Returns the min/max activity of the linear constraint under the current
195 // integer_trail bounds.
196 std::pair<int64_t, int64_t> ComputeMinMaxActivity(
197 const LinearConstraintProto& proto, IntegerTrail* integer_trail) {
198 int64_t sum_min = 0;
199 int64_t sum_max = 0;
200
201 for (int i = 0; i < proto.vars_size(); ++i) {
202 const int64_t coeff = proto.coeffs(i);
203 const IntegerVariable var = this->Integer(proto.vars(i));
204 const int64_t lb = integer_trail->LowerBound(var).value();
205 const int64_t ub = integer_trail->UpperBound(var).value();
206 if (coeff >= 0) {
207 sum_min += coeff * lb;
208 sum_max += coeff * ub;
209 } else {
210 sum_min += coeff * ub;
211 sum_max += coeff * lb;
212 }
213 }
214 return {sum_min, sum_max};
215 }
216
217 // For logging only, these are not super efficient.
219 int result = 0;
220 for (const IntegerVariable var : integers_) {
221 if (var != kNoIntegerVariable) result++;
222 }
223 return result;
224 }
226 int result = 0;
227 for (const BooleanVariable var : booleans_) {
228 if (var != kNoBooleanVariable) result++;
229 }
230 return result;
231 }
232
233 // Returns the number of variables in the loaded proto.
234 int NumProtoVariables() const { return integers_.size(); }
235
236 private:
237 friend void LoadVariables(const CpModelProto& model_proto,
238 bool view_all_booleans_as_integers, Model* m);
239 friend void ExtractEncoding(const CpModelProto& model_proto, Model* m);
240
241 // Note that only the variables used by at least one constraint will be
242 // created, the other will have a kNo[Integer,Interval,Boolean]VariableValue.
243 std::vector<IntegerVariable> integers_;
244 std::vector<IntervalVariable> intervals_;
245 std::vector<BooleanVariable> booleans_;
246
247 // Recover from a IntervalVariable/BooleanVariable its associated CpModelProto
248 // index. The value of -1 is used to indicate that there is no correspondence
249 // (i.e. this variable is only used internally).
252
253 // Set of constraints to ignore because they were already dealt with by
254 // ExtractEncoding().
255 absl::flat_hash_set<const ConstraintProto*> already_loaded_ct_;
256 absl::flat_hash_set<const ConstraintProto*> is_half_encoding_ct_;
257};
258
259} // namespace sat
260} // namespace operations_research
261
262#endif // OR_TOOLS_SAT_CP_MODEL_MAPPING_H_
friend void LoadVariables(const CpModelProto &model_proto, bool view_all_booleans_as_integers, Model *m)
int NumIntegerVariables() const
For logging only, these are not super efficient.
std::vector< IntegerVariable > Integers(const List &list) const
AffineExpression Affine(const LinearExpressionProto &exp) const
std::pair< int64_t, int64_t > ComputeMinMaxActivity(const LinearConstraintProto &proto, IntegerTrail *integer_trail)
int GetProtoVariableFromBooleanVariable(BooleanVariable var) const
int GetProtoLiteralFromLiteral(sat::Literal lit) const
This one should only be used when we have a mapping.
bool ConstraintIsAlreadyLoaded(const ConstraintProto *ct) const
bool IsHalfEncodingConstraint(const ConstraintProto *ct) const
std::vector< IntervalVariable > Intervals(const ProtoIndices &indices) const
int NumProtoVariables() const
Returns the number of variables in the loaded proto.
int GetProtoVariableFromIntegerVariable(IntegerVariable var) const
LinearExpression GetExprFromProto(const LinearExpressionProto &expr_proto) const
friend void ExtractEncoding(const CpModelProto &model_proto, Model *m)
std::vector< sat::Literal > Literals(const ProtoIndices &indices) const
std::vector< AffineExpression > Affines(const List &list) const
IntervalVariable Interval(int i) const
IntegerVariable Integer(int ref) const
const std::vector< IntegerVariable > & GetVariableMapping() const
IntegerValue LowerBound(IntegerVariable i) const
Returns the current lower/upper bound of the given integer variable.
Definition integer.h:1317
IntegerValue UpperBound(IntegerVariable i) const
Definition integer.h:1321
int vars_size() const
repeated int32 vars = 1;
int coeffs_size() const
repeated int64 coeffs = 2;
BooleanVariable Variable() const
Definition sat_base.h:87
std::vector< IntegerVariable > NegationOf(absl::Span< const IntegerVariable > vars)
Returns the vector of the negated variables.
Definition integer.cc:52
const IntegerVariable kNoIntegerVariable(-1)
const IntervalVariable kNoIntervalVariable(-1)
LinearExpression CanonicalizeExpr(const LinearExpression &expr)
const BooleanVariable kNoBooleanVariable(-1)
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
double ToDouble(IntegerValue value)
In SWIG mode, we don't want anything besides these top-level includes.
absl::flat_hash_set< IntegerVariable > objective_impacting_variables
double ScaleIntegerObjective(IntegerValue value) const