operations_research::sat::BoolRLTCutHelper Class Reference

Detailed Description

Separate RLT cuts.

See for instance "Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products", Ksenia Bestuzheva, Ambros Gleixner, Tobias Achterberg, https://arxiv.org/abs/2211.13545

Definition at line 577 of file cuts.h.

#include <cuts.h>

Public Member Functions
	BoolRLTCutHelper (Model *model)
	~BoolRLTCutHelper ()
void	Initialize (absl::Span< const IntegerVariable > lp_vars)
bool	TrySimpleSeparation (const CutData &input_ct)
	Tries RLT separation of the input constraint. Returns true on success.
const CutData &	cut () const
	If successful, this contains the last generated cut.
std::string	Info () const
	Single line of text that we append to the cut log line.

Constructor & Destructor Documentation

BoolRLTCutHelper()

operations_research::sat::BoolRLTCutHelper::BoolRLTCutHelper ( Model * model )

inlineexplicit

Definition at line 579 of file cuts.h.

~BoolRLTCutHelper()

operations_research::sat::BoolRLTCutHelper::~BoolRLTCutHelper

(

)

Definition at line 1663 of file cuts.cc.

Member Function Documentation

cut()

const CutData & operations_research::sat::BoolRLTCutHelper::cut ( ) const

inline

If successful, this contains the last generated cut.

Definition at line 593 of file cuts.h.

Info()

std::string operations_research::sat::BoolRLTCutHelper::Info ( ) const

inline

Single line of text that we append to the cut log line.

Definition at line 596 of file cuts.h.

Initialize()

void operations_research::sat::BoolRLTCutHelper::Initialize

(

absl::Span< const IntegerVariable >

lp_vars

)

Precompute data according to the current lp relaxation. This also restrict any Boolean to be currently appearing in the LP.

Definition at line 1671 of file cuts.cc.

TrySimpleSeparation()

bool operations_research::sat::BoolRLTCutHelper::TrySimpleSeparation

(

const CutData &

input_ct

)

Tries RLT separation of the input constraint. Returns true on success.

Todo

(user): do less work, add more stats.

We will list the interesting "factor" to try to multiply + linearize the input constraint with.

We can look at the linearized factor * term and bound the activity delta rescaled by 1 / factor.

CASE linearized_term delta = term/factor - previous

DROP, 0 0 - X MC_CORMICK, factor * ub - (ub - X) (ub - X) * (1 - 1/factor) <= 0 SQUARE, factor=X 1 - X RLT, factor - P 1 - X - P/X <= 1 - X

Todo

(user): detect earlier that a factor is not worth checking because we already loose too much with the DROP/MC_CORMICK cases ? Filter more ? I think we can probably evaluate the factor efficiency during the first loop which usually have a small complexity compared to num_factor_to_try times num filtered terms.

The only options are DROP or MC_CORMICK, but the later will unlikely win.

Todo

(user): we never use factor with lp value < 1e-4, but we could use a factor equal to 1.0 I think. Double check.

Here the MC_CORMICK will not loose much. And SQUARE or RLT cannot win much, so we can assume there is no loss and just look for violated subconstraint.

Convert to var or -var (to mean 1 - var).

Todo

(user): We could keep for each factor the max gain, so that we can decided if it is not even worth trying a factor.

Todo

(user): Avoid constructing the cut just to evaluate its efficacy.

If we found a good factor, applies it to the non-filtered base constraint.

Definition at line 1677 of file cuts.cc.

---

The documentation for this class was generated from the following files:

• ortools/sat/cuts.h
• ortools/sat/cuts.cc