OR-Tools  9.6
cp_model_utils.cc
Go to the documentation of this file.
1 // Copyright 2010-2022 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 #include "ortools/sat/cp_model_utils.h"
15 
16 #include <cstdint>
17 #include <cstdlib>
18 #include <functional>
19 #include <string>
20 #include <vector>
21 
22 #include "absl/container/flat_hash_map.h"
23 #include "ortools/base/logging.h"
24 #include "ortools/base/stl_util.h"
25 #include "ortools/sat/cp_model.pb.h"
26 #include "ortools/util/sorted_interval_list.h"
27 
28 namespace operations_research {
29 namespace sat {
30 
31 namespace {
32 
33 template <typename IntList>
34 void AddIndices(const IntList& indices, std::vector<int>* output) {
35  output->insert(output->end(), indices.begin(), indices.end());
36 }
37 
38 } // namespace
39 
40 void SetToNegatedLinearExpression(const LinearExpressionProto& input_expr,
41  LinearExpressionProto* output_negated_expr) {
42  output_negated_expr->Clear();
43  for (int i = 0; i < input_expr.vars_size(); ++i) {
44  output_negated_expr->add_vars(NegatedRef(input_expr.vars(i)));
45  output_negated_expr->add_coeffs(input_expr.coeffs(i));
46  }
47  output_negated_expr->set_offset(-input_expr.offset());
48 }
49 
50 IndexReferences GetReferencesUsedByConstraint(const ConstraintProto& ct) {
51  IndexReferences output;
52  switch (ct.constraint_case()) {
53  case ConstraintProto::ConstraintCase::kBoolOr:
54  AddIndices(ct.bool_or().literals(), &output.literals);
55  break;
56  case ConstraintProto::ConstraintCase::kBoolAnd:
57  AddIndices(ct.bool_and().literals(), &output.literals);
58  break;
59  case ConstraintProto::ConstraintCase::kAtMostOne:
60  AddIndices(ct.at_most_one().literals(), &output.literals);
61  break;
62  case ConstraintProto::ConstraintCase::kExactlyOne:
63  AddIndices(ct.exactly_one().literals(), &output.literals);
64  break;
65  case ConstraintProto::ConstraintCase::kBoolXor:
66  AddIndices(ct.bool_xor().literals(), &output.literals);
67  break;
68  case ConstraintProto::ConstraintCase::kIntDiv:
69  AddIndices(ct.int_div().target().vars(), &output.variables);
70  for (const LinearExpressionProto& expr : ct.int_div().exprs()) {
71  AddIndices(expr.vars(), &output.variables);
72  }
73  break;
74  case ConstraintProto::ConstraintCase::kIntMod:
75  AddIndices(ct.int_mod().target().vars(), &output.variables);
76  for (const LinearExpressionProto& expr : ct.int_mod().exprs()) {
77  AddIndices(expr.vars(), &output.variables);
78  }
79  break;
80  case ConstraintProto::ConstraintCase::kLinMax: {
81  AddIndices(ct.lin_max().target().vars(), &output.variables);
82  for (const LinearExpressionProto& expr : ct.lin_max().exprs()) {
83  AddIndices(expr.vars(), &output.variables);
84  }
85  break;
86  }
87  case ConstraintProto::ConstraintCase::kIntProd:
88  AddIndices(ct.int_prod().target().vars(), &output.variables);
89  for (const LinearExpressionProto& expr : ct.int_prod().exprs()) {
90  AddIndices(expr.vars(), &output.variables);
91  }
92  break;
93  case ConstraintProto::ConstraintCase::kLinear:
94  AddIndices(ct.linear().vars(), &output.variables);
95  break;
96  case ConstraintProto::ConstraintCase::kAllDiff:
97  for (const LinearExpressionProto& expr : ct.all_diff().exprs()) {
98  AddIndices(expr.vars(), &output.variables);
99  }
100  break;
101  case ConstraintProto::ConstraintCase::kDummyConstraint:
102  AddIndices(ct.dummy_constraint().vars(), &output.variables);
103  break;
104  case ConstraintProto::ConstraintCase::kElement:
105  output.variables.push_back(ct.element().index());
106  output.variables.push_back(ct.element().target());
107  AddIndices(ct.element().vars(), &output.variables);
108  break;
109  case ConstraintProto::ConstraintCase::kCircuit:
110  AddIndices(ct.circuit().literals(), &output.literals);
111  break;
112  case ConstraintProto::ConstraintCase::kRoutes:
113  AddIndices(ct.routes().literals(), &output.literals);
114  break;
115  case ConstraintProto::ConstraintCase::kInverse:
116  AddIndices(ct.inverse().f_direct(), &output.variables);
117  AddIndices(ct.inverse().f_inverse(), &output.variables);
118  break;
119  case ConstraintProto::ConstraintCase::kReservoir:
120  for (const LinearExpressionProto& time : ct.reservoir().time_exprs()) {
121  AddIndices(time.vars(), &output.variables);
122  }
123  for (const LinearExpressionProto& level :
124  ct.reservoir().level_changes()) {
125  AddIndices(level.vars(), &output.variables);
126  }
127  AddIndices(ct.reservoir().active_literals(), &output.literals);
128  break;
129  case ConstraintProto::ConstraintCase::kTable:
130  AddIndices(ct.table().vars(), &output.variables);
131  break;
132  case ConstraintProto::ConstraintCase::kAutomaton:
133  AddIndices(ct.automaton().vars(), &output.variables);
134  break;
135  case ConstraintProto::ConstraintCase::kInterval:
136  AddIndices(ct.interval().start().vars(), &output.variables);
137  AddIndices(ct.interval().size().vars(), &output.variables);
138  AddIndices(ct.interval().end().vars(), &output.variables);
139  break;
140  case ConstraintProto::ConstraintCase::kNoOverlap:
141  break;
142  case ConstraintProto::ConstraintCase::kNoOverlap2D:
143  break;
144  case ConstraintProto::ConstraintCase::kCumulative:
145  AddIndices(ct.cumulative().capacity().vars(), &output.variables);
146  for (const LinearExpressionProto& demand : ct.cumulative().demands()) {
147  AddIndices(demand.vars(), &output.variables);
148  }
149  break;
150  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
151  break;
152  }
153  return output;
154 }
155 
156 #define APPLY_TO_SINGULAR_FIELD(ct_name, field_name) \
157  { \
158  int temp = ct->mutable_##ct_name()->field_name(); \
159  f(&temp); \
160  ct->mutable_##ct_name()->set_##field_name(temp); \
161  }
162 
163 #define APPLY_TO_REPEATED_FIELD(ct_name, field_name) \
164  { \
165  for (int& r : *ct->mutable_##ct_name()->mutable_##field_name()) f(&r); \
166  }
167 
168 void ApplyToAllLiteralIndices(const std::function<void(int*)>& f,
169  ConstraintProto* ct) {
170  for (int& r : *ct->mutable_enforcement_literal()) f(&r);
171  switch (ct->constraint_case()) {
172  case ConstraintProto::ConstraintCase::kBoolOr:
173  APPLY_TO_REPEATED_FIELD(bool_or, literals);
174  break;
175  case ConstraintProto::ConstraintCase::kBoolAnd:
176  APPLY_TO_REPEATED_FIELD(bool_and, literals);
177  break;
178  case ConstraintProto::ConstraintCase::kAtMostOne:
179  APPLY_TO_REPEATED_FIELD(at_most_one, literals);
180  break;
181  case ConstraintProto::ConstraintCase::kExactlyOne:
182  APPLY_TO_REPEATED_FIELD(exactly_one, literals);
183  break;
184  case ConstraintProto::ConstraintCase::kBoolXor:
185  APPLY_TO_REPEATED_FIELD(bool_xor, literals);
186  break;
187  case ConstraintProto::ConstraintCase::kIntDiv:
188  break;
189  case ConstraintProto::ConstraintCase::kIntMod:
190  break;
191  case ConstraintProto::ConstraintCase::kLinMax:
192  break;
193  case ConstraintProto::ConstraintCase::kIntProd:
194  break;
195  case ConstraintProto::ConstraintCase::kLinear:
196  break;
197  case ConstraintProto::ConstraintCase::kAllDiff:
198  break;
199  case ConstraintProto::ConstraintCase::kDummyConstraint:
200  break;
201  case ConstraintProto::ConstraintCase::kElement:
202  break;
203  case ConstraintProto::ConstraintCase::kCircuit:
204  APPLY_TO_REPEATED_FIELD(circuit, literals);
205  break;
206  case ConstraintProto::ConstraintCase::kRoutes:
207  APPLY_TO_REPEATED_FIELD(routes, literals);
208  break;
209  case ConstraintProto::ConstraintCase::kInverse:
210  break;
211  case ConstraintProto::ConstraintCase::kReservoir:
212  APPLY_TO_REPEATED_FIELD(reservoir, active_literals);
213  break;
214  case ConstraintProto::ConstraintCase::kTable:
215  break;
216  case ConstraintProto::ConstraintCase::kAutomaton:
217  break;
218  case ConstraintProto::ConstraintCase::kInterval:
219  break;
220  case ConstraintProto::ConstraintCase::kNoOverlap:
221  break;
222  case ConstraintProto::ConstraintCase::kNoOverlap2D:
223  break;
224  case ConstraintProto::ConstraintCase::kCumulative:
225  break;
226  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
227  break;
228  }
229 }
230 
231 void ApplyToAllVariableIndices(const std::function<void(int*)>& f,
232  ConstraintProto* ct) {
233  switch (ct->constraint_case()) {
234  case ConstraintProto::ConstraintCase::kBoolOr:
235  break;
236  case ConstraintProto::ConstraintCase::kBoolAnd:
237  break;
238  case ConstraintProto::ConstraintCase::kAtMostOne:
239  break;
240  case ConstraintProto::ConstraintCase::kExactlyOne:
241  break;
242  case ConstraintProto::ConstraintCase::kBoolXor:
243  break;
244  case ConstraintProto::ConstraintCase::kIntDiv:
245  APPLY_TO_REPEATED_FIELD(int_div, target()->mutable_vars);
246  for (int i = 0; i < ct->int_div().exprs_size(); ++i) {
247  APPLY_TO_REPEATED_FIELD(int_div, exprs(i)->mutable_vars);
248  }
249  break;
250  case ConstraintProto::ConstraintCase::kIntMod:
251  APPLY_TO_REPEATED_FIELD(int_mod, target()->mutable_vars);
252  for (int i = 0; i < ct->int_mod().exprs_size(); ++i) {
253  APPLY_TO_REPEATED_FIELD(int_mod, exprs(i)->mutable_vars);
254  }
255  break;
256  case ConstraintProto::ConstraintCase::kLinMax:
257  APPLY_TO_REPEATED_FIELD(lin_max, target()->mutable_vars);
258  for (int i = 0; i < ct->lin_max().exprs_size(); ++i) {
259  APPLY_TO_REPEATED_FIELD(lin_max, exprs(i)->mutable_vars);
260  }
261  break;
262  case ConstraintProto::ConstraintCase::kIntProd:
263  APPLY_TO_REPEATED_FIELD(int_prod, target()->mutable_vars);
264  for (int i = 0; i < ct->int_prod().exprs_size(); ++i) {
265  APPLY_TO_REPEATED_FIELD(int_prod, exprs(i)->mutable_vars);
266  }
267  break;
268  case ConstraintProto::ConstraintCase::kLinear:
269  APPLY_TO_REPEATED_FIELD(linear, vars);
270  break;
271  case ConstraintProto::ConstraintCase::kAllDiff:
272  for (int i = 0; i < ct->all_diff().exprs_size(); ++i) {
273  APPLY_TO_REPEATED_FIELD(all_diff, exprs(i)->mutable_vars);
274  }
275  break;
276  case ConstraintProto::ConstraintCase::kDummyConstraint:
277  APPLY_TO_REPEATED_FIELD(dummy_constraint, vars);
278  break;
279  case ConstraintProto::ConstraintCase::kElement:
280  APPLY_TO_SINGULAR_FIELD(element, index);
281  APPLY_TO_SINGULAR_FIELD(element, target);
282  APPLY_TO_REPEATED_FIELD(element, vars);
283  break;
284  case ConstraintProto::ConstraintCase::kCircuit:
285  break;
286  case ConstraintProto::ConstraintCase::kRoutes:
287  break;
288  case ConstraintProto::ConstraintCase::kInverse:
289  APPLY_TO_REPEATED_FIELD(inverse, f_direct);
290  APPLY_TO_REPEATED_FIELD(inverse, f_inverse);
291  break;
292  case ConstraintProto::ConstraintCase::kReservoir:
293  for (int i = 0; i < ct->reservoir().time_exprs_size(); ++i) {
294  APPLY_TO_REPEATED_FIELD(reservoir, time_exprs(i)->mutable_vars);
295  }
296  for (int i = 0; i < ct->reservoir().level_changes_size(); ++i) {
297  APPLY_TO_REPEATED_FIELD(reservoir, level_changes(i)->mutable_vars);
298  }
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  APPLY_TO_REPEATED_FIELD(interval, start()->mutable_vars);
308  APPLY_TO_REPEATED_FIELD(interval, size()->mutable_vars);
309  APPLY_TO_REPEATED_FIELD(interval, end()->mutable_vars);
310  break;
311  case ConstraintProto::ConstraintCase::kNoOverlap:
312  break;
313  case ConstraintProto::ConstraintCase::kNoOverlap2D:
314  break;
315  case ConstraintProto::ConstraintCase::kCumulative:
316  APPLY_TO_REPEATED_FIELD(cumulative, capacity()->mutable_vars);
317  for (int i = 0; i < ct->cumulative().demands_size(); ++i) {
318  for (int& r :
319  *ct->mutable_cumulative()->mutable_demands(i)->mutable_vars()) {
320  f(&r);
321  }
322  }
323  break;
324  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
325  break;
326  }
327 }
328 
329 void ApplyToAllIntervalIndices(const std::function<void(int*)>& f,
330  ConstraintProto* ct) {
331  switch (ct->constraint_case()) {
332  case ConstraintProto::ConstraintCase::kBoolOr:
333  break;
334  case ConstraintProto::ConstraintCase::kBoolAnd:
335  break;
336  case ConstraintProto::ConstraintCase::kAtMostOne:
337  break;
338  case ConstraintProto::ConstraintCase::kExactlyOne:
339  break;
340  case ConstraintProto::ConstraintCase::kBoolXor:
341  break;
342  case ConstraintProto::ConstraintCase::kIntDiv:
343  break;
344  case ConstraintProto::ConstraintCase::kIntMod:
345  break;
346  case ConstraintProto::ConstraintCase::kLinMax:
347  break;
348  case ConstraintProto::ConstraintCase::kIntProd:
349  break;
350  case ConstraintProto::ConstraintCase::kLinear:
351  break;
352  case ConstraintProto::ConstraintCase::kAllDiff:
353  break;
354  case ConstraintProto::ConstraintCase::kDummyConstraint:
355  break;
356  case ConstraintProto::ConstraintCase::kElement:
357  break;
358  case ConstraintProto::ConstraintCase::kCircuit:
359  break;
360  case ConstraintProto::ConstraintCase::kRoutes:
361  break;
362  case ConstraintProto::ConstraintCase::kInverse:
363  break;
364  case ConstraintProto::ConstraintCase::kReservoir:
365  break;
366  case ConstraintProto::ConstraintCase::kTable:
367  break;
368  case ConstraintProto::ConstraintCase::kAutomaton:
369  break;
370  case ConstraintProto::ConstraintCase::kInterval:
371  break;
372  case ConstraintProto::ConstraintCase::kNoOverlap:
373  APPLY_TO_REPEATED_FIELD(no_overlap, intervals);
374  break;
375  case ConstraintProto::ConstraintCase::kNoOverlap2D:
376  APPLY_TO_REPEATED_FIELD(no_overlap_2d, x_intervals);
377  APPLY_TO_REPEATED_FIELD(no_overlap_2d, y_intervals);
378  break;
379  case ConstraintProto::ConstraintCase::kCumulative:
380  APPLY_TO_REPEATED_FIELD(cumulative, intervals);
381  break;
382  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
383  break;
384  }
385 }
386 
387 #undef APPLY_TO_SINGULAR_FIELD
388 #undef APPLY_TO_REPEATED_FIELD
389 
390 std::string ConstraintCaseName(
391  ConstraintProto::ConstraintCase constraint_case) {
392  switch (constraint_case) {
393  case ConstraintProto::ConstraintCase::kBoolOr:
394  return "kBoolOr";
395  case ConstraintProto::ConstraintCase::kBoolAnd:
396  return "kBoolAnd";
397  case ConstraintProto::ConstraintCase::kAtMostOne:
398  return "kAtMostOne";
399  case ConstraintProto::ConstraintCase::kExactlyOne:
400  return "kExactlyOne";
401  case ConstraintProto::ConstraintCase::kBoolXor:
402  return "kBoolXor";
403  case ConstraintProto::ConstraintCase::kIntDiv:
404  return "kIntDiv";
405  case ConstraintProto::ConstraintCase::kIntMod:
406  return "kIntMod";
407  case ConstraintProto::ConstraintCase::kLinMax:
408  return "kLinMax";
409  case ConstraintProto::ConstraintCase::kIntProd:
410  return "kIntProd";
411  case ConstraintProto::ConstraintCase::kLinear:
412  return "kLinear";
413  case ConstraintProto::ConstraintCase::kAllDiff:
414  return "kAllDiff";
415  case ConstraintProto::ConstraintCase::kDummyConstraint:
416  return "kDummyConstraint";
417  case ConstraintProto::ConstraintCase::kElement:
418  return "kElement";
419  case ConstraintProto::ConstraintCase::kCircuit:
420  return "kCircuit";
421  case ConstraintProto::ConstraintCase::kRoutes:
422  return "kRoutes";
423  case ConstraintProto::ConstraintCase::kInverse:
424  return "kInverse";
425  case ConstraintProto::ConstraintCase::kReservoir:
426  return "kReservoir";
427  case ConstraintProto::ConstraintCase::kTable:
428  return "kTable";
429  case ConstraintProto::ConstraintCase::kAutomaton:
430  return "kAutomaton";
431  case ConstraintProto::ConstraintCase::kInterval:
432  return "kInterval";
433  case ConstraintProto::ConstraintCase::kNoOverlap:
434  return "kNoOverlap";
435  case ConstraintProto::ConstraintCase::kNoOverlap2D:
436  return "kNoOverlap2D";
437  case ConstraintProto::ConstraintCase::kCumulative:
438  return "kCumulative";
439  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
440  return "kEmpty";
441  }
442 }
443 
444 std::vector<int> UsedVariables(const ConstraintProto& ct) {
445  IndexReferences references = GetReferencesUsedByConstraint(ct);
446  for (int& ref : references.variables) {
447  ref = PositiveRef(ref);
448  }
449  for (const int lit : references.literals) {
450  references.variables.push_back(PositiveRef(lit));
451  }
452  for (const int lit : ct.enforcement_literal()) {
453  references.variables.push_back(PositiveRef(lit));
454  }
455  gtl::STLSortAndRemoveDuplicates(&references.variables);
456  return references.variables;
457 }
458 
459 std::vector<int> UsedIntervals(const ConstraintProto& ct) {
460  std::vector<int> used_intervals;
461  switch (ct.constraint_case()) {
462  case ConstraintProto::ConstraintCase::kBoolOr:
463  break;
464  case ConstraintProto::ConstraintCase::kBoolAnd:
465  break;
466  case ConstraintProto::ConstraintCase::kAtMostOne:
467  break;
468  case ConstraintProto::ConstraintCase::kExactlyOne:
469  break;
470  case ConstraintProto::ConstraintCase::kBoolXor:
471  break;
472  case ConstraintProto::ConstraintCase::kIntDiv:
473  break;
474  case ConstraintProto::ConstraintCase::kIntMod:
475  break;
476  case ConstraintProto::ConstraintCase::kLinMax:
477  break;
478  case ConstraintProto::ConstraintCase::kIntProd:
479  break;
480  case ConstraintProto::ConstraintCase::kLinear:
481  break;
482  case ConstraintProto::ConstraintCase::kAllDiff:
483  break;
484  case ConstraintProto::ConstraintCase::kDummyConstraint:
485  break;
486  case ConstraintProto::ConstraintCase::kElement:
487  break;
488  case ConstraintProto::ConstraintCase::kCircuit:
489  break;
490  case ConstraintProto::ConstraintCase::kRoutes:
491  break;
492  case ConstraintProto::ConstraintCase::kInverse:
493  break;
494  case ConstraintProto::ConstraintCase::kReservoir:
495  break;
496  case ConstraintProto::ConstraintCase::kTable:
497  break;
498  case ConstraintProto::ConstraintCase::kAutomaton:
499  break;
500  case ConstraintProto::ConstraintCase::kInterval:
501  break;
502  case ConstraintProto::ConstraintCase::kNoOverlap:
503  AddIndices(ct.no_overlap().intervals(), &used_intervals);
504  break;
505  case ConstraintProto::ConstraintCase::kNoOverlap2D:
506  AddIndices(ct.no_overlap_2d().x_intervals(), &used_intervals);
507  AddIndices(ct.no_overlap_2d().y_intervals(), &used_intervals);
508  break;
509  case ConstraintProto::ConstraintCase::kCumulative:
510  AddIndices(ct.cumulative().intervals(), &used_intervals);
511  break;
512  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
513  break;
514  }
515  gtl::STLSortAndRemoveDuplicates(&used_intervals);
516  return used_intervals;
517 }
518 
519 int64_t ComputeInnerObjective(const CpObjectiveProto& objective,
520  absl::Span<const int64_t> solution) {
521  int64_t objective_value = 0;
522  for (int i = 0; i < objective.vars_size(); ++i) {
523  int64_t coeff = objective.coeffs(i);
524  const int ref = objective.vars(i);
525  const int var = PositiveRef(ref);
526  if (!RefIsPositive(ref)) coeff = -coeff;
527  objective_value += coeff * solution[var];
528  }
529  return objective_value;
530 }
531 
532 bool ExpressionContainsSingleRef(const LinearExpressionProto& expr) {
533  return expr.offset() == 0 && expr.vars_size() == 1 &&
534  std::abs(expr.coeffs(0)) == 1;
535 }
536 
537 bool ExpressionIsAffine(const LinearExpressionProto& expr) {
538  return expr.vars_size() <= 1;
539 }
540 
541 // Returns the reference the expression can be reduced to. It will DCHECK that
542 // ExpressionContainsSingleRef(expr) is true.
543 int GetSingleRefFromExpression(const LinearExpressionProto& expr) {
544  DCHECK(ExpressionContainsSingleRef(expr));
545  return expr.coeffs(0) == 1 ? expr.vars(0) : NegatedRef(expr.vars(0));
546 }
547 
548 void AddLinearExpressionToLinearConstraint(const LinearExpressionProto& expr,
549  int64_t coefficient,
550  LinearConstraintProto* linear) {
551  for (int i = 0; i < expr.vars_size(); ++i) {
552  linear->add_vars(expr.vars(i));
553  linear->add_coeffs(expr.coeffs(i) * coefficient);
554  }
555  DCHECK(!linear->domain().empty());
556  const int64_t shift = coefficient * expr.offset();
557  if (shift != 0) {
558  FillDomainInProto(ReadDomainFromProto(*linear).AdditionWith(Domain(-shift)),
559  linear);
560  }
561 }
562 
563 bool LinearExpressionProtosAreEqual(const LinearExpressionProto& a,
564  const LinearExpressionProto& b,
565  int64_t b_scaling) {
566  if (a.vars_size() != b.vars_size()) return false;
567  if (a.offset() != b.offset() * b_scaling) return false;
568  absl::flat_hash_map<int, int64_t> coeffs;
569  for (int i = 0; i < a.vars_size(); ++i) {
570  coeffs[a.vars(i)] += a.coeffs(i);
571  coeffs[b.vars(i)] += -b.coeffs(i) * b_scaling;
572  }
573 
574  for (const auto [var, coeff] : coeffs) {
575  if (coeff != 0) return false;
576  }
577  return true;
578 }
579 
580 uint64_t FingerprintExpression(const LinearExpressionProto& lin,
581  uint64_t seed) {
582  uint64_t fp = seed;
583  if (!lin.vars().empty()) {
584  fp = FingerprintRepeatedField(lin.vars(), fp);
585  fp = FingerprintRepeatedField(lin.coeffs(), fp);
586  }
587  fp = FingerprintSingleField(lin.offset(), fp);
588  return fp;
589 }
590 
591 uint64_t FingerprintModel(const CpModelProto& model, uint64_t seed) {
592  uint64_t fp = seed;
593  for (const IntegerVariableProto& var_proto : model.variables()) {
594  fp = FingerprintRepeatedField(var_proto.domain(), fp);
595  }
596  for (const ConstraintProto& ct : model.constraints()) {
597  if (!ct.enforcement_literal().empty()) {
598  fp = FingerprintRepeatedField(ct.enforcement_literal(), fp);
599  }
600  switch (ct.constraint_case()) {
601  case ConstraintProto::ConstraintCase::kBoolOr:
602  fp = FingerprintRepeatedField(ct.bool_or().literals(), fp);
603  break;
604  case ConstraintProto::ConstraintCase::kBoolAnd:
605  fp = FingerprintRepeatedField(ct.bool_and().literals(), fp);
606  break;
607  case ConstraintProto::ConstraintCase::kAtMostOne:
608  fp = FingerprintRepeatedField(ct.at_most_one().literals(), fp);
609  break;
610  case ConstraintProto::ConstraintCase::kExactlyOne:
611  fp = FingerprintRepeatedField(ct.exactly_one().literals(), fp);
612  break;
613  case ConstraintProto::ConstraintCase::kBoolXor:
614  fp = FingerprintRepeatedField(ct.bool_xor().literals(), fp);
615  break;
616  case ConstraintProto::ConstraintCase::kIntDiv:
617  fp = FingerprintExpression(ct.int_div().target(), fp);
618  for (const LinearExpressionProto& expr : ct.int_div().exprs()) {
619  fp = FingerprintExpression(expr, fp);
620  }
621  break;
622  case ConstraintProto::ConstraintCase::kIntMod:
623  fp = FingerprintExpression(ct.int_mod().target(), fp);
624  for (const LinearExpressionProto& expr : ct.int_mod().exprs()) {
625  fp = FingerprintExpression(expr, fp);
626  }
627  break;
628  case ConstraintProto::ConstraintCase::kLinMax: {
629  fp = FingerprintExpression(ct.lin_max().target(), fp);
630  for (const LinearExpressionProto& expr : ct.lin_max().exprs()) {
631  fp = FingerprintExpression(expr, fp);
632  }
633  break;
634  }
635  case ConstraintProto::ConstraintCase::kIntProd:
636  fp = FingerprintExpression(ct.int_prod().target(), fp);
637  for (const LinearExpressionProto& expr : ct.int_prod().exprs()) {
638  fp = FingerprintExpression(expr, fp);
639  }
640  break;
641  case ConstraintProto::ConstraintCase::kLinear:
642  fp = FingerprintRepeatedField(ct.linear().vars(), fp);
643  fp = FingerprintRepeatedField(ct.linear().coeffs(), fp);
644  fp = FingerprintRepeatedField(ct.linear().domain(), fp);
645  break;
646  case ConstraintProto::ConstraintCase::kAllDiff:
647  for (const LinearExpressionProto& expr : ct.all_diff().exprs()) {
648  fp = FingerprintExpression(expr, fp);
649  }
650  break;
651  case ConstraintProto::ConstraintCase::kDummyConstraint:
652  break;
653  case ConstraintProto::ConstraintCase::kElement:
654  fp = FingerprintSingleField(ct.element().index(), fp);
655  fp = FingerprintSingleField(ct.element().target(), fp);
656  fp = FingerprintRepeatedField(ct.element().vars(), fp);
657  break;
658  case ConstraintProto::ConstraintCase::kCircuit:
659  fp = FingerprintRepeatedField(ct.circuit().heads(), fp);
660  fp = FingerprintRepeatedField(ct.circuit().tails(), fp);
661  fp = FingerprintRepeatedField(ct.circuit().literals(), fp);
662  break;
663  case ConstraintProto::ConstraintCase::kRoutes:
664  fp = FingerprintRepeatedField(ct.routes().heads(), fp);
665  fp = FingerprintRepeatedField(ct.routes().tails(), fp);
666  fp = FingerprintRepeatedField(ct.routes().literals(), fp);
667  break;
668  case ConstraintProto::ConstraintCase::kInverse:
669  fp = FingerprintRepeatedField(ct.inverse().f_direct(), fp);
670  fp = FingerprintRepeatedField(ct.inverse().f_inverse(), fp);
671  break;
672  case ConstraintProto::ConstraintCase::kReservoir:
673  fp = FingerprintSingleField(ct.reservoir().min_level(), fp);
674  fp = FingerprintSingleField(ct.reservoir().max_level(), fp);
675  for (const LinearExpressionProto& expr : ct.reservoir().time_exprs()) {
676  fp = FingerprintExpression(expr, fp);
677  }
678  for (const LinearExpressionProto& expr :
679  ct.reservoir().level_changes()) {
680  fp = FingerprintExpression(expr, fp);
681  }
682  break;
683  case ConstraintProto::ConstraintCase::kTable:
684  fp = FingerprintRepeatedField(ct.table().vars(), fp);
685  fp = FingerprintRepeatedField(ct.table().values(), fp);
686  fp = FingerprintSingleField(ct.table().negated(), fp);
687  break;
688  case ConstraintProto::ConstraintCase::kAutomaton:
689  fp = FingerprintSingleField(ct.automaton().starting_state(), fp);
690  fp = FingerprintRepeatedField(ct.automaton().final_states(), fp);
691  fp = FingerprintRepeatedField(ct.automaton().transition_tail(), fp);
692  fp = FingerprintRepeatedField(ct.automaton().transition_head(), fp);
693  fp = FingerprintRepeatedField(ct.automaton().transition_label(), fp);
694  fp = FingerprintRepeatedField(ct.automaton().vars(), fp);
695  break;
696  case ConstraintProto::ConstraintCase::kInterval:
697  fp = FingerprintExpression(ct.interval().start(), fp);
698  fp = FingerprintExpression(ct.interval().size(), fp);
699  fp = FingerprintExpression(ct.interval().end(), fp);
700  break;
701  case ConstraintProto::ConstraintCase::kNoOverlap:
702  fp = FingerprintRepeatedField(ct.no_overlap().intervals(), fp);
703  break;
704  case ConstraintProto::ConstraintCase::kNoOverlap2D:
705  fp = FingerprintRepeatedField(ct.no_overlap_2d().x_intervals(), fp);
706  fp = FingerprintRepeatedField(ct.no_overlap_2d().y_intervals(), fp);
707  break;
708  case ConstraintProto::ConstraintCase::kCumulative:
709  fp = FingerprintRepeatedField(ct.cumulative().intervals(), fp);
710  fp = FingerprintExpression(ct.cumulative().capacity(), fp);
711  for (const LinearExpressionProto& demand : ct.cumulative().demands()) {
712  fp = FingerprintExpression(demand, fp);
713  }
714  break;
715  case ConstraintProto::ConstraintCase::CONSTRAINT_NOT_SET:
716  break;
717  }
718  }
719 
720  // Fingerprint the objective.
721  if (model.has_objective()) {
722  fp = FingerprintRepeatedField(model.objective().vars(), fp);
723  fp = FingerprintRepeatedField(model.objective().coeffs(), fp);
724  fp = FingerprintSingleField(model.objective().offset(), fp);
725  fp = FingerprintSingleField(model.objective().scaling_factor(), fp);
726  fp = FingerprintRepeatedField(model.objective().domain(), fp);
727  } else if (model.has_floating_point_objective()) {
728  fp = FingerprintRepeatedField(model.floating_point_objective().vars(), fp);
729  fp =
730  FingerprintRepeatedField(model.floating_point_objective().coeffs(), fp);
731  fp = FingerprintSingleField(model.floating_point_objective().offset(), fp);
732  fp =
733  FingerprintSingleField(model.floating_point_objective().maximize(), fp);
734  }
735 
736  if (model.has_solution_hint()) {
737  fp = FingerprintRepeatedField(model.solution_hint().vars(), fp);
738  fp = FingerprintRepeatedField(model.solution_hint().values(), fp);
739  }
740 
741  // TODO(user): Should we fingerprint decision strategies?
742 
743  return fp;
744 }
745 
746 #if !defined(__PORTABLE_PLATFORM__)
747 namespace {
748 
749 // We need to print " { " instead of " {\n" to inline our variables like:
750 //
751 // variables { domain: [0, 1] }
752 //
753 // instead of
754 //
755 // variables {
756 // domain: [0, 1] }
757 class InlineFieldPrinter
758  : public google::protobuf::TextFormat::FastFieldValuePrinter {
759  void PrintMessageStart(const google::protobuf::Message& /*message*/,
760  int /*field_index*/, int /*field_count*/,
761  bool /*single_line_mode*/,
762  google::protobuf::TextFormat::BaseTextGenerator*
763  generator) const override {
764  generator->PrintLiteral(" { ");
765  }
766 };
767 
768 class InlineMessagePrinter
769  : public google::protobuf::TextFormat::MessagePrinter {
770  public:
771  InlineMessagePrinter() {
772  printer_.SetSingleLineMode(true);
773  printer_.SetUseShortRepeatedPrimitives(true);
774  }
775 
776  void Print(const google::protobuf::Message& message,
777  bool /*single_line_mode*/,
778  google::protobuf::TextFormat::BaseTextGenerator* generator)
779  const override {
780  buffer_.clear();
781  printer_.PrintToString(message, &buffer_);
782  generator->Print(buffer_.data(), buffer_.size());
783  }
784 
785  private:
786  google::protobuf::TextFormat::Printer printer_;
787  mutable std::string buffer_;
788 };
789 
790 // Register a InlineFieldPrinter() for all the fields containing the message we
791 // want to print in one line.
792 void RegisterFieldPrinters(
793  const google::protobuf::Descriptor* descriptor,
794  absl::flat_hash_set<const google::protobuf::Descriptor*>* descriptors,
795  google::protobuf::TextFormat::Printer* printer) {
796  // Recursion stopper.
797  if (!descriptors->insert(descriptor).second) return;
798 
799  for (int i = 0; i < descriptor->field_count(); ++i) {
800  const google::protobuf::FieldDescriptor* field = descriptor->field(i);
801  if (field->type() == google::protobuf::FieldDescriptor::TYPE_MESSAGE) {
802  if (field->message_type() == IntegerVariableProto::descriptor() ||
803  field->message_type() == LinearExpressionProto::descriptor()) {
804  printer->RegisterFieldValuePrinter(field, new InlineFieldPrinter());
805  } else {
806  RegisterFieldPrinters(field->message_type(), descriptors, printer);
807  }
808  }
809  }
810 }
811 
812 } // namespace
813 
814 void SetupTextFormatPrinter(google::protobuf::TextFormat::Printer* printer) {
815  printer->SetUseShortRepeatedPrimitives(true);
816  absl::flat_hash_set<const google::protobuf::Descriptor*> descriptors;
817  RegisterFieldPrinters(CpModelProto::descriptor(), &descriptors, printer);
818  printer->RegisterMessagePrinter(IntegerVariableProto::descriptor(),
819  new InlineMessagePrinter());
820  printer->RegisterMessagePrinter(LinearExpressionProto::descriptor(),
821  new InlineMessagePrinter());
822 }
823 #endif // !defined(__PORTABLE_PLATFORM__)
824 
825 } // namespace sat
826 } // namespace operations_research
operations_research::Domain
We call domain any subset of Int64 = [kint64min, kint64max].
Definition: sorted_interval_list.h:82
operations_research::Domain::AdditionWith
Domain AdditionWith(const Domain &domain) const
Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.
Definition: sorted_interval_list.cc:378
b
int64_t b
Definition: constraint_solver/table.cc:47
a
int64_t a
Definition: constraint_solver/table.cc:46
APPLY_TO_SINGULAR_FIELD
#define APPLY_TO_SINGULAR_FIELD(ct_name, field_name)
Definition: cp_model_utils.cc:156
APPLY_TO_REPEATED_FIELD
#define APPLY_TO_REPEATED_FIELD(ct_name, field_name)
Definition: cp_model_utils.cc:163
cp_model_utils.h
ct
const Constraint * ct
Definition: demon_profiler.cc:44
var
IntVar * var
Definition: expr_array.cc:1874
model
GRBmodel * model
Definition: gurobi_interface.cc:278
index
int index
Definition: local_search.cc:2724
gtl::STLSortAndRemoveDuplicates
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:58
operations_research::sat::FingerprintRepeatedField
uint64_t FingerprintRepeatedField(const google::protobuf::RepeatedField< T > &sequence, uint64_t seed)
Definition: cp_model_utils.h:205
operations_research::sat::UsedVariables
std::vector< int > UsedVariables(const ConstraintProto &ct)
Definition: cp_model_utils.cc:444
operations_research::sat::RefIsPositive
bool RefIsPositive(int ref)
Definition: cp_model_utils.h:43
operations_research::sat::UsedIntervals
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Definition: cp_model_utils.cc:459
operations_research::sat::SetToNegatedLinearExpression
void SetToNegatedLinearExpression(const LinearExpressionProto &input_expr, LinearExpressionProto *output_negated_expr)
Definition: cp_model_utils.cc:40
operations_research::sat::FingerprintSingleField
uint64_t FingerprintSingleField(const T &field, uint64_t seed)
Definition: cp_model_utils.h:213
operations_research::sat::ApplyToAllLiteralIndices
void ApplyToAllLiteralIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
Definition: cp_model_utils.cc:168
operations_research::sat::LinearExpressionProtosAreEqual
bool LinearExpressionProtosAreEqual(const LinearExpressionProto &a, const LinearExpressionProto &b, int64_t b_scaling)
Definition: cp_model_utils.cc:563
operations_research::sat::ApplyToAllIntervalIndices
void ApplyToAllIntervalIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
Definition: cp_model_utils.cc:329
operations_research::sat::FillDomainInProto
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Definition: cp_model_utils.h:100
operations_research::sat::FingerprintExpression
uint64_t FingerprintExpression(const LinearExpressionProto &lin, uint64_t seed)
Definition: cp_model_utils.cc:580
operations_research::sat::ExpressionIsAffine
bool ExpressionIsAffine(const LinearExpressionProto &expr)
Definition: cp_model_utils.cc:537
operations_research::sat::ReadDomainFromProto
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Definition: cp_model_utils.h:111
operations_research::sat::ApplyToAllVariableIndices
void ApplyToAllVariableIndices(const std::function< void(int *)> &f, ConstraintProto *ct)
Definition: cp_model_utils.cc:231
operations_research::sat::ComputeInnerObjective
int64_t ComputeInnerObjective(const CpObjectiveProto &objective, absl::Span< const int64_t > solution)
Definition: cp_model_utils.cc:519
operations_research::sat::SetupTextFormatPrinter
void SetupTextFormatPrinter(google::protobuf::TextFormat::Printer *printer)
Definition: cp_model_utils.cc:814
operations_research::sat::GetReferencesUsedByConstraint
IndexReferences GetReferencesUsedByConstraint(const ConstraintProto &ct)
Definition: cp_model_utils.cc:50
operations_research::sat::PositiveRef
int PositiveRef(int ref)
Definition: cp_model_utils.h:42
operations_research::sat::AddLinearExpressionToLinearConstraint
void AddLinearExpressionToLinearConstraint(const LinearExpressionProto &expr, int64_t coefficient, LinearConstraintProto *linear)
Definition: cp_model_utils.cc:548
operations_research::sat::ConstraintCaseName
std::string ConstraintCaseName(ConstraintProto::ConstraintCase constraint_case)
Definition: cp_model_utils.cc:390
operations_research::sat::GetSingleRefFromExpression
int GetSingleRefFromExpression(const LinearExpressionProto &expr)
Definition: cp_model_utils.cc:543
operations_research::sat::NegatedRef
int NegatedRef(int ref)
Definition: cp_model_utils.h:41
operations_research::sat::ExpressionContainsSingleRef
bool ExpressionContainsSingleRef(const LinearExpressionProto &expr)
Definition: cp_model_utils.cc:532
operations_research::sat::FingerprintModel
uint64_t FingerprintModel(const CpModelProto &model, uint64_t seed)
Definition: cp_model_utils.cc:591
operations_research
Collection of objects used to extend the Constraint Solver library.
Definition: dense_doubly_linked_list.h:21
demand
int64_t demand
Definition: resource.cc:126
time
int64_t time
Definition: resource.cc:1694
interval
IntervalVar * interval
Definition: resource.cc:101
coefficient
int64_t coefficient
Definition: routing_filters.cc:969
capacity
int64_t capacity
Definition: routing_flow.cc:151
sorted_interval_list.h
end
std::optional< int64_t > end
Definition: sparse_submatrix.cc:37
start
int64_t start
Definition: sparse_submatrix.cc:36
stl_util.h
operations_research::sat::IndexReferences
Definition: cp_model_utils.h:61
operations_research::sat::IndexReferences::variables
std::vector< int > variables
Definition: cp_model_utils.h:62
operations_research::sat::IndexReferences::literals
std::vector< int > literals
Definition: cp_model_utils.h:63
message
std::string message
Definition: trace.cc:399
objective_value
double objective_value
Definition: trust_region.cc:168