operations_research::sat::BoolRLTCutHelper Class Reference

#include <cuts.h>

Public Member Functions
	BoolRLTCutHelper (Model *model)
	~BoolRLTCutHelper ()
void	Initialize (const absl::flat_hash_map< IntegerVariable, glop::ColIndex > &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.

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 566 of file cuts.h.

Constructor & Destructor Documentation

BoolRLTCutHelper()

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

inlineexplicit

Definition at line 568 of file cuts.h.

~BoolRLTCutHelper()

operations_research::sat::BoolRLTCutHelper::~BoolRLTCutHelper

(

)

Definition at line 1645 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 583 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 586 of file cuts.h.

Initialize()

void operations_research::sat::BoolRLTCutHelper::Initialize

(

const absl::flat_hash_map< IntegerVariable, glop::ColIndex > &

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 1653 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 1660 of file cuts.cc.

---

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

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