Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
linear_constraint_manager.h
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstdint>
19#include <string>
20#include <vector>
21
22#include "absl/container/btree_map.h"
23#include "absl/container/flat_hash_map.h"
24#include "absl/strings/string_view.h"
25#include "absl/types/span.h"
29#include "ortools/sat/integer.h"
32#include "ortools/sat/model.h"
35#include "ortools/sat/util.h"
38
39namespace operations_research {
40namespace sat {
41
42// Stores for each IntegerVariable its temporary LP solution.
43//
44// This is shared between all LinearProgrammingConstraint because in the corner
45// case where we have many different LinearProgrammingConstraint and a lot of
46// variable, we could theoretically use up a quadratic amount of memory
47// otherwise.
49 : public util_intops::StrongVector<IntegerVariable, double> {
50 ModelLpValues() = default;
51};
52
53// Same as ModelLpValues for reduced costs.
55 : public util_intops::StrongVector<IntegerVariable, double> {
56 ModelReducedCosts() = default;
57};
58
59// Stores the mapping integer_variable -> glop::ColIndex.
60// This is shared across all LP, which is fine since there are disjoint.
62 : public util_intops::StrongVector<IntegerVariable, glop::ColIndex> {
64};
65
66// Knowing the symmetry of the IP problem should allow us to
67// solve the LP faster via "folding" techniques.
68//
69// You can read this for the LP part: "Dimension Reduction via Colour
70// Refinement", Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal
71// Selman, https://arxiv.org/abs/1307.5697
72//
73// In the presence of symmetry, by considering all symmetric version of a
74// constraint and summing them, we can derive a new constraint using the sum
75// of the variable on each orbit instead of the individual variables.
76//
77// For the integration in a MIP solver, I couldn't find many reference. The way
78// I did it here is to introduce for each orbit a variable representing the
79// sum of the orbit variable. This allows to represent the folded LP in terms
80// of these variables (that are connected to the rest of the solver) and just
81// reuse the full machinery.
82//
83// There are related info in "Orbital Shrinking", Matteo Fischetti & Leo
84// Liberti, https://link.springer.com/chapter/10.1007/978-3-642-32147-4_6
86 public:
88 : shared_stats_(model->GetOrCreate<SharedStatistics>()),
89 integer_trail_(model->GetOrCreate<IntegerTrail>()) {}
91
92 // This must be called with all orbits before we call FoldLinearConstraint().
93 // Note that sum_var MUST not be in any of the orbits. All orbits must also be
94 // disjoint.
95 //
96 // Precondition: All IntegerVariable must be positive.
97 void AddSymmetryOrbit(IntegerVariable sum_var,
98 absl::Span<const IntegerVariable> orbit);
99
100 // If there are no symmetry, we shouldn't bother calling the functions below.
101 // Note that they will still work, but be no-op.
102 bool HasSymmetry() const { return has_symmetry_; }
103
104 // Accessors by orbit index in [0, num_orbits).
105 int NumOrbits() const { return orbits_.size(); }
106 IntegerVariable OrbitSumVar(int i) const { return orbit_sum_vars_[i]; }
107 absl::Span<const IntegerVariable> Orbit(int i) const { return orbits_[i]; }
108
109 // Returns the orbit number in [0, num_orbits) if var belong to a non-trivial
110 // orbit or if it is a "orbit_sum_var". Returns -1 otherwise.
111 int OrbitIndex(IntegerVariable var) const;
112
113 // Returns true iff var is one of the sum_var passed to AddSymmetryOrbit().
114 bool IsOrbitSumVar(IntegerVariable var) const;
115
116 // This will be only true for variable not appearing in any orbit and for
117 // the orbit sum variables.
118 bool AppearInFoldedProblem(IntegerVariable var) const;
119
120 // Given a constraint on the "original" model variables, try to construct a
121 // symmetric version of it using the orbit sum variables. This might fail if
122 // we encounter integer overflow. Returns true on success. On failure, the
123 // original constraints will not be usable.
124 //
125 // Preconditions: All IntegerVariable must be positive. And the constraint
126 // lb/ub must be tight and not +/- int64_t max.
127 bool FoldLinearConstraint(LinearConstraint* ct, bool* folded = nullptr);
128
129 private:
130 SharedStatistics* shared_stats_;
131 IntegerTrail* integer_trail_;
132
133 bool has_symmetry_ = false;
134 int64_t num_overflows_ = 0;
136
137 // We index our vector by positive variable only.
139
140 // Orbit info index by number in [0, num_orbits);
141 std::vector<IntegerVariable> orbit_sum_vars_;
143};
144
145// This class holds a list of globally valid linear constraints and has some
146// logic to decide which one should be part of the LP relaxation. We want more
147// for a better relaxation, but for efficiency we do not want to have too much
148// constraints while solving the LP.
149//
150// This class is meant to contain all the initial constraints of the LP
151// relaxation and to get new cuts as they are generated. Thus, it can both
152// manage cuts but also only add the initial constraints lazily if there is too
153// many of them.
155 public:
157 // Note that this constraint always contains "tight" lb/ub, some of these
158 // bound might be trivial level zero bounds, and one can know this by
159 // looking at lb_is_trivial/ub_is_trivial.
161
162 double l2_norm = 0.0;
164 size_t hash;
165
166 // Updated only for deletable constraints. This is incremented every time
167 // ChangeLp() is called and the constraint is active in the LP or not in the
168 // LP and violated.
169 double active_count = 0.0;
170
171 // TODO(user): This is the number of time the constraint was consecutively
172 // inactive, and go up to 100 with the default param, so we could optimize
173 // the space used more.
174 uint16_t inactive_count = 0;
175
176 // TODO(user): Pack bool and in general optimize the memory of this class.
178 bool is_in_lp = false;
179 bool ub_is_trivial = false;
180 bool lb_is_trivial = false;
181
182 // For now, we mark all the generated cuts as deletable and the problem
183 // constraints as undeletable.
184 // TODO(user): We can have a better heuristics. Some generated good cuts
185 // can be marked undeletable and some unused problem specified constraints
186 // can be marked deletable.
187 bool is_deletable = false;
188 };
189
191 : sat_parameters_(*model->GetOrCreate<SatParameters>()),
192 integer_trail_(*model->GetOrCreate<IntegerTrail>()),
193 time_limit_(model->GetOrCreate<TimeLimit>()),
194 expanded_lp_solution_(*model->GetOrCreate<ModelLpValues>()),
195 expanded_reduced_costs_(*model->GetOrCreate<ModelReducedCosts>()),
196 model_(model),
197 symmetrizer_(model->GetOrCreate<LinearConstraintSymmetrizer>()) {}
199
200 // Add a new constraint to the manager. Note that we canonicalize constraints
201 // and merge the bounds of constraints with the same terms. We also perform
202 // basic preprocessing. If added is given, it will be set to true if this
203 // constraint was actually a new one and to false if it was dominated by an
204 // already existing one.
205 DEFINE_STRONG_INDEX_TYPE(ConstraintIndex);
206 ConstraintIndex Add(LinearConstraint ct, bool* added = nullptr,
207 bool* folded = nullptr);
208
209 // Same as Add(), but logs some information about the newly added constraint.
210 // Cuts are also handled slightly differently than normal constraints.
211 //
212 // Returns true if a new cut was added and false if this cut is not
213 // efficacious or if it is a duplicate of an already existing one.
214 bool AddCut(LinearConstraint ct, std::string type_name,
215 std::string extra_info = "");
216
217 // These must be level zero bounds.
218 bool UpdateConstraintLb(glop::RowIndex index_in_lp, IntegerValue new_lb);
219 bool UpdateConstraintUb(glop::RowIndex index_in_lp, IntegerValue new_ub);
220
221 // The objective is used as one of the criterion to score cuts.
222 // The more a cut is parallel to the objective, the better its score is.
223 //
224 // Currently this should only be called once per IntegerVariable (Checked). It
225 // is easy to support dynamic modification if it becomes needed.
226 void SetObjectiveCoefficient(IntegerVariable var, IntegerValue coeff);
227
228 // Heuristic to decides what LP is best solved next. We use the model lp
229 // solutions as an heuristic, and it should usually be updated with the last
230 // known solution before this call.
231 //
232 // The current solution state is used for detecting inactive constraints. It
233 // is also updated correctly on constraint deletion/addition so that the
234 // simplex can be fully iterative on restart by loading this modified state.
235 //
236 // Returns true iff LpConstraints() will return a different LP than before.
237 bool ChangeLp(glop::BasisState* solution_state,
238 int* num_new_constraints = nullptr);
239
240 // This can be called initially to add all the current constraint to the LP
241 // returned by GetLp().
243
244 // All the constraints managed by this class.
247 return constraint_infos_;
248 }
249
250 // The set of constraints indices in AllConstraints() that should be part
251 // of the next LP to solve.
252 const std::vector<ConstraintIndex>& LpConstraints() const {
253 return lp_constraints_;
254 }
255
256 // To simplify CutGenerator api.
258 return expanded_lp_solution_;
259 }
261 return expanded_reduced_costs_;
262 }
263
264 // Stats.
265 int64_t num_constraints() const { return constraint_infos_.size(); }
266 int64_t num_constraint_updates() const { return num_constraint_updates_; }
267 int64_t num_simplifications() const { return num_simplifications_; }
268 int64_t num_merged_constraints() const { return num_merged_constraints_; }
270 return num_shortened_constraints_;
271 }
272 int64_t num_split_constraints() const { return num_split_constraints_; }
273 int64_t num_coeff_strenghtening() const { return num_coeff_strenghtening_; }
274 int64_t num_cuts() const { return num_cuts_; }
275 int64_t num_add_cut_calls() const { return num_add_cut_calls_; }
276
277 const absl::btree_map<std::string, int>& type_to_num_cuts() const {
278 return type_to_num_cuts_;
279 }
280
281 // If a debug solution has been loaded, this checks if the given constraint
282 // cut it or not. Returns true if and only if everything is fine and the cut
283 // does not violate the loaded solution.
284 bool DebugCheckConstraint(const LinearConstraint& cut);
285
286 // Getter "ReducedCosts" API for cuts.
287 //
288 // It is not possible to set together to true a set of literals 'l' such that
289 // sum_l GetLiteralReducedCost(l) > ReducedCostsGap(). Note that we only
290 // return non-negative "reduced costs" here.
291 absl::int128 ReducedCostsGap() const { return reduced_costs_gap_; }
292 absl::int128 GetLiteralReducedCost(Literal l) const {
293 const auto it = reduced_costs_map_.find(l);
294 if (it == reduced_costs_map_.end()) return 0;
295 return absl::int128(it->second.value());
296 }
297
298 // Reduced cost API for cuts.
299 // These functions allow to clear the data and set the reduced cost info.
301 reduced_costs_gap_ = 0;
302 reduced_costs_map_.clear();
303 }
304 void SetReducedCostsGap(absl::int128 gap) { reduced_costs_gap_ = gap; }
305 void SetLiteralReducedCost(Literal l, IntegerValue coeff) {
306 reduced_costs_map_[l] = coeff;
307 }
308
309 private:
310 // Heuristic that decide which constraints we should remove from the current
311 // LP. Note that such constraints can be added back later by the heuristic
312 // responsible for adding new constraints from the pool.
313 //
314 // Returns true if and only if one or more constraints where removed.
315 //
316 // If the solutions_state is empty, then this function does nothing and
317 // returns false (this is used for tests). Otherwise, the solutions_state is
318 // assumed to correspond to the current LP and to be of the correct size.
319 bool MaybeRemoveSomeInactiveConstraints(glop::BasisState* solution_state);
320
321 // Apply basic inprocessing simplification rules:
322 // - remove fixed variable
323 // - reduce large coefficient (i.e. coeff strenghtenning or big-M reduction).
324 // This uses level-zero bounds.
325 // Returns true if the terms of the constraint changed.
326 bool SimplifyConstraint(LinearConstraint* ct);
327
328 // Helper method to compute objective parallelism for a given constraint. This
329 // also lazily computes objective norm.
330 void ComputeObjectiveParallelism(ConstraintIndex ct_index);
331
332 // Multiplies all active counts and the increment counter by the given
333 // 'scaling_factor'. This should be called when at least one of the active
334 // counts is too high.
335 void RescaleActiveCounts(double scaling_factor);
336
337 // Removes some deletable constraints with low active counts. For now, we
338 // don't remove any constraints which are already in LP.
339 void PermanentlyRemoveSomeConstraints();
340
341 // Make sure the lb/ub are tight and fill lb_is_trivial/ub_is_trivial.
342 void FillDerivedFields(ConstraintInfo* info);
343
344 const SatParameters& sat_parameters_;
345 const IntegerTrail& integer_trail_;
346
347 // Set at true by Add()/SimplifyConstraint() and at false by ChangeLp().
348 bool current_lp_is_changed_ = false;
349
350 // Optimization to avoid calling SimplifyConstraint() when not needed.
351 int64_t last_simplification_timestamp_ = 0;
352
354
355 // The subset of constraints currently in the lp.
356 std::vector<ConstraintIndex> lp_constraints_;
357
358 // We keep a map from the hash of our constraint terms to their position in
359 // constraints_. This is an optimization to detect duplicate constraints. We
360 // are robust to collisions because we always relies on the ground truth
361 // contained in constraints_ and the code is still okay if we do not merge the
362 // constraints.
363 absl::flat_hash_map<size_t, ConstraintIndex> equiv_constraints_;
364
365 // Reduced costs data used by some routing cuts.
366 absl::int128 reduced_costs_gap_ = 0;
367 absl::flat_hash_map<Literal, IntegerValue> reduced_costs_map_;
368
369 int64_t num_constraint_updates_ = 0;
370 int64_t num_simplifications_ = 0;
371 int64_t num_merged_constraints_ = 0;
372 int64_t num_shortened_constraints_ = 0;
373 int64_t num_split_constraints_ = 0;
374 int64_t num_coeff_strenghtening_ = 0;
375
376 int64_t num_cuts_ = 0;
377 int64_t num_add_cut_calls_ = 0;
378 absl::btree_map<std::string, int> type_to_num_cuts_;
379
380 bool objective_is_defined_ = false;
381 bool objective_norm_computed_ = false;
382 double objective_l2_norm_ = 0.0;
383
384 // Total deterministic time spent in this class.
385 double dtime_ = 0.0;
386
387 // Sparse representation of the objective coeffs indexed by positive variables
388 // indices. Important: We cannot use a dense representation here in the corner
389 // case where we have many independent LPs. Alternatively, we could share a
390 // dense vector between all LinearConstraintManager.
391 double sum_of_squared_objective_coeffs_ = 0.0;
392 absl::flat_hash_map<IntegerVariable, double> objective_map_;
393
394 TimeLimit* time_limit_;
395 ModelLpValues& expanded_lp_solution_;
396 ModelReducedCosts& expanded_reduced_costs_;
397 Model* model_;
398 LinearConstraintSymmetrizer* symmetrizer_;
399
400 // We want to decay the active counts of all constraints at each call and
401 // increase the active counts of active/violated constraints. However this can
402 // be too slow in practice. So instead, we keep an increment counter and
403 // update only the active/violated constraints. The counter itself is
404 // increased by a factor at each call. This has the same effect as decaying
405 // all the active counts at each call. This trick is similar to sat clause
406 // management.
407 double constraint_active_count_increase_ = 1.0;
408
409 int32_t num_deletable_constraints_ = 0;
410};
411
412// Before adding cuts to the global pool, it is a classical thing to only keep
413// the top n of a given type during one generation round. This is there to help
414// doing that.
415//
416// TODO(user): Avoid computing efficacity twice.
417// TODO(user): We don't use any orthogonality consideration here.
418// TODO(user): Detect duplicate cuts?
419class TopNCuts {
420 public:
421 explicit TopNCuts(int n) : cuts_(n) {}
422
423 // Adds a cut to the local pool.
424 void AddCut(
425 LinearConstraint ct, absl::string_view name,
427
428 // Empty the local pool and add all its content to the manager.
430
431 private:
432 struct CutCandidate {
433 std::string name;
435 };
436 TopN<CutCandidate, double> cuts_;
437};
438
439} // namespace sat
440} // namespace operations_research
441
442#endif // OR_TOOLS_SAT_LINEAR_CONSTRAINT_MANAGER_H_
ConstraintIndex Add(LinearConstraint ct, bool *added=nullptr, bool *folded=nullptr)
const std::vector< ConstraintIndex > & LpConstraints() const
bool ChangeLp(glop::BasisState *solution_state, int *num_new_constraints=nullptr)
bool AddCut(LinearConstraint ct, std::string type_name, std::string extra_info="")
bool UpdateConstraintUb(glop::RowIndex index_in_lp, IntegerValue new_ub)
bool UpdateConstraintLb(glop::RowIndex index_in_lp, IntegerValue new_lb)
These must be level zero bounds.
const util_intops::StrongVector< ConstraintIndex, ConstraintInfo > & AllConstraints() const
All the constraints managed by this class.
const absl::btree_map< std::string, int > & type_to_num_cuts() const
const util_intops::StrongVector< IntegerVariable, double > & ReducedCosts()
const util_intops::StrongVector< IntegerVariable, double > & LpValues()
To simplify CutGenerator api.
void SetObjectiveCoefficient(IntegerVariable var, IntegerValue coeff)
int NumOrbits() const
Accessors by orbit index in [0, num_orbits).
bool FoldLinearConstraint(LinearConstraint *ct, bool *folded=nullptr)
void AddSymmetryOrbit(IntegerVariable sum_var, absl::Span< const IntegerVariable > orbit)
absl::Span< const IntegerVariable > Orbit(int i) const
bool IsOrbitSumVar(IntegerVariable var) const
Returns true iff var is one of the sum_var passed to AddSymmetryOrbit().
Simple class to add statistics by name and print them at the end.
void TransferToManager(LinearConstraintManager *manager)
Empty the local pool and add all its content to the manager.
void AddCut(LinearConstraint ct, absl::string_view name, const util_intops::StrongVector< IntegerVariable, double > &lp_solution)
Adds a cut to the local pool.
In SWIG mode, we don't want anything besides these top-level includes.
Same as ModelLpValues for reduced costs.