OR-Tools  8.2
presolve.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_FLATZINC_PRESOLVE_H_
15#define OR_TOOLS_FLATZINC_PRESOLVE_H_
16
17#include <functional>
18#include <string>
19
20#include "absl/container/flat_hash_map.h"
21#include "absl/container/flat_hash_set.h"
22#include "absl/strings/match.h"
23#include "ortools/base/hash.h"
27
28namespace operations_research {
29namespace fz {
30// The Presolver "pre-solves" a Model by applying some iterative
31// transformations to it, which may simplify and/or shrink the model.
32//
33// TODO(user): Error reporting of unfeasible models.
34class Presolver {
35 public:
36 // Recursively apply all the pre-solve rules to the model, until exhaustion.
37 // The reduced model will:
38 // - Have some unused variables.
39 // - Have some unused constraints (marked as inactive).
40 // - Have some modified constraints (for example, they will no longer
41 // refer to unused variables).
42 void Run(Model* model);
43
44 private:
45 // This struct stores the affine mapping of one variable:
46 // it represents new_var = var * coefficient + offset. It also stores the
47 // constraint that defines this mapping.
48 struct AffineMapping {
49 IntegerVariable* variable;
51 int64 offset;
52 Constraint* constraint;
53
54 AffineMapping()
55 : variable(nullptr), coefficient(0), offset(0), constraint(nullptr) {}
56 AffineMapping(IntegerVariable* v, int64 c, int64 o, Constraint* ct)
57 : variable(v), coefficient(c), offset(o), constraint(ct) {}
58 };
59
60 // This struct stores the mapping of two index variables (of a 2D array; not
61 // included here) onto a single index variable (of the flattened 1D array).
62 // The original 2D array could be trimmed in the process; so we also need an
63 // offset.
64 // Eg. new_index_var = index_var1 * int_coeff + index_var2 + int_offset
65 struct Array2DIndexMapping {
66 IntegerVariable* variable1;
68 IntegerVariable* variable2;
69 int64 offset;
70 Constraint* constraint;
71
72 Array2DIndexMapping()
73 : variable1(nullptr),
74 coefficient(0),
75 variable2(nullptr),
76 offset(0),
77 constraint(nullptr) {}
78 Array2DIndexMapping(IntegerVariable* v1, int64 c, IntegerVariable* v2,
80 : variable1(v1),
81 coefficient(c),
82 variable2(v2),
83 offset(o),
84 constraint(ct) {}
85 };
86
87 // Substitution support.
88 void SubstituteEverywhere(Model* model);
89 void SubstituteAnnotation(Annotation* ann);
90
91 // Presolve rules.
92 void PresolveBool2Int(Constraint* ct);
93 void PresolveStoreAffineMapping(Constraint* ct);
94 void PresolveStoreFlatteningMapping(Constraint* ct);
95 void PresolveSimplifyElement(Constraint* ct);
96 void PresolveSimplifyExprElement(Constraint* ct);
97
98 // Helpers.
99 void UpdateRuleStats(const std::string& rule_name) {
100 successful_rules_[rule_name]++;
101 }
102
103 // The presolver will discover some equivalence classes of variables [two
104 // variable are equivalent when replacing one by the other leads to the same
105 // logical model]. We will store them here, using a Union-find data structure.
106 // See http://en.wikipedia.org/wiki/Disjoint-set_data_structure.
107 // Note that the equivalence is directed. We prefer to replace all instances
108 // of 'from' with 'to', rather than the opposite.
109 void AddVariableSubstitution(IntegerVariable* from, IntegerVariable* to);
110 IntegerVariable* FindRepresentativeOfVar(IntegerVariable* var);
111 absl::flat_hash_map<const IntegerVariable*, IntegerVariable*>
112 var_representative_map_;
113 std::vector<IntegerVariable*> var_representative_vector_;
114
115 // Stores affine_map_[x] = a * y + b.
116 absl::flat_hash_map<const IntegerVariable*, AffineMapping> affine_map_;
117
118 // Stores array2d_index_map_[z] = a * x + y + b.
119 absl::flat_hash_map<const IntegerVariable*, Array2DIndexMapping>
120 array2d_index_map_;
121
122 // Count applications of presolve rules. Use a sorted map for reporting
123 // purposes.
124 std::map<std::string, int> successful_rules_;
125};
126} // namespace fz
127} // namespace operations_research
128
129#endif // OR_TOOLS_FLATZINC_PRESOLVE_H_
const Constraint * ct
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 coefficient