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