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 
29 namespace operations_research {
30 namespace 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:
43  struct ConstraintInfo {
45  double l2_norm = 0.0;
47  double objective_parallelism = 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().
111  void AddAllConstraintsToLp();
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.
231 template <typename Element>
232 class 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?
286 class 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.
295  void TransferToManager(
297  LinearConstraintManager* manager);
298 
299  private:
300  struct CutCandidate {
301  std::string name;
302  LinearConstraint cut;
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 absl::StrongVector< ConstraintIndex, ConstraintInfo > & AllConstraints() const
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="")
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