 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
#include <cuts.h>
Classes | |
| struct | BestImpliedBoundInfo |
Public Member Functions | |
| ImpliedBoundsProcessor (absl::Span< const IntegerVariable > lp_vars_, IntegerTrail *integer_trail, ImpliedBounds *implied_bounds) | |
| We will only replace IntegerVariable appearing in lp_vars_. | |
| void | RecomputeCacheAndSeparateSomeImpliedBoundCuts (const util_intops::StrongVector< IntegerVariable, double > &lp_values) |
| bool | DecomposeWithImpliedLowerBound (const CutTerm &term, IntegerValue factor_t, CutTerm &bool_term, CutTerm &slack_term) |
| bool | DecomposeWithImpliedUpperBound (const CutTerm &term, IntegerValue factor_t, CutTerm &bool_term, CutTerm &slack_term) |
| std::pair< int, int > | PostprocessWithImpliedBound (const std::function< IntegerValue(IntegerValue)> &f, IntegerValue factor_t, CutData *cut, CutDataBuilder *builder) |
| bool | CacheDataForCut (IntegerVariable first_slack, CutData *cut) |
| CutDataBuilder * | BaseCutBuilder () |
| bool | TryToExpandWithLowerImpliedbound (IntegerValue factor_t, int i, bool complement, CutData *cut, CutDataBuilder *builder) |
| Important: The cut_builder_ must have been reset. | |
| void | AddLpVariable (IntegerVariable var) |
| BestImpliedBoundInfo | GetCachedImpliedBoundInfo (IntegerVariable var) const |
| TopNCuts & | IbCutPool () |
Given an upper-bounded linear relation (sum terms <= ub), this algorithm inspects the integer variable appearing in the sum and try to replace each of them by a tight lower bound (>= coeff * binary + lb) using the implied bound repository. By tight, we mean that it will take the same value under the current LP solution.
We use a class to reuse memory of the tmp terms.
|
inline |
|
inline |
|
inline |
| bool operations_research::sat::ImpliedBoundsProcessor::CacheDataForCut | ( | IntegerVariable | first_slack, |
| CutData * | cut ) |
Precomputes quantities used by all cut generation. This allows to do that once rather than 6 times. Return false if there are no exploitable implied bounds.
Cache the BestImpliedBoundInfo if relevant.
| bool operations_research::sat::ImpliedBoundsProcessor::DecomposeWithImpliedLowerBound | ( | const CutTerm & | term, |
| IntegerValue | factor_t, | ||
| CutTerm & | bool_term, | ||
| CutTerm & | slack_term ) |
This assumes the term is simple: expr[0] = var - LB / UB - var. We use an implied lower bound on this expr, independently of the term.coeff sign.
If possible, returns true and express X = bool_term + slack_term. If coeff of X is positive, then all coeff will be positive here.
We only want to expand non-Boolean and non-slack term!
Try lower bounded direction for implied bound. This kind should always be beneficial if it exists:
Because X = bound_diff * B + S We can replace coeff * X by the expression before applying f: = f(coeff * bound_diff) * B + f(coeff) * [X - bound_diff * B] = f(coeff) * X + (f(coeff * bound_diff) - f(coeff) * bound_diff] * B So we can "lift" B into the cut with a non-negative coefficient.
We have X/-X = info.diff * Boolean + slack.
Create slack. The expression is term.exp - bound_diff * bool_term The variable shouldn't be the same.
| bool operations_research::sat::ImpliedBoundsProcessor::DecomposeWithImpliedUpperBound | ( | const CutTerm & | term, |
| IntegerValue | factor_t, | ||
| CutTerm & | bool_term, | ||
| CutTerm & | slack_term ) |
This assumes the term is simple: expr[0] = var - LB / UB - var. We use an implied upper bound on this expr, independently of term.coeff sign.
If possible, returns true and express X = bool_term + slack_term. If coeff of X is positive, then bool_term will have a positive coeff but slack_term will have a negative one.
We use the fact that calling DecomposeWithImpliedLowerBound() with term.Complement() give us almost what we want. You have -complement(X) = -diff.B - slack
This is required not to have a constant term which might mess up our cut heuristics.
| ImpliedBoundsProcessor::BestImpliedBoundInfo operations_research::sat::ImpliedBoundsProcessor::GetCachedImpliedBoundInfo | ( | IntegerVariable | var | ) | const |
|
inline |
| std::pair< int, int > operations_research::sat::ImpliedBoundsProcessor::PostprocessWithImpliedBound | ( | const std::function< IntegerValue(IntegerValue)> & | f, |
| IntegerValue | factor_t, | ||
| CutData * | cut, | ||
| CutDataBuilder * | builder ) |
We are about to apply the super-additive function f() to the CutData. Use implied bound information to eventually substitute and make the cut stronger. Returns the number of {lb_ib, ub_ib} applied.
This should lead to stronger cuts even if the norms migth be worse.
Score is just the final lp value. Higher is better since it is a <= constraint.
This side is always good. c.X = c.d.B + c.S applying f to the result we have f(c.d).B + f(c).[X - d.B] which give f(c).X + [f(c.d) - f(c).d].B and the second term is always positive by super-additivity.
Test if it is better to use this "bad" side.
Use the implied bound on (-X) if it is beneficial to do so. Like complementing, this is not always good.
We have comp(X) = diff - X = diff * B + S X = diff * (1 - B) - S. So if we applies f, we will get: f(coeff * diff) * (1 - B) + f(-coeff) * S and substituing S = diff * (1 - B) - X, we get:
| void operations_research::sat::ImpliedBoundsProcessor::RecomputeCacheAndSeparateSomeImpliedBoundCuts | ( | const util_intops::StrongVector< IntegerVariable, double > & | lp_values | ) |
| bool operations_research::sat::ImpliedBoundsProcessor::TryToExpandWithLowerImpliedbound | ( | IntegerValue | factor_t, |
| int | i, | ||
| bool | complement, | ||
| CutData * | cut, | ||
| CutDataBuilder * | builder ) |
Important: The cut_builder_ must have been reset.
It should be good to use IB, but sometime we have things like 7.3 = 2 * bool@1 + 5.3 and the expanded Boolean is at its upper bound. It is always good to complement such variable.
1.12.0