OR-Tools  8.1
cuts.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_CUTS_H_
15 #define OR_TOOLS_SAT_CUTS_H_
16 
17 #include <utility>
18 #include <vector>
19 
20 #include "ortools/base/int_type.h"
22 #include "ortools/sat/integer.h"
23 #include "ortools/sat/intervals.h"
26 #include "ortools/sat/model.h"
28 
29 namespace operations_research {
30 namespace sat {
31 
32 // A "cut" generator on a set of IntegerVariable.
33 //
34 // The generate_cuts() function will usually be called with the current LP
35 // optimal solution (but should work for any lp_values). Note that a
36 // CutGenerator should:
37 // - Only look at the lp_values positions that corresponds to its 'vars' or
38 // their negation.
39 // - Only add cuts in term of the same variables or their negation.
40 struct CutGenerator {
41  std::vector<IntegerVariable> vars;
42  std::function<void(
44  LinearConstraintManager* manager)>
46 };
47 
48 // Given an upper-bounded linear relation (sum terms <= ub), this algorithm
49 // inspects the integer variable appearing in the sum and try to replace each of
50 // them by a tight lower bound (>= coeff * binary + lb) using the implied bound
51 // repository. By tight, we mean that it will take the same value under the
52 // current LP solution.
53 //
54 // We use a class to reuse memory of the tmp terms.
56  public:
57  // We will only replace IntegerVariable appearing in lp_vars_.
58  ImpliedBoundsProcessor(absl::Span<const IntegerVariable> lp_vars_,
59  IntegerTrail* integer_trail,
60  ImpliedBounds* implied_bounds)
61  : lp_vars_(lp_vars_.begin(), lp_vars_.end()),
62  integer_trail_(integer_trail),
63  implied_bounds_(implied_bounds) {}
64 
65  // Processes and updates the given cut.
68  LinearConstraint* cut);
69 
70  // Same as ProcessUpperBoundedConstraint() but instead of just using
71  // var >= coeff * binary + lb we use var == slack + coeff * binary + lb where
72  // slack is a new temporary variable that we create.
73  //
74  // The new slack will be such that slack_infos[(slack - first_slack) / 2]
75  // contains its definition so that we can properly handle it in the cut
76  // generation and substitute it back later.
77  struct SlackInfo {
78  // This slack is equal to sum of terms + offset.
79  std::vector<std::pair<IntegerVariable, IntegerValue>> terms;
80  IntegerValue offset;
81 
82  // The slack bounds and current lp_value.
83  IntegerValue lb = IntegerValue(0);
84  IntegerValue ub = IntegerValue(0);
85  double lp_value = 0.0;
86  };
88  bool substitute_only_inner_variables, IntegerVariable first_slack,
90  LinearConstraint* cut, std::vector<SlackInfo>* slack_infos);
91 
92  // See if some of the implied bounds equation are violated and add them to
93  // the IB cut pool if it is the case.
96 
97  // Only used for debugging.
98  //
99  // Substituting back the slack created by the function above should give
100  // exactly the same cut as the original one.
101  bool DebugSlack(IntegerVariable first_slack,
102  const LinearConstraint& initial_cut,
103  const LinearConstraint& cut,
104  const std::vector<SlackInfo>& info);
105 
106  // Add a new variable that could be used in the new cuts.
107  void AddLpVariable(IntegerVariable var) { lp_vars_.insert(var); }
108 
109  // Must be called before we process any constraints with a different
110  // lp_values or level zero bounds.
111  void ClearCache() const { cache_.clear(); }
112 
114  double bool_lp_value = 0.0;
115  double slack_lp_value = std::numeric_limits<double>::infinity();
117  IntegerValue bound_diff;
118  IntegerVariable bool_var = kNoIntegerVariable;
119  };
121 
122  // As we compute the best implied bounds for each variable, we add violated
123  // cuts here.
124  TopNCuts& IbCutPool() { return ib_cut_pool_; }
125 
126  private:
127  BestImpliedBoundInfo ComputeBestImpliedBound(
128  IntegerVariable var,
130 
131  absl::flat_hash_set<IntegerVariable> lp_vars_;
132  mutable absl::flat_hash_map<IntegerVariable, BestImpliedBoundInfo> cache_;
133 
134  TopNCuts ib_cut_pool_ = TopNCuts(50);
135 
136  // Data from the constructor.
137  IntegerTrail* integer_trail_;
138  ImpliedBounds* implied_bounds_;
139 
140  // Temporary memory used by ProcessUpperBoundedConstraint().
141  mutable std::vector<std::pair<IntegerVariable, IntegerValue>> tmp_terms_;
142 };
143 
144 // Visible for testing. Returns a function f on integers such that:
145 // - f is non-decreasing.
146 // - f is super-additive: f(a) + f(b) <= f(a + b)
147 // - 1 <= f(divisor) <= max_scaling
148 // - For all x, f(x * divisor) = x * f(divisor)
149 // - For all x, f(x * divisor + remainder) = x * f(divisor)
150 //
151 // Preconditions:
152 // - 0 <= remainder < divisor.
153 // - 1 <= max_scaling.
154 //
155 // This is used in IntegerRoundingCut() and is responsible for "strengthening"
156 // the cut. Just taking f(x) = x / divisor result in the non-strengthened cut
157 // and using any function that stricly dominate this one is better.
158 //
159 // Algorithm:
160 // - We first scale by a factor t so that rhs_remainder >= divisor / 2.
161 // - Then, if max_scaling == 2, we use the function described
162 // in "Strenghtening Chvatal-Gomory cuts and Gomory fractional cuts", Adam N.
163 // Letchfrod, Andrea Lodi.
164 // - Otherwise, we use a generalization of this which is a discretized version
165 // of the classical MIR rounding function that only take the value of the
166 // form "an_integer / max_scaling". As max_scaling goes to infinity, this
167 // converge to the real-valued MIR function.
168 //
169 // Note that for each value of max_scaling we will get a different function.
170 // And that there is no dominance relation between any of these functions. So
171 // it could be nice to try to generate a cut using different values of
172 // max_scaling.
173 IntegerValue GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor,
174  IntegerValue max_t);
175 std::function<IntegerValue(IntegerValue)> GetSuperAdditiveRoundingFunction(
176  IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t,
177  IntegerValue max_scaling);
178 
179 // Given an upper bounded linear constraint, this function tries to transform it
180 // to a valid cut that violate the given LP solution using integer rounding.
181 // Note that the returned cut might not always violate the LP solution, in which
182 // case it can be discarded.
183 //
184 // What this does is basically take the integer division of the constraint by an
185 // integer. If the coefficients where doubles, this would be the same as scaling
186 // the constraint and then rounding. We choose the coefficient of the most
187 // fractional variable (rescaled by its coefficient) as the divisor, but there
188 // are other possible alternatives.
189 //
190 // Note that if the constraint is tight under the given lp solution, and if
191 // there is a unique variable not at one of its bounds and fractional, then we
192 // are guaranteed to generate a cut that violate the current LP solution. This
193 // should be the case for Chvatal-Gomory base constraints modulo our loss of
194 // precision while doing exact integer computations.
195 //
196 // Precondition:
197 // - We assumes that the given initial constraint is tight using the given lp
198 // values. This could be relaxed, but for now it should always be the case, so
199 // we log a message and abort if not, to ease debugging.
200 // - The IntegerVariable of the cuts are not used here. We assumes that the
201 // first three vectors are in one to one correspondence with the initial order
202 // of the variable in the cut.
203 //
204 // TODO(user): There is a bunch of heuristic involved here, and we could spend
205 // more effort tunning them. In particular, one can try many heuristics and keep
206 // the best looking cut (or more than one). This is not on the critical code
207 // path, so we can spend more effort in finding good cuts.
209  IntegerValue max_scaling = IntegerValue(60);
210 };
212  public:
213  void ComputeCut(RoundingOptions options, const std::vector<double>& lp_values,
214  const std::vector<IntegerValue>& lower_bounds,
215  const std::vector<IntegerValue>& upper_bounds,
216  ImpliedBoundsProcessor* ib_processor, LinearConstraint* cut);
217 
218  // Returns the number of implied bound lifted Booleans in the last
219  // ComputeCut() call. Useful for investigation.
220  int NumLiftedBooleans() const { return num_lifted_booleans_; }
221 
222  private:
223  // The helper is just here to reuse the memory for these vectors.
224  std::vector<int> relevant_indices_;
225  std::vector<double> relevant_lp_values_;
226  std::vector<IntegerValue> relevant_coeffs_;
227  std::vector<IntegerValue> relevant_bound_diffs_;
228  std::vector<IntegerValue> divisors_;
229  std::vector<std::pair<int, IntegerValue>> adjusted_coeffs_;
230  std::vector<IntegerValue> remainders_;
231  std::vector<bool> change_sign_at_postprocessing_;
232  std::vector<IntegerValue> rs_;
233  std::vector<IntegerValue> best_rs_;
234 
235  int num_lifted_booleans_ = 0;
236  std::vector<std::pair<IntegerVariable, IntegerValue>> tmp_terms_;
237 };
238 
239 // Helper to find knapsack or flow cover cuts (not yet implemented).
241  public:
242  // Try to find a cut with a knapsack heuristic.
243  // If this returns true, you can get the cut via cut().
244  bool TrySimpleKnapsack(const LinearConstraint base_ct,
245  const std::vector<double>& lp_values,
246  const std::vector<IntegerValue>& lower_bounds,
247  const std::vector<IntegerValue>& upper_bounds);
248 
249  // If successful, info about the last generated cut.
250  LinearConstraint* mutable_cut() { return &cut_; }
251  const LinearConstraint& cut() const { return cut_; }
252 
253  // Single line of text that we append to the cut log line.
254  const std::string Info() { return absl::StrCat("lift=", num_lifting_); }
255 
256  private:
257  struct Term {
258  int index;
259  double dist_to_max_value;
260  IntegerValue positive_coeff; // abs(coeff in original constraint).
261  IntegerValue diff;
262  };
263  std::vector<Term> terms_;
264  std::vector<bool> in_cut_;
265 
266  LinearConstraint cut_;
267  int num_lifting_;
268 };
269 
270 // If a variable is away from its upper bound by more than value 1.0, then it
271 // cannot be part of a cover that will violate the lp solution. This method
272 // returns a reduced constraint by removing such variables from the given
273 // constraint.
274 LinearConstraint GetPreprocessedLinearConstraint(
275  const LinearConstraint& constraint,
277  const IntegerTrail& integer_trail);
278 
279 // Returns true if sum of all the variables in the given constraint is less than
280 // or equal to constraint upper bound. This method assumes that all the
281 // coefficients are non negative.
282 bool ConstraintIsTriviallyTrue(const LinearConstraint& constraint,
283  const IntegerTrail& integer_trail);
284 
285 // If the left variables in lp solution satisfies following inequality, we prove
286 // that there does not exist any knapsack cut which is violated by the solution.
287 // Let |Cmin| = smallest possible cover size.
288 // Let S = smallest (var_ub - lp_values[var]) first |Cmin| variables.
289 // Let cut lower bound = sum_(var in S)(var_ub - lp_values[var])
290 // For any cover,
291 // If cut lower bound >= 1
292 // ==> sum_(var in S)(var_ub - lp_values[var]) >= 1
293 // ==> sum_(var in cover)(var_ub - lp_values[var]) >= 1
294 // ==> The solution already satisfies cover. Since this is true for all covers,
295 // this method returns false in such cases.
296 // This method assumes that the constraint is preprocessed and has only non
297 // negative coefficients.
299  const LinearConstraint& preprocessed_constraint,
301  const IntegerTrail& integer_trail);
302 
303 // Struct to help compute upper bound for knapsack instance.
304 struct KnapsackItem {
305  double profit;
306  double weight;
307  bool operator>(const KnapsackItem& other) const {
308  return profit * other.weight > other.profit * weight;
309  }
310 };
311 
312 // Gets upper bound on profit for knapsack instance by solving the linear
313 // relaxation.
314 double GetKnapsackUpperBound(std::vector<KnapsackItem> items, double capacity);
315 
316 // Returns true if the linear relaxation upper bound for the knapsack instance
317 // shows that this constraint cannot be used to form a cut. This method assumes
318 // that all the coefficients are non negative.
320  const LinearConstraint& constraint,
322  const IntegerTrail& integer_trail);
323 
324 // Returns true if the given constraint passes all the filters described above.
325 // This method assumes that the constraint is preprocessed and has only non
326 // negative coefficients.
328  const LinearConstraint& preprocessed_constraint,
330  const IntegerTrail& integer_trail);
331 
332 // Converts the given constraint into canonical knapsack form (described
333 // below) and adds it to 'knapsack_constraints'.
334 // Canonical knapsack form:
335 // - Constraint has finite upper bound.
336 // - All coefficients are positive.
337 // For constraint with finite lower bound, this method also adds the negation of
338 // the given constraint after converting it to canonical knapsack form.
339 void ConvertToKnapsackForm(const LinearConstraint& constraint,
340  std::vector<LinearConstraint>* knapsack_constraints,
341  IntegerTrail* integer_trail);
342 
343 // Returns true if the cut is lifted. Lifting procedure is described below.
344 //
345 // First we decide a lifting sequence for the binary variables which are not
346 // already in cut. We lift the cut for each lifting candidate one by one.
347 //
348 // Given the original constraint where the lifting candidate is fixed to one, we
349 // compute the maximum value the cut can take and still be feasible using a
350 // knapsack problem. We can then lift the variable in the cut using the
351 // difference between the cut upper bound and this maximum value.
352 bool LiftKnapsackCut(
353  const LinearConstraint& constraint,
355  const std::vector<IntegerValue>& cut_vars_original_coefficients,
356  const IntegerTrail& integer_trail, TimeLimit* time_limit,
357  LinearConstraint* cut);
358 
359 // A cut generator that creates knpasack cover cuts.
360 //
361 // For a constraint of type
362 // \sum_{i=1..n}(a_i * x_i) <= b
363 // where x_i are integer variables with upper bound u_i, a cover of size k is a
364 // subset C of {1 , .. , n} such that \sum_{c \in C}(a_c * u_c) > b.
365 //
366 // A knapsack cover cut is a constraint of the form
367 // \sum_{c \in C}(u_c - x_c) >= 1
368 // which is equivalent to \sum_{c \in C}(x_c) <= \sum_{c \in C}(u_c) - 1.
369 // In other words, in a feasible solution, at least some of the variables do
370 // not take their maximum value.
371 //
372 // If all x_i are binary variables then the cover cut becomes
373 // \sum_{c \in C}(x_c) <= |C| - 1.
374 //
375 // The major difficulty for generating Knapsack cover cuts is finding a minimal
376 // cover set C that cut a given floating point solution. There are many ways to
377 // heuristically generate the cover but the following method that uses a
378 // solution of the LP relaxation of the constraint works the best.
379 //
380 // Look at a given linear relaxation solution for the integer problem x'
381 // and try to solve the following knapsack problem:
382 // Minimize \sum_{i=1..n}(z_i * (u_i - x_i')),
383 // such that \sum_{i=1..n}(a_i * u_i * z_i) > b,
384 // where z_i is a binary decision variable and x_i' are values of the variables
385 // in the given relaxation solution x'. If the objective of the optimal solution
386 // of this problem is less than 1, this algorithm does not generate any cuts.
387 // Otherwise, it adds a knapsack cover cut in the form
388 // \sum_{i=1..n}(z_i' * x_i) <= cb,
389 // where z_i' is the value of z_i in the optimal solution of the above
390 // problem and cb is the upper bound for the cut constraint. Note that the above
391 // problem can be converted into a standard kanpsack form by replacing z_i by 1
392 // - y_i. In that case the problem becomes
393 // Maximize \sum_{i=1..n}((u_i - x_i') * (y_i - 1)),
394 // such that
395 // \sum_{i=1..n}(a_i * u_i * y_i) <= \sum_{i=1..n}(a_i * u_i) - b - 1.
396 //
397 // Solving this knapsack instance would help us find the smallest cover with
398 // maximum LP violation.
399 //
400 // Cut strengthning:
401 // Let lambda = \sum_{c \in C}(a_c * u_c) - b and max_coeff = \max_{c
402 // \in C}(a_c), then cut can be strengthened as
403 // \sum_{c \in C}(u_c - x_c) >= ceil(lambda / max_coeff)
404 //
405 // For further information about knapsack cover cuts see
406 // A. Atamtürk, Cover and Pack Inequalities for (Mixed) Integer Programming
407 // Annals of Operations Research Volume 139, Issue 1 , pp 21-38, 2005.
408 // TODO(user): Implement cut lifting.
410  const std::vector<LinearConstraint>& base_constraints,
411  const std::vector<IntegerVariable>& vars, Model* model);
412 
413 // A cut generator for z = x * y (x and y >= 0).
414 CutGenerator CreatePositiveMultiplicationCutGenerator(IntegerVariable z,
415  IntegerVariable x,
416  IntegerVariable y,
417  Model* model);
418 
419 // A cut generator for y = x ^ 2 (x >= 0).
420 // It will dynamically add a linear inequality to push y closer to the parabola.
421 CutGenerator CreateSquareCutGenerator(IntegerVariable y, IntegerVariable x,
422  Model* model);
423 
424 // A cut generator for all_diff(xi). Let the united domain of all xi be D. Sum
425 // of any k-sized subset of xi need to be greater or equal to the sum of
426 // smallest k values in D and lesser or equal to the sum of largest k values in
427 // D. The cut generator first sorts the variables based on LP values and adds
428 // cuts of the form described above if they are violated by lp solution. Note
429 // that all the fixed variables are ignored while generating cuts.
430 CutGenerator CreateAllDifferentCutGenerator(
431  const std::vector<IntegerVariable>& vars, Model* model);
432 
433 // Consider the Lin Max constraint with d expressions and n variables in the
434 // form: target = max {exprs[k] = Sum (wki * xi + bk)}. k in {1,..,d}.
435 // Li = lower bound of xi
436 // Ui = upper bound of xi.
437 // Let zk be in {0,1} for all k in {1,..,d}.
438 // The target = exprs[k] when zk = 1.
439 //
440 // The following is a valid linearization for Lin Max.
441 // target >= exprs[k], for all k in {1,..,d}
442 // target <= Sum (wli * xi) + Sum((Nlk + bk) * zk), for all l in {1,..,d}
443 // Where Nlk is a large number defined as:
444 // Nlk = Sum (max((wki - wli)*Li, (wki - wli)*Ui))
445 // = Sum (max corner difference for variable i, target expr l, max expr k)
446 //
447 // Consider a partition of variables xi into set {1,..,d} as I.
448 // i.e. I(i) = j means xi is mapped to jth index.
449 // The following inequality is valid and sharp cut for the lin max constraint
450 // described above.
451 //
452 // target <= Sum(i=1..n)(wI(i)i * xi + Sum(k=1..d)(MPlusCoefficient_ki * zk))
453 // + Sum(k=1..d)(bk * zk) ,
454 // Where MPlusCoefficient_ki = max((wki - wI(i)i) * Li,
455 // (wki - wI(i)i) * Ui)
456 // = max corner difference for variable i,
457 // target expr I(i), max expr k.
458 //
459 // For detailed proof of validity, refer
460 // Reference: "Strong mixed-integer programming formulations for trained neural
461 // networks" by Ross Anderson et. (https://arxiv.org/pdf/1811.01988.pdf).
462 //
463 // In the cut generator, we compute the most violated partition I by computing
464 // the rhs value (wI(i)i * lp_value(xi) + Sum(k=1..d)(MPlusCoefficient_ki * zk))
465 // for each variable for each partition index. We choose the partition index
466 // that gives lowest rhs value for a given variable.
467 //
468 // Note: This cut generator requires all expressions to contain only positive
469 // vars.
470 CutGenerator CreateLinMaxCutGenerator(
471  const IntegerVariable target, const std::vector<LinearExpression>& exprs,
472  const std::vector<IntegerVariable>& z_vars, Model* model);
473 
474 // For a given set of intervals and demands, we compute the maximum energy of
475 // each task and make sure it is less than the span of the intervals * its
476 // capacity.
477 //
478 // If an interval is optional, it contributes
479 // min_demand * min_size * presence_literal
480 // amount of total energy.
481 //
482 // If an interval is performed, it contributes either min_demand * size or
483 // demand * min_size. We choose the most violated formulation.
484 //
485 // The maximum energy is capacity * span of intervals at level 0.
486 CutGenerator CreateCumulativeCutGenerator(
487  const std::vector<IntervalVariable>& intervals,
488  const IntegerVariable capacity, const std::vector<IntegerVariable>& demands,
489  Model* model);
490 
491 // For a given set of intervals and demands, we first compute the mandatory part
492 // of the interval as [start_max , end_min]. We use this to calculate mandatory
493 // demands for each start_max time points for eligible intervals.
494 // Since the sum of these mandatory demands must be smaller or equal to the
495 // capacity, we create a cut representing that.
496 //
497 // If an interval is optional, it contributes min_demand * presence_literal
498 // amount of demand to the mandatory demands sum. So the final cut is generated
499 // as follows:
500 // sum(demands of always present intervals)
501 // + sum(presence_literal * min_of_demand) <= capacity.
503  const std::vector<IntervalVariable>& intervals,
504  const IntegerVariable capacity, const std::vector<IntegerVariable>& demands,
505  Model* model);
506 
507 // For a given set of intervals, we first compute the min and max of all
508 // intervals. Then we create a cut that indicates that all intervals must fit
509 // in that span.
510 //
511 // If an interval is optional, it contributes min_size * presence_literal
512 // amount of demand to the mandatory demands sum. So the final cut is generated
513 // as follows:
514 // sum(sizes of always present intervals)
515 // + sum(presence_literal * min_of_size) <= span of all intervals.
516 CutGenerator CreateNoOverlapCutGenerator(
517  const std::vector<IntervalVariable>& intervals, Model* model);
518 
519 // For a given set of intervals in a no_overlap constraint, we detect violated
520 // mandatory precedences and create a cut for these.
522  const std::vector<IntervalVariable>& intervals, Model* model);
523 
524 // Extracts the variables that have a Literal view from base variables and
525 // create a generator that will returns constraint of the form "at_most_one"
526 // between such literals.
527 CutGenerator CreateCliqueCutGenerator(
528  const std::vector<IntegerVariable>& base_variables, Model* model);
529 
530 } // namespace sat
531 } // namespace operations_research
532 
533 #endif // OR_TOOLS_SAT_CUTS_H_
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::sat::ImpliedBoundsProcessor::SlackInfo::terms
std::vector< std::pair< IntegerVariable, IntegerValue > > terms
Definition: cuts.h:79
operations_research::sat::IntegerTrail
Definition: integer.h:533
operations_research::sat::kNoIntegerVariable
const IntegerVariable kNoIntegerVariable(-1)
operations_research::sat::CreateAllDifferentCutGenerator
CutGenerator CreateAllDifferentCutGenerator(const std::vector< IntegerVariable > &vars, Model *model)
Definition: cuts.cc:1817
time_limit.h
operations_research::sat::GetFactorT
IntegerValue GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue max_t)
Definition: cuts.cc:615
operations_research::sat::KnapsackItem::profit
double profit
Definition: cuts.h:305
operations_research::sat::CutGenerator
Definition: cuts.h:40
operations_research::sat::CreateCliqueCutGenerator
CutGenerator CreateCliqueCutGenerator(const std::vector< IntegerVariable > &base_variables, Model *model)
Definition: cuts.cc:2410
operations_research::sat::CoverCutHelper::mutable_cut
LinearConstraint * mutable_cut()
Definition: cuts.h:250
linear_constraint.h
operations_research::sat::CanBeFilteredUsingKnapsackUpperBound
bool CanBeFilteredUsingKnapsackUpperBound(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
Definition: cuts.cc:335
operations_research::sat::ImpliedBoundsProcessor::SlackInfo::ub
IntegerValue ub
Definition: cuts.h:84
operations_research::sat::CoverCutHelper::TrySimpleKnapsack
bool TrySimpleKnapsack(const LinearConstraint base_ct, const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds)
Definition: cuts.cc:1154
model.h
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::sat::CreateNoOverlapPrecedenceCutGenerator
CutGenerator CreateNoOverlapPrecedenceCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
Definition: cuts.cc:2347
operations_research::sat::ImpliedBoundsProcessor::SlackInfo::lp_value
double lp_value
Definition: cuts.h:85
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo
Definition: cuts.h:113
operations_research::sat::ImpliedBoundsProcessor::SeparateSomeImpliedBoundCuts
void SeparateSomeImpliedBoundCuts(const absl::StrongVector< IntegerVariable, double > &lp_values)
Definition: cuts.cc:1574
operations_research::sat::ImpliedBoundsProcessor::ImpliedBoundsProcessor
ImpliedBoundsProcessor(absl::Span< const IntegerVariable > lp_vars_, IntegerTrail *integer_trail, ImpliedBounds *implied_bounds)
Definition: cuts.h:58
operations_research::sat::ConvertToKnapsackForm
void ConvertToKnapsackForm(const LinearConstraint &constraint, std::vector< LinearConstraint > *knapsack_constraints, IntegerTrail *integer_trail)
Definition: cuts.cc:387
operations_research::TimeLimit
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
index
int index
Definition: pack.cc:508
operations_research::sat::ImpliedBoundsProcessor
Definition: cuts.h:55
operations_research::sat::CreateSquareCutGenerator
CutGenerator CreateSquareCutGenerator(IntegerVariable y, IntegerVariable x, Model *model)
Definition: cuts.cc:1423
operations_research::sat::CanBeFilteredUsingCutLowerBound
bool CanBeFilteredUsingCutLowerBound(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
Definition: cuts.cc:289
operations_research::sat::LinearConstraintManager
Definition: linear_constraint_manager.h:40
operations_research::sat::LiftKnapsackCut
bool LiftKnapsackCut(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const std::vector< IntegerValue > &cut_vars_original_coefficients, const IntegerTrail &integer_trail, TimeLimit *time_limit, LinearConstraint *cut)
Definition: cuts.cc:171
operations_research::sat::LinearConstraint
Definition: linear_constraint.h:39
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo::slack_lp_value
double slack_lp_value
Definition: cuts.h:115
operations_research::sat::CreateOverlappingCumulativeCutGenerator
CutGenerator CreateOverlappingCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
Definition: cuts.cc:2216
time_limit
SharedTimeLimit * time_limit
Definition: cp_model_solver.cc:2103
operations_research::sat::RoundingOptions
Definition: cuts.h:208
int_type.h
intervals.h
operations_research::sat::ImpliedBoundsProcessor::ProcessUpperBoundedConstraintWithSlackCreation
void ProcessUpperBoundedConstraintWithSlackCreation(bool substitute_only_inner_variables, IntegerVariable first_slack, const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraint *cut, std::vector< SlackInfo > *slack_infos)
Definition: cuts.cc:1583
operations_research::sat::ImpliedBoundsProcessor::IbCutPool
TopNCuts & IbCutPool()
Definition: cuts.h:124
operations_research::sat::CreateLinMaxCutGenerator
CutGenerator CreateLinMaxCutGenerator(const IntegerVariable target, const std::vector< LinearExpression > &exprs, const std::vector< IntegerVariable > &z_vars, Model *model)
Definition: cuts.cc:1914
operations_research::sat::RoundingOptions::max_scaling
IntegerValue max_scaling
Definition: cuts.h:209
operations_research::sat::CreateNoOverlapCutGenerator
CutGenerator CreateNoOverlapCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
Definition: cuts.cc:2330
operations_research::sat::IntegerRoundingCutHelper
Definition: cuts.h:211
operations_research::sat::TopNCuts
Definition: linear_constraint_manager.h:280
operations_research::sat::ImpliedBounds
Definition: implied_bounds.h:77
operations_research::sat::CanFormValidKnapsackCover
bool CanFormValidKnapsackCover(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
Definition: cuts.cc:369
operations_research::sat::CreatePositiveMultiplicationCutGenerator
CutGenerator CreatePositiveMultiplicationCutGenerator(IntegerVariable z, IntegerVariable x, IntegerVariable y, Model *model)
Definition: cuts.cc:1327
implied_bounds.h
operations_research::sat::ImpliedBoundsProcessor::GetCachedImpliedBoundInfo
BestImpliedBoundInfo GetCachedImpliedBoundInfo(IntegerVariable var)
Definition: cuts.cc:1499
model
GRBmodel * model
Definition: gurobi_interface.cc:269
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo::bool_lp_value
double bool_lp_value
Definition: cuts.h:114
operations_research::sat::ImpliedBoundsProcessor::ProcessUpperBoundedConstraint
void ProcessUpperBoundedConstraint(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraint *cut)
Definition: cuts.cc:1490
operations_research::sat::GetSuperAdditiveRoundingFunction
std::function< IntegerValue(IntegerValue)> GetSuperAdditiveRoundingFunction(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t, IntegerValue max_scaling)
Definition: cuts.cc:623
operations_research::sat::ImpliedBoundsProcessor::AddLpVariable
void AddLpVariable(IntegerVariable var)
Definition: cuts.h:107
absl::StrongVector< IntegerVariable, double >
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo::bound_diff
IntegerValue bound_diff
Definition: cuts.h:117
linear_constraint_manager.h
operations_research::sat::GetPreprocessedLinearConstraint
LinearConstraint GetPreprocessedLinearConstraint(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
Definition: cuts.cc:249
operations_research::sat::CutGenerator::generate_cuts
std::function< void(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraintManager *manager)> generate_cuts
Definition: cuts.h:45
operations_research::sat::CoverCutHelper::cut
const LinearConstraint & cut() const
Definition: cuts.h:251
operations_research::sat::KnapsackItem::weight
double weight
Definition: cuts.h:306
lower_bounds
std::vector< double > lower_bounds
Definition: sat/lp_utils.cc:498
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo::bool_var
IntegerVariable bool_var
Definition: cuts.h:118
operations_research::sat::ImpliedBoundsProcessor::SlackInfo
Definition: cuts.h:77
operations_research::sat::ImpliedBoundsProcessor::ClearCache
void ClearCache() const
Definition: cuts.h:111
operations_research::sat::IntegerRoundingCutHelper::ComputeCut
void ComputeCut(RoundingOptions options, const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds, ImpliedBoundsProcessor *ib_processor, LinearConstraint *cut)
Definition: cuts.cc:706
operations_research::sat::ImpliedBoundsProcessor::DebugSlack
bool DebugSlack(IntegerVariable first_slack, const LinearConstraint &initial_cut, const LinearConstraint &cut, const std::vector< SlackInfo > &info)
Definition: cuts.cc:1724
operations_research::sat::GetKnapsackUpperBound
double GetKnapsackUpperBound(std::vector< KnapsackItem > items, const double capacity)
Definition: cuts.cc:317
operations_research::sat::CutGenerator::vars
std::vector< IntegerVariable > vars
Definition: cuts.h:41
operations_research::sat::CreateCumulativeCutGenerator
CutGenerator CreateCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
Definition: cuts.cc:2197
capacity
int64 capacity
Definition: routing_flow.cc:129
operations_research::sat::CoverCutHelper::Info
const std::string Info()
Definition: cuts.h:254
operations_research::sat::CoverCutHelper
Definition: cuts.h:240
operations_research::sat::ImpliedBoundsProcessor::BestImpliedBoundInfo::is_positive
bool is_positive
Definition: cuts.h:116
operations_research::sat::KnapsackItem
Definition: cuts.h:304
operations_research::sat::ImpliedBoundsProcessor::SlackInfo::offset
IntegerValue offset
Definition: cuts.h:80
operations_research::sat::IntegerRoundingCutHelper::NumLiftedBooleans
int NumLiftedBooleans() const
Definition: cuts.h:220
upper_bounds
std::vector< double > upper_bounds
Definition: sat/lp_utils.cc:499
operations_research::sat::CreateKnapsackCoverCutGenerator
CutGenerator CreateKnapsackCoverCutGenerator(const std::vector< LinearConstraint > &base_constraints, const std::vector< IntegerVariable > &vars, Model *model)
Definition: cuts.cc:436
operations_research::sat::KnapsackItem::operator>
bool operator>(const KnapsackItem &other) const
Definition: cuts.h:307
operations_research::sat::ImpliedBoundsProcessor::SlackInfo::lb
IntegerValue lb
Definition: cuts.h:83
operations_research::sat::ConstraintIsTriviallyTrue
bool ConstraintIsTriviallyTrue(const LinearConstraint &constraint, const IntegerTrail &integer_trail)
Definition: cuts.cc:273
integer.h