OR-Tools  8.2
cp_model_utils.cc
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
15
17
18namespace operations_research {
19namespace sat {
20
21namespace {
22
23template <typename IntList>
24void AddIndices(const IntList& indices, std::vector<int>* output) {
25 output->insert(output->end(), indices.begin(), indices.end());
26}
27
28} // namespace
29
30void SetToNegatedLinearExpression(const LinearExpressionProto& input_expr,
31 LinearExpressionProto* output_negated_expr) {
32 output_negated_expr->Clear();
33 for (int i = 0; i < input_expr.vars_size(); ++i) {
34 output_negated_expr->add_vars(NegatedRef(input_expr.vars(i)));
35 output_negated_expr->add_coeffs(input_expr.coeffs(i));
36 }
37 output_negated_expr->set_offset(-input_expr.offset());
38}
39
41 IndexReferences output;
42 switch (ct.constraint_case()) {
43 case ConstraintProto::ConstraintCase::kBoolOr:
44 AddIndices(ct.bool_or().literals(), &output.literals);
45 break;
46 case ConstraintProto::ConstraintCase::kBoolAnd:
47 AddIndices(ct.bool_and().literals(), &output.literals);
48 break;
49 case ConstraintProto::ConstraintCase::kAtMostOne:
50 AddIndices(ct.at_most_one().literals(), &output.literals);
51 break;
52 case ConstraintProto::ConstraintCase::kExactlyOne:
53 AddIndices(ct.exactly_one().literals(), &output.literals);
54 break;
55 case ConstraintProto::ConstraintCase::kBoolXor:
56 AddIndices(ct.bool_xor().literals(), &output.literals);
57 break;
58 case ConstraintProto::ConstraintCase::kIntDiv:
59 output.variables.push_back(ct.int_div().target());
60 AddIndices(ct.int_div().vars(), &output.variables);
61 break;
62 case ConstraintProto::ConstraintCase::kIntMod:
63 output.variables.push_back(ct.int_mod().target());
64 AddIndices(ct.int_mod().vars(), &output.variables);
65 break;
66 case ConstraintProto::ConstraintCase::kIntMax:
67 output.variables.push_back(ct.int_max().target());
68 AddIndices(ct.int_max().vars(), &output.variables);
69 break;
70 case ConstraintProto::ConstraintCase::kLinMax: {
71 AddIndices(ct.lin_max().target().vars(), &output.variables);
72 for (int i = 0; i < ct.lin_max().exprs_size(); ++i) {
73 AddIndices(ct.lin_max().exprs(i).vars(), &output.variables);
74 }
75 break;
76 }
77 case ConstraintProto::ConstraintCase::kIntMin:
78 output.variables.push_back(ct.int_min().target());
79 AddIndices(ct.int_min().vars(), &output.variables);
80 break;
81 case ConstraintProto::ConstraintCase::kLinMin: {
82 AddIndices(ct.lin_min().target().vars(), &output.variables);
83 for (int i = 0; i < ct.lin_min().exprs_size(); ++i) {
84 AddIndices(ct.lin_min().exprs(i).vars(), &output.variables);
85 }
86 break;
87 }
88 case ConstraintProto::ConstraintCase::kIntProd:
89 output.variables.push_back(ct.int_prod().target());
90 AddIndices(ct.int_prod().vars(), &output.variables);
91 break;
92 case ConstraintProto::ConstraintCase::kLinear:
93 AddIndices(ct.linear().vars(), &output.variables);
94 break;
95 case ConstraintProto::ConstraintCase::kAllDiff:
96 AddIndices(ct.all_diff().vars(), &output.variables);
97 break;
98 case ConstraintProto::ConstraintCase::kElement:
99 output.variables.push_back(ct.element().index());
100 output.variables.push_back(ct.element().target());
101 AddIndices(ct.element().vars(), &output.variables);
102 break;
103 case ConstraintProto::ConstraintCase::kCircuit:
104 AddIndices(ct.circuit().literals(), &output.literals);
105 break;
106 case ConstraintProto::ConstraintCase::kRoutes:
107 AddIndices(ct.routes().literals(), &output.literals);
108 break;
109 case ConstraintProto::ConstraintCase::kInverse:
110 AddIndices(ct.inverse().f_direct(), &output.variables);
111 AddIndices(ct.inverse().f_inverse(), &output.variables);
112 break;
113 case ConstraintProto::ConstraintCase::kReservoir:
114 AddIndices(ct.reservoir().times(), &output.variables);
115 AddIndices(ct.reservoir().actives(), &output.literals);
116 break;
117 case ConstraintProto::ConstraintCase::kTable:
118 AddIndices(ct.table().vars(), &output.variables);
119 break;
120 case ConstraintProto::ConstraintCase::kAutomaton:
121 AddIndices(ct.automaton().vars(), &output.variables);
122 break;
123 case ConstraintProto::ConstraintCase::kInterval:
124 if (ct.interval().has_start_view()) {
125 AddIndices(ct.interval().start_view().vars(), &output.variables);
126 } else {
127 output.variables.push_back(ct.interval().start());
128 }
129 if (ct.interval().has_size_view()) {
130 AddIndices(ct.interval().size_view().vars(), &output.variables);
131 } else {
132 output.variables.push_back(ct.interval().size());
133 }
134 if (ct.interval().has_end_view()) {
135 AddIndices(ct.interval().end_view().vars(), &output.variables);
136 } else {
137 output.variables.push_back(ct.interval().end());
138 }
139 break;
140 case ConstraintProto::ConstraintCase::kNoOverlap:
141 break;
142 case ConstraintProto::ConstraintCase::kNoOverlap2D:
143 break;
144 case ConstraintProto::ConstraintCase::kCumulative:
145 output.variables.push_back(ct.cumulative().capacity());
146 AddIndices(ct.cumulative().demands(), &output.variables);
147 break;
148 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
149 break;
150 }
151 return output;
152}
153
154#define APPLY_TO_SINGULAR_FIELD(ct_name, field_name) \
155 { \
156 int temp = ct->mutable_##ct_name()->field_name(); \
157 f(&temp); \
158 ct->mutable_##ct_name()->set_##field_name(temp); \
159 }
160
161#define APPLY_TO_REPEATED_FIELD(ct_name, field_name) \
162 { \
163 for (int& r : *ct->mutable_##ct_name()->mutable_##field_name()) f(&r); \
164 }
165
166void ApplyToAllLiteralIndices(const std::function<void(int*)>& f,
167 ConstraintProto* ct) {
168 for (int& r : *ct->mutable_enforcement_literal()) f(&r);
169 switch (ct->constraint_case()) {
170 case ConstraintProto::ConstraintCase::kBoolOr:
171 APPLY_TO_REPEATED_FIELD(bool_or, literals);
172 break;
173 case ConstraintProto::ConstraintCase::kBoolAnd:
174 APPLY_TO_REPEATED_FIELD(bool_and, literals);
175 break;
176 case ConstraintProto::ConstraintCase::kAtMostOne:
177 APPLY_TO_REPEATED_FIELD(at_most_one, literals);
178 break;
179 case ConstraintProto::ConstraintCase::kExactlyOne:
180 APPLY_TO_REPEATED_FIELD(exactly_one, literals);
181 break;
182 case ConstraintProto::ConstraintCase::kBoolXor:
183 APPLY_TO_REPEATED_FIELD(bool_xor, literals);
184 break;
185 case ConstraintProto::ConstraintCase::kIntDiv:
186 break;
187 case ConstraintProto::ConstraintCase::kIntMod:
188 break;
189 case ConstraintProto::ConstraintCase::kIntMax:
190 break;
191 case ConstraintProto::ConstraintCase::kLinMax:
192 break;
193 case ConstraintProto::ConstraintCase::kIntMin:
194 break;
195 case ConstraintProto::ConstraintCase::kLinMin:
196 break;
197 case ConstraintProto::ConstraintCase::kIntProd:
198 break;
199 case ConstraintProto::ConstraintCase::kLinear:
200 break;
201 case ConstraintProto::ConstraintCase::kAllDiff:
202 break;
203 case ConstraintProto::ConstraintCase::kElement:
204 break;
205 case ConstraintProto::ConstraintCase::kCircuit:
206 APPLY_TO_REPEATED_FIELD(circuit, literals);
207 break;
208 case ConstraintProto::ConstraintCase::kRoutes:
209 APPLY_TO_REPEATED_FIELD(routes, literals);
210 break;
211 case ConstraintProto::ConstraintCase::kInverse:
212 break;
213 case ConstraintProto::ConstraintCase::kReservoir:
214 APPLY_TO_REPEATED_FIELD(reservoir, actives);
215 break;
216 case ConstraintProto::ConstraintCase::kTable:
217 break;
218 case ConstraintProto::ConstraintCase::kAutomaton:
219 break;
220 case ConstraintProto::ConstraintCase::kInterval:
221 break;
222 case ConstraintProto::ConstraintCase::kNoOverlap:
223 break;
224 case ConstraintProto::ConstraintCase::kNoOverlap2D:
225 break;
226 case ConstraintProto::ConstraintCase::kCumulative:
227 break;
228 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
229 break;
230 }
231}
232
233void ApplyToAllVariableIndices(const std::function<void(int*)>& f,
234 ConstraintProto* ct) {
235 switch (ct->constraint_case()) {
236 case ConstraintProto::ConstraintCase::kBoolOr:
237 break;
238 case ConstraintProto::ConstraintCase::kBoolAnd:
239 break;
240 case ConstraintProto::ConstraintCase::kAtMostOne:
241 break;
242 case ConstraintProto::ConstraintCase::kExactlyOne:
243 break;
244 case ConstraintProto::ConstraintCase::kBoolXor:
245 break;
246 case ConstraintProto::ConstraintCase::kIntDiv:
247 APPLY_TO_SINGULAR_FIELD(int_div, target);
248 APPLY_TO_REPEATED_FIELD(int_div, vars);
249 break;
250 case ConstraintProto::ConstraintCase::kIntMod:
251 APPLY_TO_SINGULAR_FIELD(int_mod, target);
252 APPLY_TO_REPEATED_FIELD(int_mod, vars);
253 break;
254 case ConstraintProto::ConstraintCase::kIntMax:
255 APPLY_TO_SINGULAR_FIELD(int_max, target);
256 APPLY_TO_REPEATED_FIELD(int_max, vars);
257 break;
258 case ConstraintProto::ConstraintCase::kLinMax:
259 APPLY_TO_REPEATED_FIELD(lin_max, target()->mutable_vars);
260 for (int i = 0; i < ct->lin_max().exprs_size(); ++i) {
261 APPLY_TO_REPEATED_FIELD(lin_max, exprs(i)->mutable_vars);
262 }
263 break;
264 case ConstraintProto::ConstraintCase::kIntMin:
265 APPLY_TO_SINGULAR_FIELD(int_min, target);
266 APPLY_TO_REPEATED_FIELD(int_min, vars);
267 break;
268 case ConstraintProto::ConstraintCase::kLinMin:
269 APPLY_TO_REPEATED_FIELD(lin_min, target()->mutable_vars);
270 for (int i = 0; i < ct->lin_min().exprs_size(); ++i) {
271 APPLY_TO_REPEATED_FIELD(lin_min, exprs(i)->mutable_vars);
272 }
273 break;
274 case ConstraintProto::ConstraintCase::kIntProd:
275 APPLY_TO_SINGULAR_FIELD(int_prod, target);
276 APPLY_TO_REPEATED_FIELD(int_prod, vars);
277 break;
278 case ConstraintProto::ConstraintCase::kLinear:
279 APPLY_TO_REPEATED_FIELD(linear, vars);
280 break;
281 case ConstraintProto::ConstraintCase::kAllDiff:
282 APPLY_TO_REPEATED_FIELD(all_diff, vars);
283 break;
284 case ConstraintProto::ConstraintCase::kElement:
286 APPLY_TO_SINGULAR_FIELD(element, target);
287 APPLY_TO_REPEATED_FIELD(element, vars);
288 break;
289 case ConstraintProto::ConstraintCase::kCircuit:
290 break;
291 case ConstraintProto::ConstraintCase::kRoutes:
292 break;
293 case ConstraintProto::ConstraintCase::kInverse:
294 APPLY_TO_REPEATED_FIELD(inverse, f_direct);
295 APPLY_TO_REPEATED_FIELD(inverse, f_inverse);
296 break;
297 case ConstraintProto::ConstraintCase::kReservoir:
298 APPLY_TO_REPEATED_FIELD(reservoir, times);
299 break;
300 case ConstraintProto::ConstraintCase::kTable:
301 APPLY_TO_REPEATED_FIELD(table, vars);
302 break;
303 case ConstraintProto::ConstraintCase::kAutomaton:
304 APPLY_TO_REPEATED_FIELD(automaton, vars);
305 break;
306 case ConstraintProto::ConstraintCase::kInterval:
307 if (ct->interval().has_start_view()) {
308 APPLY_TO_REPEATED_FIELD(interval, start_view()->mutable_vars);
309 } else {
311 }
312 if (ct->interval().has_size_view()) {
313 APPLY_TO_REPEATED_FIELD(interval, size_view()->mutable_vars);
314 } else {
316 }
317 if (ct->interval().has_end_view()) {
318 APPLY_TO_REPEATED_FIELD(interval, end_view()->mutable_vars);
319 } else {
321 }
322 break;
323 case ConstraintProto::ConstraintCase::kNoOverlap:
324 break;
325 case ConstraintProto::ConstraintCase::kNoOverlap2D:
326 break;
327 case ConstraintProto::ConstraintCase::kCumulative:
329 APPLY_TO_REPEATED_FIELD(cumulative, demands);
330 break;
331 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
332 break;
333 }
334}
335
336void ApplyToAllIntervalIndices(const std::function<void(int*)>& f,
337 ConstraintProto* ct) {
338 switch (ct->constraint_case()) {
339 case ConstraintProto::ConstraintCase::kBoolOr:
340 break;
341 case ConstraintProto::ConstraintCase::kBoolAnd:
342 break;
343 case ConstraintProto::ConstraintCase::kAtMostOne:
344 break;
345 case ConstraintProto::ConstraintCase::kExactlyOne:
346 break;
347 case ConstraintProto::ConstraintCase::kBoolXor:
348 break;
349 case ConstraintProto::ConstraintCase::kIntDiv:
350 break;
351 case ConstraintProto::ConstraintCase::kIntMod:
352 break;
353 case ConstraintProto::ConstraintCase::kIntMax:
354 break;
355 case ConstraintProto::ConstraintCase::kLinMax:
356 break;
357 case ConstraintProto::ConstraintCase::kIntMin:
358 break;
359 case ConstraintProto::ConstraintCase::kLinMin:
360 break;
361 case ConstraintProto::ConstraintCase::kIntProd:
362 break;
363 case ConstraintProto::ConstraintCase::kLinear:
364 break;
365 case ConstraintProto::ConstraintCase::kAllDiff:
366 break;
367 case ConstraintProto::ConstraintCase::kElement:
368 break;
369 case ConstraintProto::ConstraintCase::kCircuit:
370 break;
371 case ConstraintProto::ConstraintCase::kRoutes:
372 break;
373 case ConstraintProto::ConstraintCase::kInverse:
374 break;
375 case ConstraintProto::ConstraintCase::kReservoir:
376 break;
377 case ConstraintProto::ConstraintCase::kTable:
378 break;
379 case ConstraintProto::ConstraintCase::kAutomaton:
380 break;
381 case ConstraintProto::ConstraintCase::kInterval:
382 break;
383 case ConstraintProto::ConstraintCase::kNoOverlap:
384 APPLY_TO_REPEATED_FIELD(no_overlap, intervals);
385 break;
386 case ConstraintProto::ConstraintCase::kNoOverlap2D:
387 APPLY_TO_REPEATED_FIELD(no_overlap_2d, x_intervals);
388 APPLY_TO_REPEATED_FIELD(no_overlap_2d, y_intervals);
389 break;
390 case ConstraintProto::ConstraintCase::kCumulative:
391 APPLY_TO_REPEATED_FIELD(cumulative, intervals);
392 break;
393 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
394 break;
395 }
396}
397
398#undef APPLY_TO_SINGULAR_FIELD
399#undef APPLY_TO_REPEATED_FIELD
400
402 ConstraintProto::ConstraintCase constraint_case) {
403 switch (constraint_case) {
404 case ConstraintProto::ConstraintCase::kBoolOr:
405 return "kBoolOr";
406 case ConstraintProto::ConstraintCase::kBoolAnd:
407 return "kBoolAnd";
408 case ConstraintProto::ConstraintCase::kAtMostOne:
409 return "kAtMostOne";
410 case ConstraintProto::ConstraintCase::kExactlyOne:
411 return "kExactlyOne";
412 case ConstraintProto::ConstraintCase::kBoolXor:
413 return "kBoolXor";
414 case ConstraintProto::ConstraintCase::kIntDiv:
415 return "kIntDiv";
416 case ConstraintProto::ConstraintCase::kIntMod:
417 return "kIntMod";
418 case ConstraintProto::ConstraintCase::kIntMax:
419 return "kIntMax";
420 case ConstraintProto::ConstraintCase::kLinMax:
421 return "kLinMax";
422 case ConstraintProto::ConstraintCase::kIntMin:
423 return "kIntMin";
424 case ConstraintProto::ConstraintCase::kLinMin:
425 return "kLinMin";
426 case ConstraintProto::ConstraintCase::kIntProd:
427 return "kIntProd";
428 case ConstraintProto::ConstraintCase::kLinear:
429 return "kLinear";
430 case ConstraintProto::ConstraintCase::kAllDiff:
431 return "kAllDiff";
432 case ConstraintProto::ConstraintCase::kElement:
433 return "kElement";
434 case ConstraintProto::ConstraintCase::kCircuit:
435 return "kCircuit";
436 case ConstraintProto::ConstraintCase::kRoutes:
437 return "kRoutes";
438 case ConstraintProto::ConstraintCase::kInverse:
439 return "kInverse";
440 case ConstraintProto::ConstraintCase::kReservoir:
441 return "kReservoir";
442 case ConstraintProto::ConstraintCase::kTable:
443 return "kTable";
444 case ConstraintProto::ConstraintCase::kAutomaton:
445 return "kAutomaton";
446 case ConstraintProto::ConstraintCase::kInterval:
447 return "kInterval";
448 case ConstraintProto::ConstraintCase::kNoOverlap:
449 return "kNoOverlap";
450 case ConstraintProto::ConstraintCase::kNoOverlap2D:
451 return "kNoOverlap2D";
452 case ConstraintProto::ConstraintCase::kCumulative:
453 return "kCumulative";
454 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
455 return "kEmpty";
456 }
457}
458
459std::vector<int> UsedVariables(const ConstraintProto& ct) {
461 for (int& ref : references.variables) {
462 ref = PositiveRef(ref);
463 }
464 for (const int lit : references.literals) {
465 references.variables.push_back(PositiveRef(lit));
466 }
467 for (const int lit : ct.enforcement_literal()) {
468 references.variables.push_back(PositiveRef(lit));
469 }
471 return references.variables;
472}
473
474std::vector<int> UsedIntervals(const ConstraintProto& ct) {
475 std::vector<int> used_intervals;
476 switch (ct.constraint_case()) {
477 case ConstraintProto::ConstraintCase::kBoolOr:
478 break;
479 case ConstraintProto::ConstraintCase::kBoolAnd:
480 break;
481 case ConstraintProto::ConstraintCase::kAtMostOne:
482 break;
483 case ConstraintProto::ConstraintCase::kExactlyOne:
484 break;
485 case ConstraintProto::ConstraintCase::kBoolXor:
486 break;
487 case ConstraintProto::ConstraintCase::kIntDiv:
488 break;
489 case ConstraintProto::ConstraintCase::kIntMod:
490 break;
491 case ConstraintProto::ConstraintCase::kIntMax:
492 break;
493 case ConstraintProto::ConstraintCase::kLinMax:
494 break;
495 case ConstraintProto::ConstraintCase::kIntMin:
496 break;
497 case ConstraintProto::ConstraintCase::kLinMin:
498 break;
499 case ConstraintProto::ConstraintCase::kIntProd:
500 break;
501 case ConstraintProto::ConstraintCase::kLinear:
502 break;
503 case ConstraintProto::ConstraintCase::kAllDiff:
504 break;
505 case ConstraintProto::ConstraintCase::kElement:
506 break;
507 case ConstraintProto::ConstraintCase::kCircuit:
508 break;
509 case ConstraintProto::ConstraintCase::kRoutes:
510 break;
511 case ConstraintProto::ConstraintCase::kInverse:
512 break;
513 case ConstraintProto::ConstraintCase::kReservoir:
514 break;
515 case ConstraintProto::ConstraintCase::kTable:
516 break;
517 case ConstraintProto::ConstraintCase::kAutomaton:
518 break;
519 case ConstraintProto::ConstraintCase::kInterval:
520 break;
521 case ConstraintProto::ConstraintCase::kNoOverlap:
522 AddIndices(ct.no_overlap().intervals(), &used_intervals);
523 break;
524 case ConstraintProto::ConstraintCase::kNoOverlap2D:
525 AddIndices(ct.no_overlap_2d().x_intervals(), &used_intervals);
526 AddIndices(ct.no_overlap_2d().y_intervals(), &used_intervals);
527 break;
528 case ConstraintProto::ConstraintCase::kCumulative:
529 AddIndices(ct.cumulative().intervals(), &used_intervals);
530 break;
531 case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
532 break;
533 }
534 gtl::STLSortAndRemoveDuplicates(&used_intervals);
535 return used_intervals;
536}
537
538int64 ComputeInnerObjective(const CpObjectiveProto& objective,
539 const CpSolverResponse& response) {
540 int64 objective_value = 0;
541 auto& repeated_field_values = response.solution().empty()
542 ? response.solution_lower_bounds()
543 : response.solution();
544 for (int i = 0; i < objective.vars_size(); ++i) {
545 int64 coeff = objective.coeffs(i);
546 const int ref = objective.vars(i);
547 const int var = PositiveRef(ref);
548 if (!RefIsPositive(ref)) coeff = -coeff;
549 objective_value += coeff * repeated_field_values[var];
550 }
551 return objective_value;
552}
553
554} // namespace sat
555} // namespace operations_research
SharedResponseManager * response
#define APPLY_TO_SINGULAR_FIELD(ct_name, field_name)
#define APPLY_TO_REPEATED_FIELD(ct_name, field_name)
const Constraint * ct
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:58
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)
int64 ComputeInnerObjective(const CpObjectiveProto &objective, const CpSolverResponse &response)
void ApplyToAllLiteralIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void ApplyToAllIntervalIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
void ApplyToAllVariableIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)
std::string ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)
bool RefIsPositive(int ref)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
IntervalVar * interval
Definition: resource.cc:98
int64 capacity