14 #ifndef OR_TOOLS_SAT_CUTS_H_
15 #define OR_TOOLS_SAT_CUTS_H_
42 std::vector<IntegerVariable>
vars;
62 : lp_vars_(lp_vars_.begin(), lp_vars_.end()),
63 integer_trail_(integer_trail),
64 implied_bounds_(implied_bounds) {}
80 std::vector<std::pair<IntegerVariable, IntegerValue>>
terms;
84 IntegerValue
lb = IntegerValue(0);
85 IntegerValue
ub = IntegerValue(0);
89 bool substitute_only_inner_variables, IntegerVariable first_slack,
105 const std::vector<SlackInfo>& info);
128 BestImpliedBoundInfo ComputeBestImpliedBound(
132 absl::flat_hash_set<IntegerVariable> lp_vars_;
133 mutable absl::flat_hash_map<IntegerVariable, BestImpliedBoundInfo> cache_;
142 mutable std::vector<std::pair<IntegerVariable, IntegerValue>> tmp_terms_;
174 IntegerValue
GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor,
177 IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t,
178 IntegerValue max_scaling);
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_;
236 int num_lifted_booleans_ = 0;
237 std::vector<std::pair<IntegerVariable, IntegerValue>> tmp_terms_;
246 const std::vector<double>& lp_values,
255 const std::string
Info() {
return absl::StrCat(
"lift=", num_lifting_); }
260 double dist_to_max_value;
261 IntegerValue positive_coeff;
264 std::vector<Term> terms_;
265 std::vector<bool> in_cut_;
267 LinearConstraint cut_;
276 const LinearConstraint& constraint,
278 const IntegerTrail& integer_trail);
284 const IntegerTrail& integer_trail);
300 const LinearConstraint& preprocessed_constraint,
302 const IntegerTrail& integer_trail);
321 const LinearConstraint& constraint,
323 const IntegerTrail& integer_trail);
329 const LinearConstraint& preprocessed_constraint,
331 const IntegerTrail& integer_trail);
341 std::vector<LinearConstraint>* knapsack_constraints,
342 IntegerTrail* integer_trail);
354 const LinearConstraint& constraint,
356 const std::vector<IntegerValue>& cut_vars_original_coefficients,
358 LinearConstraint* cut);
411 const std::vector<LinearConstraint>& base_constraints,
412 const std::vector<IntegerVariable>& vars, Model*
model);
432 const std::vector<IntegerVariable>& vars, Model*
model);
472 const IntegerVariable target,
const std::vector<LinearExpression>& exprs,
473 const std::vector<IntegerVariable>& z_vars, Model*
model);
488 const std::vector<IntervalVariable>& intervals,
489 const IntegerVariable
capacity,
const std::vector<IntegerVariable>& demands,
504 const std::vector<IntervalVariable>& intervals,
505 const IntegerVariable
capacity,
const std::vector<IntegerVariable>& demands,
518 const std::vector<IntervalVariable>& intervals, Model*
model);
523 const std::vector<IntervalVariable>& intervals, Model*
model);
529 const std::vector<IntegerVariable>& base_variables, Model*
model);
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
const LinearConstraint & cut() const
LinearConstraint * mutable_cut()
bool TrySimpleKnapsack(const LinearConstraint base_ct, const std::vector< double > &lp_values, const std::vector< IntegerValue > &lower_bounds, const std::vector< IntegerValue > &upper_bounds)
void AddLpVariable(IntegerVariable var)
void ProcessUpperBoundedConstraintWithSlackCreation(bool substitute_only_inner_variables, IntegerVariable first_slack, const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraint *cut, std::vector< SlackInfo > *slack_infos)
void ProcessUpperBoundedConstraint(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraint *cut)
bool DebugSlack(IntegerVariable first_slack, const LinearConstraint &initial_cut, const LinearConstraint &cut, const std::vector< SlackInfo > &info)
BestImpliedBoundInfo GetCachedImpliedBoundInfo(IntegerVariable var)
ImpliedBoundsProcessor(absl::Span< const IntegerVariable > lp_vars_, IntegerTrail *integer_trail, ImpliedBounds *implied_bounds)
void SeparateSomeImpliedBoundCuts(const absl::StrongVector< IntegerVariable, double > &lp_values)
int NumLiftedBooleans() const
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)
SharedTimeLimit * time_limit
void ConvertToKnapsackForm(const LinearConstraint &constraint, std::vector< LinearConstraint > *knapsack_constraints, IntegerTrail *integer_trail)
LinearConstraint GetPreprocessedLinearConstraint(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
CutGenerator CreateNoOverlapPrecedenceCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
bool CanFormValidKnapsackCover(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
CutGenerator CreateCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
CutGenerator CreateNoOverlapCutGenerator(const std::vector< IntervalVariable > &intervals, Model *model)
IntegerValue GetFactorT(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue max_t)
double GetKnapsackUpperBound(std::vector< KnapsackItem > items, const double capacity)
CutGenerator CreateOverlappingCumulativeCutGenerator(const std::vector< IntervalVariable > &intervals, const IntegerVariable capacity, const std::vector< IntegerVariable > &demands, Model *model)
CutGenerator CreateSquareCutGenerator(IntegerVariable y, IntegerVariable x, Model *model)
bool CanBeFilteredUsingCutLowerBound(const LinearConstraint &preprocessed_constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
const IntegerVariable kNoIntegerVariable(-1)
CutGenerator CreateLinMaxCutGenerator(const IntegerVariable target, const std::vector< LinearExpression > &exprs, const std::vector< IntegerVariable > &z_vars, Model *model)
CutGenerator CreateAllDifferentCutGenerator(const std::vector< IntegerVariable > &vars, Model *model)
bool CanBeFilteredUsingKnapsackUpperBound(const LinearConstraint &constraint, const absl::StrongVector< IntegerVariable, double > &lp_values, const IntegerTrail &integer_trail)
std::function< IntegerValue(IntegerValue)> GetSuperAdditiveRoundingFunction(IntegerValue rhs_remainder, IntegerValue divisor, IntegerValue t, IntegerValue max_scaling)
CutGenerator CreateKnapsackCoverCutGenerator(const std::vector< LinearConstraint > &base_constraints, const std::vector< IntegerVariable > &vars, Model *model)
bool ConstraintIsTriviallyTrue(const LinearConstraint &constraint, const IntegerTrail &integer_trail)
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)
CutGenerator CreatePositiveMultiplicationCutGenerator(IntegerVariable z, IntegerVariable x, IntegerVariable y, Model *model)
CutGenerator CreateCliqueCutGenerator(const std::vector< IntegerVariable > &base_variables, Model *model)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > lower_bounds
std::vector< double > upper_bounds
std::vector< IntegerVariable > vars
std::function< void(const absl::StrongVector< IntegerVariable, double > &lp_values, LinearConstraintManager *manager)> generate_cuts
std::vector< std::pair< IntegerVariable, IntegerValue > > terms
bool operator>(const KnapsackItem &other) const