OR-Tools  8.2
presolve.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 
16 #include <map>
17 #include <set>
18 
19 #include "absl/strings/match.h"
20 #include "absl/strings/str_format.h"
21 #include "absl/strings/str_join.h"
22 #include "absl/strings/string_view.h"
23 #include "ortools/base/map_util.h"
25 #include "ortools/flatzinc/model.h"
26 #include "ortools/graph/cliques.h"
29 
30 ABSL_FLAG(bool, fz_floats_are_ints, true,
31  "Interpret floats as integers in all variables and constraints.");
32 
33 namespace operations_research {
34 namespace fz {
35 namespace {
36 enum PresolveState { ALWAYS_FALSE, ALWAYS_TRUE, UNDECIDED };
37 
38 // TODO(user): accept variables fixed to 0 or 1.
39 bool Has01Values(IntegerVariable* var) {
40  return var->domain.Min() == 0 && var->domain.Max() == 1;
41 }
42 
43 bool Is0Or1(int64 value) { return !(value & ~1LL); }
44 
45 template <class T>
46 bool IsArrayBoolean(const std::vector<T>& values) {
47  for (int i = 0; i < values.size(); ++i) {
48  if (values[i] != 0 && values[i] != 1) {
49  return false;
50  }
51  }
52  return true;
53 }
54 
55 template <class T>
56 bool AtMostOne0OrAtMostOne1(const std::vector<T>& values) {
57  CHECK(IsArrayBoolean(values));
58  int num_zero = 0;
59  int num_one = 0;
60  for (T val : values) {
61  if (val) {
62  num_one++;
63  } else {
64  num_zero++;
65  }
66  if (num_one > 1 && num_zero > 1) {
67  return false;
68  }
69  }
70  return true;
71 }
72 
73 absl::flat_hash_set<int64> GetValueSet(const Argument& arg) {
74  absl::flat_hash_set<int64> result;
75  if (arg.HasOneValue()) {
76  result.insert(arg.Value());
77  } else {
78  const Domain& domain = arg.Var()->domain;
79  if (domain.is_interval && !domain.values.empty()) {
80  for (int64 v = domain.values[0]; v <= domain.values[1]; ++v) {
81  result.insert(v);
82  }
83  } else {
84  result.insert(domain.values.begin(), domain.values.end());
85  }
86  }
87  return result;
88 }
89 
90 void SetConstraintAsIntEq(Constraint* ct, IntegerVariable* var, int64 value) {
91  CHECK(var != nullptr);
92  ct->type = "int_eq";
93  ct->arguments.clear();
94  ct->arguments.push_back(Argument::IntVarRef(var));
96 }
97 
98 bool OverlapsAt(const Argument& array, int pos, const Argument& other) {
99  if (array.type == Argument::INT_VAR_REF_ARRAY) {
100  const Domain& domain = array.variables[pos]->domain;
101  if (domain.IsAllInt64()) {
102  return true;
103  }
104  switch (other.type) {
105  case Argument::INT_VALUE: {
106  return domain.Contains(other.Value());
107  }
108  case Argument::INT_INTERVAL: {
109  return domain.OverlapsIntInterval(other.values[0], other.values[1]);
110  }
111  case Argument::INT_LIST: {
112  return domain.OverlapsIntList(other.values);
113  }
114  case Argument::INT_VAR_REF: {
115  return domain.OverlapsDomain(other.variables[0]->domain);
116  }
117  default: {
118  LOG(FATAL) << "Case not supported in OverlapsAt";
119  return false;
120  }
121  }
122  } else if (array.type == Argument::INT_LIST) {
123  const int64 value = array.values[pos];
124  switch (other.type) {
125  case Argument::INT_VALUE: {
126  return value == other.values[0];
127  }
128  case Argument::INT_INTERVAL: {
129  return other.values[0] <= value && value <= other.values[1];
130  }
131  case Argument::INT_LIST: {
132  return std::find(other.values.begin(), other.values.end(), value) !=
133  other.values.end();
134  }
135  case Argument::INT_VAR_REF: {
136  return other.variables[0]->domain.Contains(value);
137  }
138  default: {
139  LOG(FATAL) << "Case not supported in OverlapsAt";
140  return false;
141  }
142  }
143  } else {
144  LOG(FATAL) << "First argument not supported in OverlapsAt";
145  return false;
146  }
147 }
148 
149 template <class T>
150 void AppendIfNotInSet(T* value, absl::flat_hash_set<T*>* s,
151  std::vector<T*>* vec) {
152  if (s->insert(value).second) {
153  vec->push_back(value);
154  }
155  DCHECK_EQ(s->size(), vec->size());
156 }
157 
158 } // namespace
159 
160 // Note on documentation
161 //
162 // In order to document presolve rules, we will use the following naming
163 // convention:
164 // - x, x1, xi, y, y1, yi denote integer variables
165 // - b, b1, bi denote boolean variables
166 // - c, c1, ci denote integer constants
167 // - t, t1, ti denote boolean constants
168 // - => x after a constraint denotes the target variable of this constraint.
169 // Arguments are listed in order.
170 
171 // Propagates cast constraint.
172 // Rule 1:
173 // Input: bool2int(b, c) or bool2int(t, x)
174 // Output: int_eq(...)
175 //
176 // Rule 2:
177 // Input: bool2int(b, x)
178 // Action: Replace all instances of x by b.
179 // Output: inactive constraint
180 void Presolver::PresolveBool2Int(Constraint* ct) {
181  DCHECK_EQ(ct->type, "bool2int");
182  if (ct->arguments[0].HasOneValue() || ct->arguments[1].HasOneValue()) {
183  // Rule 1.
184  UpdateRuleStats("bool2int: rename to int_eq");
185  ct->type = "int_eq";
186  } else {
187  // Rule 2.
188  UpdateRuleStats("bool2int: merge boolean and integer variables.");
189  AddVariableSubstitution(ct->arguments[1].Var(), ct->arguments[0].Var());
190  ct->MarkAsInactive();
191  }
192 }
193 
194 // Minizinc flattens 2d element constraints (x = A[y][z]) into 1d element
195 // constraint with an affine mapping between y, z and the new index.
196 // This rule stores the mapping to reconstruct the 2d element constraint.
197 // This mapping can involve 1 or 2 variables dependening if y or z in A[y][z]
198 // is a constant in the model).
199 void Presolver::PresolveStoreAffineMapping(Constraint* ct) {
200  CHECK_EQ(2, ct->arguments[1].variables.size());
201  IntegerVariable* const var0 = ct->arguments[1].variables[0];
202  IntegerVariable* const var1 = ct->arguments[1].variables[1];
203  const int64 coeff0 = ct->arguments[0].values[0];
204  const int64 coeff1 = ct->arguments[0].values[1];
205  const int64 rhs = ct->arguments[2].Value();
206  if (coeff0 == -1 && !gtl::ContainsKey(affine_map_, var0)) {
207  affine_map_[var0] = AffineMapping(var1, coeff0, -rhs, ct);
208  UpdateRuleStats("int_lin_eq: store affine mapping");
209  } else if (coeff1 == -1 && !gtl::ContainsKey(affine_map_, var1)) {
210  affine_map_[var1] = AffineMapping(var0, coeff0, -rhs, ct);
211  UpdateRuleStats("int_lin_eq: store affine mapping");
212  }
213 }
214 
215 void Presolver::PresolveStoreFlatteningMapping(Constraint* ct) {
216  CHECK_EQ(3, ct->arguments[1].variables.size());
217  IntegerVariable* const var0 = ct->arguments[1].variables[0];
218  IntegerVariable* const var1 = ct->arguments[1].variables[1];
219  IntegerVariable* const var2 = ct->arguments[1].variables[2];
220  const int64 coeff0 = ct->arguments[0].values[0];
221  const int64 coeff1 = ct->arguments[0].values[1];
222  const int64 coeff2 = ct->arguments[0].values[2];
223  const int64 rhs = ct->arguments[2].Value();
224  if (coeff0 == -1 && coeff2 == 1 &&
225  !gtl::ContainsKey(array2d_index_map_, var0)) {
226  array2d_index_map_[var0] =
227  Array2DIndexMapping(var1, coeff1, var2, -rhs, ct);
228  UpdateRuleStats("int_lin_eq: store 2d flattening mapping");
229  } else if (coeff0 == -1 && coeff1 == 1 &&
230  !gtl::ContainsKey(array2d_index_map_, var0)) {
231  array2d_index_map_[var0] =
232  Array2DIndexMapping(var2, coeff2, var1, -rhs, ct);
233  UpdateRuleStats("int_lin_eq: store 2d flattening mapping");
234  } else if (coeff2 == -1 && coeff1 == 1 &&
235  !gtl::ContainsKey(array2d_index_map_, var2)) {
236  array2d_index_map_[var2] =
237  Array2DIndexMapping(var0, coeff0, var1, -rhs, ct);
238  UpdateRuleStats("int_lin_eq: store 2d flattening mapping");
239  } else if (coeff2 == -1 && coeff0 == 1 &&
240  !gtl::ContainsKey(array2d_index_map_, var2)) {
241  array2d_index_map_[var2] =
242  Array2DIndexMapping(var1, coeff1, var0, -rhs, ct);
243  UpdateRuleStats("int_lin_eq: store 2d flattening mapping");
244  }
245 }
246 
247 namespace {
248 bool IsIncreasingAndContiguous(const std::vector<int64>& values) {
249  for (int i = 0; i < values.size() - 1; ++i) {
250  if (values[i + 1] != values[i] + 1) {
251  return false;
252  }
253  }
254  return true;
255 }
256 
257 bool AreOnesFollowedByMinusOne(const std::vector<int64>& coeffs) {
258  CHECK(!coeffs.empty());
259  for (int i = 0; i < coeffs.size() - 1; ++i) {
260  if (coeffs[i] != 1) {
261  return false;
262  }
263  }
264  return coeffs.back() == -1;
265 }
266 
267 template <class T>
268 bool IsStrictPrefix(const std::vector<T>& v1, const std::vector<T>& v2) {
269  if (v1.size() >= v2.size()) {
270  return false;
271  }
272  for (int i = 0; i < v1.size(); ++i) {
273  if (v1[i] != v2[i]) {
274  return false;
275  }
276  }
277  return true;
278 }
279 } // namespace
280 
281 // Rewrite array element: array_int_element:
282 //
283 // Rule 1:
284 // Input : array_int_element(x0, [c1, .., cn], y) with x0 = a * x + b
285 // Output: array_int_element(x, [c_a1, .., c_am], b) with a * i = b = ai
286 //
287 // Rule 2:
288 // Input : array_int_element(x, [c1, .., cn], y) with x = a * x1 + x2 + b
289 // Output: array_int_element([x1, x2], [c_a1, .., c_am], b, [a, b])
290 // to be interpreted by the extraction process.
291 //
292 // Rule 3:
293 // Input: array_int_element(x, [c1, .., cn], y)
294 // Output array_int_element(x, [c1, .., c{max(x)}], y)
295 //
296 // Rule 4:
297 // Input : array_int_element(x, [c1, .., cn], y) with x0 ci = c0 + i
298 // Output: int_lin_eq([-1, 1], [y, x], 1 - c) (e.g. y = x + c - 1)
299 void Presolver::PresolveSimplifyElement(Constraint* ct) {
300  if (ct->arguments[0].variables.size() != 1) return;
301  IntegerVariable* const index_var = ct->arguments[0].Var();
302 
303  // Rule 1.
304  if (gtl::ContainsKey(affine_map_, index_var)) {
305  const AffineMapping& mapping = affine_map_[index_var];
306  const Domain& domain = mapping.variable->domain;
307  if (domain.is_interval && domain.values.empty()) {
308  // Invalid case. Ignore it.
309  return;
310  }
311  if (domain.values[0] == 0 && mapping.coefficient == 1 &&
312  mapping.offset > 1 && index_var->domain.is_interval) {
313  // Simple translation
314  const int offset = mapping.offset - 1;
315  const int size = ct->arguments[1].values.size();
316  for (int i = 0; i < size - offset; ++i) {
317  ct->arguments[1].values[i] = ct->arguments[1].values[i + offset];
318  }
319  ct->arguments[1].values.resize(size - offset);
320  affine_map_[index_var].constraint->arguments[2].values[0] = -1;
321  affine_map_[index_var].offset = 1;
322  index_var->domain.values[0] -= offset;
323  index_var->domain.values[1] -= offset;
324  UpdateRuleStats("array_int_element: simplify using affine mapping.");
325  return;
326  } else if (mapping.offset + mapping.coefficient > 0 &&
327  domain.values[0] > 0) {
328  const std::vector<int64>& values = ct->arguments[1].values;
329  std::vector<int64> new_values;
330  for (int64 i = 1; i <= domain.values.back(); ++i) {
331  const int64 index = i * mapping.coefficient + mapping.offset - 1;
332  if (index < 0) {
333  return;
334  }
335  if (index > values.size()) {
336  break;
337  }
338  new_values.push_back(values[index]);
339  }
340  // Rewrite constraint.
341  UpdateRuleStats("array_int_element: simplify using affine mapping.");
342  ct->arguments[0].variables[0] = mapping.variable;
343  ct->arguments[0].variables[0]->domain.IntersectWithInterval(
344  1, new_values.size());
345  // TODO(user): Encapsulate argument setters.
346  ct->arguments[1].values.swap(new_values);
347  if (ct->arguments[1].values.size() == 1) {
348  ct->arguments[1].type = Argument::INT_VALUE;
349  }
350  // Reset propagate flag.
351  ct->presolve_propagation_done = false;
352  // Mark old index var and affine constraint as presolved out.
353  mapping.constraint->MarkAsInactive();
354  index_var->active = false;
355  return;
356  }
357  }
358 
359  // Rule 2.
360  if (gtl::ContainsKey(array2d_index_map_, index_var)) {
361  UpdateRuleStats("array_int_element: rewrite as a 2d element");
362  const Array2DIndexMapping& mapping = array2d_index_map_[index_var];
363  // Rewrite constraint.
364  ct->arguments[0] =
365  Argument::IntVarRefArray({mapping.variable1, mapping.variable2});
366  std::vector<int64> coefs;
367  coefs.push_back(mapping.coefficient);
368  coefs.push_back(1);
369  ct->arguments.push_back(Argument::IntegerList(coefs));
370  ct->arguments.push_back(Argument::IntegerValue(mapping.offset));
371  index_var->active = false;
372  mapping.constraint->MarkAsInactive();
373  return;
374  }
375 
376  // Rule 3.
377  if (index_var->domain.Max() < ct->arguments[1].values.size()) {
378  // Reduce array of values.
379  ct->arguments[1].values.resize(index_var->domain.Max());
380  ct->presolve_propagation_done = false;
381  UpdateRuleStats("array_int_element: reduce array");
382  return;
383  }
384 
385  // Rule 4.
386  if (IsIncreasingAndContiguous(ct->arguments[1].values) &&
387  ct->arguments[2].type == Argument::INT_VAR_REF) {
388  const int64 start = ct->arguments[1].values.front();
389  IntegerVariable* const index = ct->arguments[0].Var();
390  IntegerVariable* const target = ct->arguments[2].Var();
391  UpdateRuleStats("array_int_element: rewrite as a linear constraint");
392 
393  if (start == 1) {
394  ct->type = "int_eq";
395  ct->RemoveArg(1);
396  } else {
397  // Rewrite constraint into a int_lin_eq
398  ct->type = "int_lin_eq";
399  ct->arguments[0] = Argument::IntegerList({-1, 1});
400  ct->arguments[1] = Argument::IntVarRefArray({target, index});
401  ct->arguments[2] = Argument::IntegerValue(1 - start);
402  }
403  }
404 }
405 
406 // Simplifies array_var_int_element
407 //
408 // Input : array_var_int_element(x0, [x1, .., xn], y) with x0 = a * x + b
409 // Output: array_var_int_element(x, [x_a1, .., x_an], b) with a * i = b = ai
410 void Presolver::PresolveSimplifyExprElement(Constraint* ct) {
411  if (ct->arguments[0].variables.size() != 1) return;
412 
413  IntegerVariable* const index_var = ct->arguments[0].Var();
414  if (gtl::ContainsKey(affine_map_, index_var)) {
415  const AffineMapping& mapping = affine_map_[index_var];
416  const Domain& domain = mapping.variable->domain;
417  if ((domain.is_interval && domain.values.empty()) ||
418  domain.values[0] != 1 || mapping.offset + mapping.coefficient <= 0) {
419  // Invalid case. Ignore it.
420  return;
421  }
422  const std::vector<IntegerVariable*>& vars = ct->arguments[1].variables;
423  std::vector<IntegerVariable*> new_vars;
424  for (int64 i = domain.values.front(); i <= domain.values.back(); ++i) {
425  const int64 index = i * mapping.coefficient + mapping.offset - 1;
426  if (index < 0) {
427  return;
428  }
429  if (index >= vars.size()) {
430  break;
431  }
432  new_vars.push_back(vars[index]);
433  }
434  // Rewrite constraint.
435  UpdateRuleStats("array_var_int_element: simplify using affine mapping.");
436  ct->arguments[0].variables[0] = mapping.variable;
437  // TODO(user): Encapsulate argument setters.
438  ct->arguments[1].variables.swap(new_vars);
439  // Mark old index var and affine constraint as presolved out.
440  mapping.constraint->MarkAsInactive();
441  index_var->active = false;
442  } else if (index_var->domain.is_interval &&
443  index_var->domain.values.size() == 2 &&
444  index_var->domain.Max() < ct->arguments[1].variables.size()) {
445  // Reduce array of variables.
446  ct->arguments[1].variables.resize(index_var->domain.Max());
447  UpdateRuleStats("array_var_int_element: reduce array");
448  }
449 }
450 
452  // Should rewrite float constraints.
453  if (absl::GetFlag(FLAGS_fz_floats_are_ints)) {
454  // Treat float variables as int variables, convert constraints to int.
455  for (Constraint* const ct : model->constraints()) {
456  const std::string& id = ct->type;
457  if (id == "int2float") {
458  ct->type = "int_eq";
459  } else if (id == "float_lin_le") {
460  ct->type = "int_lin_le";
461  } else if (id == "float_lin_eq") {
462  ct->type = "int_lin_eq";
463  }
464  }
465  }
466 
467  // Regroup increasing sequence of int_lin_eq([1,..,1,-1], [x1, ..., xn, yn])
468  // into sequence of int_plus(x1, x2, y2), int_plus(y2, x3, y3)...
469  std::vector<IntegerVariable*> current_variables;
470  IntegerVariable* target_variable = nullptr;
471  Constraint* first_constraint = nullptr;
472  for (Constraint* const ct : model->constraints()) {
473  if (target_variable == nullptr) {
474  if (ct->type == "int_lin_eq" && ct->arguments[0].values.size() == 3 &&
475  AreOnesFollowedByMinusOne(ct->arguments[0].values) &&
476  ct->arguments[1].values.empty() && ct->arguments[2].Value() == 0) {
477  FZVLOG << "Recognize assignment " << ct->DebugString() << FZENDL;
478  current_variables = ct->arguments[1].variables;
479  target_variable = current_variables.back();
480  current_variables.pop_back();
481  first_constraint = ct;
482  }
483  } else {
484  if (ct->type == "int_lin_eq" &&
485  AreOnesFollowedByMinusOne(ct->arguments[0].values) &&
486  ct->arguments[0].values.size() == current_variables.size() + 2 &&
487  IsStrictPrefix(current_variables, ct->arguments[1].variables)) {
488  FZVLOG << "Recognize hidden int_plus " << ct->DebugString() << FZENDL;
489  current_variables = ct->arguments[1].variables;
490  // Rewrite ct into int_plus.
491  ct->type = "int_plus";
492  ct->arguments.clear();
493  ct->arguments.push_back(Argument::IntVarRef(target_variable));
494  ct->arguments.push_back(Argument::IntVarRef(
495  current_variables[current_variables.size() - 2]));
496  ct->arguments.push_back(Argument::IntVarRef(current_variables.back()));
497  target_variable = current_variables.back();
498  current_variables.pop_back();
499  FZVLOG << " -> " << ct->DebugString() << FZENDL;
500  // We clean the first constraint too.
501  if (first_constraint != nullptr) {
502  first_constraint = nullptr;
503  }
504  } else {
505  current_variables.clear();
506  target_variable = nullptr;
507  }
508  }
509  }
510 
511  // First pass.
512  for (Constraint* const ct : model->constraints()) {
513  if (ct->active && ct->type == "bool2int") {
514  PresolveBool2Int(ct);
515  } else if (ct->active && ct->type == "int_lin_eq" &&
516  ct->arguments[1].variables.size() == 2 &&
517  ct->strong_propagation) {
518  PresolveStoreAffineMapping(ct);
519  } else if (ct->active && ct->type == "int_lin_eq" &&
520  ct->arguments[1].variables.size() == 3 &&
521  ct->strong_propagation) {
522  PresolveStoreFlatteningMapping(ct);
523  }
524  }
525  if (!var_representative_map_.empty()) {
526  // Some new substitutions were introduced. Let's process them.
527  SubstituteEverywhere(model);
528  var_representative_map_.clear();
529  var_representative_vector_.clear();
530  }
531 
532  // Second pass.
533  for (Constraint* const ct : model->constraints()) {
534  if (ct->type == "array_int_element" || ct->type == "array_bool_element") {
535  PresolveSimplifyElement(ct);
536  }
537  if (ct->type == "array_var_int_element" ||
538  ct->type == "array_var_bool_element") {
539  PresolveSimplifyExprElement(ct);
540  }
541  }
542 
543  // Report presolve rules statistics.
544  if (!successful_rules_.empty()) {
545  for (const auto& rule : successful_rules_) {
546  if (rule.second == 1) {
547  FZLOG << " - rule '" << rule.first << "' was applied 1 time" << FZENDL;
548  } else {
549  FZLOG << " - rule '" << rule.first << "' was applied " << rule.second
550  << " times" << FZENDL;
551  }
552  }
553  }
554 }
555 
556 // ----- Substitution support -----
557 
558 void Presolver::AddVariableSubstitution(IntegerVariable* from,
559  IntegerVariable* to) {
560  CHECK(from != nullptr);
561  CHECK(to != nullptr);
562  // Apply the substitutions, if any.
563  from = FindRepresentativeOfVar(from);
564  to = FindRepresentativeOfVar(to);
565  if (to->temporary) {
566  // Let's switch to keep a non temporary as representative.
567  IntegerVariable* tmp = to;
568  to = from;
569  from = tmp;
570  }
571  if (from != to) {
572  FZVLOG << "Mark " << from->DebugString() << " as equivalent to "
573  << to->DebugString() << FZENDL;
574  CHECK(to->Merge(from->name, from->domain, from->temporary));
575  from->active = false;
576  var_representative_map_[from] = to;
577  var_representative_vector_.push_back(from);
578  }
579 }
580 
581 IntegerVariable* Presolver::FindRepresentativeOfVar(IntegerVariable* var) {
582  if (var == nullptr) return nullptr;
583  IntegerVariable* start_var = var;
584  // First loop: find the top parent.
585  for (;;) {
586  IntegerVariable* parent =
587  gtl::FindWithDefault(var_representative_map_, var, var);
588  if (parent == var) break;
589  var = parent;
590  }
591  // Second loop: attach all the path to the top parent.
592  while (start_var != var) {
593  IntegerVariable* const parent = var_representative_map_[start_var];
594  var_representative_map_[start_var] = var;
595  start_var = parent;
596  }
597  return gtl::FindWithDefault(var_representative_map_, var, var);
598 }
599 
600 void Presolver::SubstituteEverywhere(Model* model) {
601  // Rewrite the constraints.
602  for (Constraint* const ct : model->constraints()) {
603  if (ct != nullptr && ct->active) {
604  for (int i = 0; i < ct->arguments.size(); ++i) {
605  Argument& argument = ct->arguments[i];
606  switch (argument.type) {
609  for (int i = 0; i < argument.variables.size(); ++i) {
610  IntegerVariable* const old_var = argument.variables[i];
611  IntegerVariable* const new_var = FindRepresentativeOfVar(old_var);
612  if (new_var != old_var) {
613  argument.variables[i] = new_var;
614  }
615  }
616  break;
617  }
618  default: {
619  }
620  }
621  }
622  }
623  }
624  // Rewrite the search.
625  for (Annotation* const ann : model->mutable_search_annotations()) {
626  SubstituteAnnotation(ann);
627  }
628  // Rewrite the output.
629  for (SolutionOutputSpecs* const output : model->mutable_output()) {
630  output->variable = FindRepresentativeOfVar(output->variable);
631  for (int i = 0; i < output->flat_variables.size(); ++i) {
632  output->flat_variables[i] =
633  FindRepresentativeOfVar(output->flat_variables[i]);
634  }
635  }
636  // Do not forget to merge domain that could have evolved asynchronously
637  // during presolve.
638  for (const auto& iter : var_representative_map_) {
639  iter.second->domain.IntersectWithDomain(iter.first->domain);
640  }
641 
642  // Change the objective variable.
643  IntegerVariable* const current_objective = model->objective();
644  if (current_objective == nullptr) return;
645  IntegerVariable* const new_objective =
646  FindRepresentativeOfVar(current_objective);
647  if (new_objective != current_objective) {
648  model->SetObjective(new_objective);
649  }
650 }
651 
652 void Presolver::SubstituteAnnotation(Annotation* ann) {
653  // TODO(user): Remove recursion.
654  switch (ann->type) {
657  for (int i = 0; i < ann->annotations.size(); ++i) {
658  SubstituteAnnotation(&ann->annotations[i]);
659  }
660  break;
661  }
664  for (int i = 0; i < ann->variables.size(); ++i) {
665  ann->variables[i] = FindRepresentativeOfVar(ann->variables[i]);
666  }
667  break;
668  }
669  default: {
670  }
671  }
672 }
673 
674 } // namespace fz
675 } // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
#define FZVLOG
#define FZLOG
#define FZENDL
GRBmodel * model
int64_t int64
const int FATAL
Definition: log_severity.h:32
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsArrayBoolean(const std::vector< T > &values)
int index
Definition: pack.cc:508
ABSL_FLAG(bool, fz_floats_are_ints, true, "Interpret floats as integers in all variables and constraints.")
static Argument IntVarRefArray(std::vector< IntegerVariable * > vars)
Definition: model.cc:422
static Argument IntegerList(std::vector< int64 > values)
Definition: model.cc:401
static Argument IntVarRef(IntegerVariable *const var)
Definition: model.cc:415
static Argument IntegerValue(int64 value)
Definition: model.cc:386
std::vector< Argument > arguments
bool Merge(const std::string &other_name, const Domain &other_domain, bool other_temporary)
Definition: model.cc:592