OR-Tools  8.2
linear_constraint_manager.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_SAT_LINEAR_CONSTRAINT_MANAGER_H_
15#define OR_TOOLS_SAT_LINEAR_CONSTRAINT_MANAGER_H_
16
17#include <cstddef>
18#include <vector>
19
20#include "absl/container/flat_hash_map.h"
21#include "absl/container/flat_hash_set.h"
25#include "ortools/sat/model.h"
26#include "ortools/sat/sat_parameters.pb.h"
28
29namespace operations_research {
30namespace sat {
31
32// This class holds a list of globally valid linear constraints and has some
33// logic to decide which one should be part of the LP relaxation. We want more
34// for a better relaxation, but for efficiency we do not want to have too much
35// constraints while solving the LP.
36//
37// This class is meant to contain all the initial constraints of the LP
38// relaxation and to get new cuts as they are generated. Thus, it can both
39// manage cuts but also only add the initial constraints lazily if there is too
40// many of them.
42 public:
45 double l2_norm = 0.0;
49 bool is_in_lp = false;
50 size_t hash;
51 double current_score = 0.0;
52
53 // Updated only for deletable constraints. This is incremented every time
54 // ChangeLp() is called and the constraint is active in the LP or not in the
55 // LP and violated.
56 double active_count = 0.0;
57
58 // For now, we mark all the generated cuts as deletable and the problem
59 // constraints as undeletable.
60 // TODO(user): We can have a better heuristics. Some generated good cuts
61 // can be marked undeletable and some unused problem specified constraints
62 // can be marked deletable.
63 bool is_deletable = false;
64 };
65
67 : sat_parameters_(*model->GetOrCreate<SatParameters>()),
68 integer_trail_(*model->GetOrCreate<IntegerTrail>()),
69 time_limit_(model->GetOrCreate<TimeLimit>()),
70 model_(model) {}
72
73 // Add a new constraint to the manager. Note that we canonicalize constraints
74 // and merge the bounds of constraints with the same terms. We also perform
75 // basic preprocessing. If added is given, it will be set to true if this
76 // constraint was actually a new one and to false if it was dominated by an
77 // already existing one.
78 DEFINE_INT_TYPE(ConstraintIndex, int32);
79 ConstraintIndex Add(LinearConstraint ct, bool* added = nullptr);
80
81 // Same as Add(), but logs some information about the newly added constraint.
82 // Cuts are also handled slightly differently than normal constraints.
83 //
84 // Returns true if a new cut was added and false if this cut is not
85 // efficacious or if it is a duplicate of an already existing one.
86 bool AddCut(LinearConstraint ct, std::string type_name,
88 std::string extra_info = "");
89
90 // The objective is used as one of the criterion to score cuts.
91 // The more a cut is parallel to the objective, the better its score is.
92 //
93 // Currently this should only be called once per IntegerVariable (Checked). It
94 // is easy to support dynamic modification if it becomes needed.
95 void SetObjectiveCoefficient(IntegerVariable var, IntegerValue coeff);
96
97 // Heuristic to decides what LP is best solved next. The given lp_solution
98 // should usually be the optimal solution of the LP returned by GetLp() before
99 // this call, but is just used as an heuristic.
100 //
101 // The current solution state is used for detecting inactive constraints. It
102 // is also updated correctly on constraint deletion/addition so that the
103 // simplex can be fully iterative on restart by loading this modified state.
104 //
105 // Returns true iff LpConstraints() will return a different LP than before.
107 glop::BasisState* solution_state);
108
109 // This can be called initially to add all the current constraint to the LP
110 // returned by GetLp().
112
113 // All the constraints managed by this class.
115 const {
116 return constraint_infos_;
117 }
118
119 // The set of constraints indices in AllConstraints() that should be part
120 // of the next LP to solve.
121 const std::vector<ConstraintIndex>& LpConstraints() const {
122 return lp_constraints_;
123 }
124
125 int64 num_cuts() const { return num_cuts_; }
126 int64 num_shortened_constraints() const { return num_shortened_constraints_; }
127 int64 num_coeff_strenghtening() const { return num_coeff_strenghtening_; }
128
129 // If a debug solution has been loaded, this checks if the given constaint cut
130 // it or not. Returns true iff everything is fine and the cut does not violate
131 // the loaded solution.
132 bool DebugCheckConstraint(const LinearConstraint& cut);
133
134 private:
135 // Heuristic that decide which constraints we should remove from the current
136 // LP. Note that such constraints can be added back later by the heuristic
137 // responsible for adding new constraints from the pool.
138 //
139 // Returns true iff one or more constraints where removed.
140 //
141 // If the solutions_state is empty, then this function does nothing and
142 // returns false (this is used for tests). Otherwise, the solutions_state is
143 // assumed to correspond to the current LP and to be of the correct size.
144 bool MaybeRemoveSomeInactiveConstraints(glop::BasisState* solution_state);
145
146 // Apply basic inprocessing simplification rules:
147 // - remove fixed variable
148 // - reduce large coefficient (i.e. coeff strenghtenning or big-M reduction).
149 // This uses level-zero bounds.
150 // Returns true if the terms of the constraint changed.
151 bool SimplifyConstraint(LinearConstraint* ct);
152
153 // Helper method to compute objective parallelism for a given constraint. This
154 // also lazily computes objective norm.
155 void ComputeObjectiveParallelism(const ConstraintIndex ct_index);
156
157 // Multiplies all active counts and the increment counter by the given
158 // 'scaling_factor'. This should be called when at least one of the active
159 // counts is too high.
160 void RescaleActiveCounts(double scaling_factor);
161
162 // Removes some deletable constraints with low active counts. For now, we
163 // don't remove any constraints which are already in LP.
164 void PermanentlyRemoveSomeConstraints();
165
166 const SatParameters& sat_parameters_;
167 const IntegerTrail& integer_trail_;
168
169 // Set at true by Add()/SimplifyConstraint() and at false by ChangeLp().
170 bool current_lp_is_changed_ = false;
171
172 // Optimization to avoid calling SimplifyConstraint() when not needed.
173 int64 last_simplification_timestamp_ = 0;
174
176
177 // The subset of constraints currently in the lp.
178 std::vector<ConstraintIndex> lp_constraints_;
179
180 // We keep a map from the hash of our constraint terms to their position in
181 // constraints_. This is an optimization to detect duplicate constraints. We
182 // are robust to collisions because we always relies on the ground truth
183 // contained in constraints_ and the code is still okay if we do not merge the
184 // constraints.
185 absl::flat_hash_map<size_t, ConstraintIndex> equiv_constraints_;
186
187 int64 num_simplifications_ = 0;
188 int64 num_merged_constraints_ = 0;
189 int64 num_shortened_constraints_ = 0;
190 int64 num_splitted_constraints_ = 0;
191 int64 num_coeff_strenghtening_ = 0;
192
193 int64 num_cuts_ = 0;
194 int64 num_add_cut_calls_ = 0;
195 std::map<std::string, int> type_to_num_cuts_;
196
197 bool objective_is_defined_ = false;
198 bool objective_norm_computed_ = false;
199 double objective_l2_norm_ = 0.0;
200
201 // Total deterministic time spent in this class.
202 double dtime_ = 0.0;
203
204 // Sparse representation of the objective coeffs indexed by positive variables
205 // indices. Important: We cannot use a dense representation here in the corner
206 // case where we have many indepedent LPs. Alternatively, we could share a
207 // dense vector between all LinearConstraintManager.
208 double sum_of_squared_objective_coeffs_ = 0.0;
209 absl::flat_hash_map<IntegerVariable, double> objective_map_;
210
211 TimeLimit* time_limit_;
212 Model* model_;
213
214 // We want to decay the active counts of all constraints at each call and
215 // increase the active counts of active/violated constraints. However this can
216 // be too slow in practice. So instead, we keep an increment counter and
217 // update only the active/violated constraints. The counter itself is
218 // increased by a factor at each call. This has the same effect as decaying
219 // all the active counts at each call. This trick is similar to sat clause
220 // management.
221 double constraint_active_count_increase_ = 1.0;
222
223 int32 num_deletable_constraints_ = 0;
224};
225
226// Keep the top n elements from a stream of elements.
227//
228// TODO(user): We could use gtl::TopN when/if it gets open sourced. Note that
229// we might be slighlty faster here since we use an indirection and don't move
230// the Element class around as much.
231template <typename Element>
232class TopN {
233 public:
234 explicit TopN(int n) : n_(n) {}
235
236 void Clear() {
237 heap_.clear();
238 elements_.clear();
239 }
240
241 void Add(Element e, double score) {
242 if (heap_.size() < n_) {
243 const int index = elements_.size();
244 heap_.push_back({index, score});
245 elements_.push_back(std::move(e));
246 if (heap_.size() == n_) {
247 // TODO(user): We could delay that on the n + 1 push.
248 std::make_heap(heap_.begin(), heap_.end());
249 }
250 } else {
251 if (score <= heap_.front().score) return;
252 const int index_to_replace = heap_.front().index;
253 elements_[index_to_replace] = std::move(e);
254
255 // If needed, we could be faster here with an update operation.
256 std::pop_heap(heap_.begin(), heap_.end());
257 heap_.back() = {index_to_replace, score};
258 std::push_heap(heap_.begin(), heap_.end());
259 }
260 }
261
262 const std::vector<Element>& UnorderedElements() const { return elements_; }
263
264 private:
265 const int n_;
266
267 // We keep a heap of the n lowest score.
268 struct HeapElement {
269 int index; // in elements_;
270 double score;
271 const double operator<(const HeapElement& other) const {
272 return score > other.score;
273 }
274 };
275 std::vector<HeapElement> heap_;
276 std::vector<Element> elements_;
277};
278
279// Before adding cuts to the global pool, it is a classical thing to only keep
280// the top n of a given type during one generation round. This is there to help
281// doing that.
282//
283// TODO(user): Avoid computing efficacity twice.
284// TODO(user): We don't use any orthogonality consideration here.
285// TODO(user): Detect duplicate cuts?
286class TopNCuts {
287 public:
288 explicit TopNCuts(int n) : cuts_(n) {}
289
290 // Add a cut to the local pool
291 void AddCut(LinearConstraint ct, const std::string& name,
293
294 // Empty the local pool and add all its content to the manager.
297 LinearConstraintManager* manager);
298
299 private:
300 struct CutCandidate {
301 std::string name;
303 };
304 TopN<CutCandidate> cuts_;
305};
306
307} // namespace sat
308} // namespace operations_research
309
310#endif // OR_TOOLS_SAT_LINEAR_CONSTRAINT_MANAGER_H_
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
bool ChangeLp(const absl::StrongVector< IntegerVariable, double > &lp_solution, glop::BasisState *solution_state)
void SetObjectiveCoefficient(IntegerVariable var, IntegerValue coeff)
ConstraintIndex Add(LinearConstraint ct, bool *added=nullptr)
const std::vector< ConstraintIndex > & LpConstraints() const
bool AddCut(LinearConstraint ct, std::string type_name, const absl::StrongVector< IntegerVariable, double > &lp_solution, std::string extra_info="")
const absl::StrongVector< ConstraintIndex, ConstraintInfo > & AllConstraints() const
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
void AddCut(LinearConstraint ct, const std::string &name, const absl::StrongVector< IntegerVariable, double > &lp_solution)
void TransferToManager(const absl::StrongVector< IntegerVariable, double > &lp_solution, LinearConstraintManager *manager)
const std::vector< Element > & UnorderedElements() const
void Add(Element e, double score)
const std::string name
const Constraint * ct
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int int32
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508