#include <linear_programming_constraint.h>

Inheritance diagram for operations_research::sat::LinearProgrammingConstraint:

Public Types
typedef glop::RowIndex	ConstraintIndex

Public Member Functions
	LinearProgrammingConstraint (Model *model, absl::Span< const IntegerVariable > vars)

void	AddLinearConstraint (LinearConstraint ct)
	Add a new linear constraint to this LP.

void	SetObjectiveCoefficient (IntegerVariable ivar, IntegerValue coeff)

void	SetMainObjectiveVariable (IntegerVariable ivar)

IntegerVariable	ObjectiveVariable () const

void	AddCutGenerator (CutGenerator generator)
	Register a new cut generator with this constraint.

bool	HasSolution () const

double	GetSolutionValue (IntegerVariable variable) const

double	GetSolutionReducedCost (IntegerVariable variable) const

bool	SolutionIsInteger () const

bool	AtOptimal () const

double	ObjectiveLpLowerBound () const

bool	Propagate () override
	PropagatorInterface API.

bool	IncrementalPropagate (const std::vector< int > &watch_indices) override

void	RegisterWith (Model *model)

void	SetLevel (int level) override
	ReversibleInterface API.

int	NumVariables () const

const std::vector< IntegerVariable > &	integer_variables () const

std::string	DimensionString () const

std::function< IntegerLiteral()>	HeuristicLpReducedCostAverageBranching ()

double	average_degeneracy () const
	Average number of nonbasic variables with zero reduced costs.

int64_t	total_num_simplex_iterations () const
	Stats.

int64_t	total_num_cut_propagations () const

int64_t	total_num_eq_propagations () const

int64_t	num_solves () const

int64_t	num_adjusts () const

int64_t	num_cut_overflows () const

int64_t	num_bad_cuts () const

int64_t	num_scaling_issues () const

int64_t	num_lp_changes () const
	This can serve as a timestamp to know if a saved basis is out of date.

const std::vector< int64_t > &	num_solves_by_status () const

const LinearConstraintManager &	constraint_manager () const

IntegerSumLE128 *	LatestOptimalConstraintOrNull () const
	Important: this is only temporarily valid.

const std::vector< std::unique_ptr< IntegerSumLE128 > > &	OptimalConstraints () const

void	EnablePropagation (bool enable)

bool	PropagationIsEnabled () const

const glop::BasisState &	GetBasisState () const

void	LoadBasisState (const glop::BasisState &state)

template<bool check_overflow>
bool	ComputeNewLinearConstraint (absl::Span< const std::pair< RowIndex, IntegerValue > > integer_multipliers, ScatteredIntegerVector scattered_vector, IntegerValue upper_bound) const

Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default

virtual	~PropagatorInterface ()=default

Detailed Description

Definition at line 136 of file linear_programming_constraint.h.

Member Typedef Documentation

◆ ConstraintIndex

glop::RowIndex operations_research::sat::LinearProgrammingConstraint::ConstraintIndex

Definition at line 139 of file linear_programming_constraint.h.

Constructor & Destructor Documentation

◆ LinearProgrammingConstraint()

operations_research::sat::LinearProgrammingConstraint::LinearProgrammingConstraint	(	Model *	model,
		absl::Span< const IntegerVariable >	vars )

Each linear programming constraint works on a fixed set of variables. We expect the set of variable to be sorted in increasing order.

Todo: (user): make SatParameters singleton too, otherwise changing them after a constraint was added will have no effect on this class.

Tweak the default parameters to make the solve incremental.

Register our local rev int repository.

Register SharedStatistics with the cut helpers.

Initialize the IntegerVariable -> ColIndex mapping.

Definition at line 253 of file linear_programming_constraint.cc.

Member Function Documentation

◆ AddCutGenerator()

void operations_research::sat::LinearProgrammingConstraint::AddCutGenerator ( CutGenerator generator )

Register a new cut generator with this constraint.

Definition at line 585 of file linear_programming_constraint.cc.

◆ AddLinearConstraint()

void operations_research::sat::LinearProgrammingConstraint::AddLinearConstraint ( LinearConstraint ct )

Add a new linear constraint to this LP.

Definition at line 320 of file linear_programming_constraint.cc.

◆ AtOptimal()

bool operations_research::sat::LinearProgrammingConstraint::AtOptimal ( ) const

inline

Returns a valid lp lower bound for the current branch, and indicates if the latest LP solve in that branch was solved to optimality or not. During normal operation, we will always propagate the LP, so this should not refer to an optimality status lower in that branch.

Definition at line 175 of file linear_programming_constraint.h.

◆ average_degeneracy()

double operations_research::sat::LinearProgrammingConstraint::average_degeneracy ( ) const

inline

Average number of nonbasic variables with zero reduced costs.

Definition at line 202 of file linear_programming_constraint.h.

◆ ComputeNewLinearConstraint()

template<bool check_overflow>

bool operations_research::sat::LinearProgrammingConstraint::ComputeNewLinearConstraint	(	absl::Span< const std::pair< RowIndex, IntegerValue > >	integer_multipliers,
		ScatteredIntegerVector *	scattered_vector,
		IntegerValue *	upper_bound ) const

Initialize the new constraint.

Compute the new constraint by taking the linear combination given by integer_multipliers of the integer constraints in integer_lp_.

Update the constraint.

Update the upper bound.

Definition at line 1993 of file linear_programming_constraint.cc.

◆ constraint_manager()

const LinearConstraintManager & operations_research::sat::LinearProgrammingConstraint::constraint_manager ( ) const

inline

Definition at line 229 of file linear_programming_constraint.h.

◆ DimensionString()

std::string operations_research::sat::LinearProgrammingConstraint::DimensionString ( ) const

inline

Definition at line 192 of file linear_programming_constraint.h.

◆ EnablePropagation()

void operations_research::sat::LinearProgrammingConstraint::EnablePropagation ( bool enable )

inline

This api allows to temporarily disable the LP propagator which can be costly during probing or other heavy propagation phase.

Definition at line 246 of file linear_programming_constraint.h.

◆ GetBasisState()

const glop::BasisState & operations_research::sat::LinearProgrammingConstraint::GetBasisState ( ) const

inline

Definition at line 252 of file linear_programming_constraint.h.

◆ GetSolutionReducedCost()

double operations_research::sat::LinearProgrammingConstraint::GetSolutionReducedCost ( IntegerVariable variable ) const

Definition at line 661 of file linear_programming_constraint.cc.

◆ GetSolutionValue()

double operations_research::sat::LinearProgrammingConstraint::GetSolutionValue ( IntegerVariable variable ) const

Definition at line 656 of file linear_programming_constraint.cc.

◆ HasSolution()

bool operations_research::sat::LinearProgrammingConstraint::HasSolution ( ) const

inline

Returns the LP value and reduced cost of a variable in the current solution. These functions should only be called when HasSolution() is true.

Note: this solution is always an OPTIMAL solution of an LP above or at the current decision level. We "erase" it when we backtrack over it.

Definition at line 166 of file linear_programming_constraint.h.

◆ HeuristicLpReducedCostAverageBranching()

std::function< IntegerLiteral()> operations_research::sat::LinearProgrammingConstraint::HeuristicLpReducedCostAverageBranching ( )

Returns a IntegerLiteral guided by the underlying LP constraints.

This computes the mean of reduced costs over successive calls, and tries to fix the variable which has the highest reduced cost. Tie-breaking is done using the variable natural order.

Definition at line 2504 of file linear_programming_constraint.cc.

◆ IncrementalPropagate()

bool operations_research::sat::LinearProgrammingConstraint::IncrementalPropagate ( const std::vector< int > & )

overridevirtual

This will only be called on a non-empty vector, otherwise Propagate() will be called. The passed vector will contain the "watch index" of all the literals that were given one at registration and that changed since the last call to Propagate(). This is only true when going down in the search tree, on backjump this list will be cleared.

Notes:

The indices may contain duplicates if the same integer variable as been updated many times or if different watched literals have the same watch_index.
At level zero, it will not contain any indices associated with literals that were already fixed when the propagator was registered. Only the indices of the literals modified after the registration will be present.

If we have a really deep branch, with a lot of LP explanation constraint, we could take a quadratic amount of memory: O(num_var) per number of propagation in that branch. To avoid that, once the memory starts to be over a few GB, we only propagate from time to time. This way we do not need to keep that many constraints around.

Note: 100 Millions int32_t variables, with the int128 coefficients and extra propagation vector is already a few GB.

We only propagate if we use less that 100 times the number of current integer literal enqueued.

At level zero, if there is still a chance to add cuts or lazy constraints, we re-run the LP.

Check whether the change breaks the current LP solution. If it does, call Propagate() on the current LP.

Todo: (user): The saved lp solution is still valid given the current variable bounds, so the LP optimal didn't change. However we might still want to add new cuts or new lazy constraints?

Todo: (user): Propagate the last optimal_constraint? Note that we need to be careful since the reversible int in IntegerSumLE are not registered. However, because we delete "optimalconstraints" on backtrack, we might not care.

Remark: Note that if we do the sequence SetBasis() / Propagate() / GetAndSaveBasis() and we are in the case where the solution is still optimal, we should get the basis from when the lp solution was set which should be what we want. Even if we set garbage during SetBasis() it should be ignored.

Todo: (user): We might still have problem at level zero.

Reimplemented from operations_research::sat::PropagatorInterface.

Definition at line 589 of file linear_programming_constraint.cc.

◆ integer_variables()

const std::vector< IntegerVariable > & operations_research::sat::LinearProgrammingConstraint::integer_variables ( ) const

inline

Definition at line 189 of file linear_programming_constraint.h.

◆ LatestOptimalConstraintOrNull()

IntegerSumLE128 * operations_research::sat::LinearProgrammingConstraint::LatestOptimalConstraintOrNull ( ) const

inline

Important: this is only temporarily valid.

Definition at line 234 of file linear_programming_constraint.h.

◆ LoadBasisState()

void operations_research::sat::LinearProgrammingConstraint::LoadBasisState ( const glop::BasisState & state )

inline

Definition at line 253 of file linear_programming_constraint.h.

◆ num_adjusts()

int64_t operations_research::sat::LinearProgrammingConstraint::num_adjusts ( ) const

inline

Definition at line 217 of file linear_programming_constraint.h.

◆ num_bad_cuts()

int64_t operations_research::sat::LinearProgrammingConstraint::num_bad_cuts ( ) const

inline

Definition at line 219 of file linear_programming_constraint.h.

◆ num_cut_overflows()

int64_t operations_research::sat::LinearProgrammingConstraint::num_cut_overflows ( ) const

inline

Definition at line 218 of file linear_programming_constraint.h.

◆ num_lp_changes()

int64_t operations_research::sat::LinearProgrammingConstraint::num_lp_changes ( ) const

inline

This can serve as a timestamp to know if a saved basis is out of date.

Definition at line 223 of file linear_programming_constraint.h.

◆ num_scaling_issues()

int64_t operations_research::sat::LinearProgrammingConstraint::num_scaling_issues ( ) const

inline

Definition at line 220 of file linear_programming_constraint.h.

◆ num_solves()

int64_t operations_research::sat::LinearProgrammingConstraint::num_solves ( ) const

inline

Definition at line 216 of file linear_programming_constraint.h.

◆ num_solves_by_status()

const std::vector< int64_t > & operations_research::sat::LinearProgrammingConstraint::num_solves_by_status ( ) const

inline

Definition at line 225 of file linear_programming_constraint.h.

◆ NumVariables()

int operations_research::sat::LinearProgrammingConstraint::NumVariables ( ) const

inline

Definition at line 186 of file linear_programming_constraint.h.

◆ ObjectiveLpLowerBound()

double operations_research::sat::LinearProgrammingConstraint::ObjectiveLpLowerBound ( ) const

inline

Definition at line 176 of file linear_programming_constraint.h.

◆ ObjectiveVariable()

IntegerVariable operations_research::sat::LinearProgrammingConstraint::ObjectiveVariable ( ) const

inline

Definition at line 156 of file linear_programming_constraint.h.

◆ OptimalConstraints()

const std::vector< std::unique_ptr< IntegerSumLE128 > > & operations_research::sat::LinearProgrammingConstraint::OptimalConstraints ( ) const

inline

Definition at line 239 of file linear_programming_constraint.h.

◆ Propagate()

bool operations_research::sat::LinearProgrammingConstraint::Propagate ( )

overridevirtual

PropagatorInterface API.

Todo: (user): It seems the time we loose by not stopping early might be worth it because we end up with a better explanation at optimality.

We put a limit on the dual objective since there is no point increasing it past our current objective upper-bound (we will already fail as soon as we pass it). Note that this limit is properly transformed using the objective scaling factor and offset stored in lp_data_.

Note: we use a bigger epsilon here to be sure that if we abort because of this, we will report a conflict.

Put an iteration limit on the work we do in the simplex for this call. Note that because we are "incremental", even if we don't solve it this time we will make progress towards a solve in the lower node of the tree search.

Add new constraints to the LP and resolve?

We wait for the first batch of problem constraints to be added before we begin to generate cuts. Note that we rely on num_solves_ since on some problems there is no other constraints than the cuts.

This must be called first.

The "generic" cuts are currently part of this class as they are using data from the current LP.

Todo: (user): Refactor so that they are just normal cut generators?

Try to add cuts.

If we didn't add any new constraint, we delay the next Solve() since likely the optimal didn't change.

Implements operations_research::sat::PropagatorInterface.

Definition at line 1749 of file linear_programming_constraint.cc.

◆ PropagationIsEnabled()

bool operations_research::sat::LinearProgrammingConstraint::PropagationIsEnabled ( ) const

inline

Definition at line 250 of file linear_programming_constraint.h.

◆ RegisterWith()

void operations_research::sat::LinearProgrammingConstraint::RegisterWith ( Model * model )

Note fdid, this is not really needed by should lead to better cache locality.

Set the LP to its initial content.

Note: we always add LP constraint lazily if we have A LOT of them. This is because currently on large problem with millions of constraints, our LP is usually not fast enough anyway.

Registering it with the trail make sure this class is always in sync when it is used in the decision heuristics.

Definition at line 511 of file linear_programming_constraint.cc.

◆ SetLevel()

void operations_research::sat::LinearProgrammingConstraint::SetLevel ( int level )

overridevirtual

ReversibleInterface API.

Get rid of all optimal constraint each time we go back to level zero.

Special case for level zero, we "reload" any previously known optimal solution from that level.

Todo: (user): Keep all optimal solution in the current branch?

Todo

Todo: (user): Still try to add cuts/constraints though!

Todo

Todo: (user): Reload the basis? This might cause issue with the basis saving/loading code in lb_tree_search.

Implements operations_research::ReversibleInterface.

Definition at line 551 of file linear_programming_constraint.cc.

◆ SetMainObjectiveVariable()

void operations_research::sat::LinearProgrammingConstraint::SetMainObjectiveVariable ( IntegerVariable ivar )

inline

The main objective variable should be equal to the linear sum of the arguments passed to SetObjectiveCoefficient().

Definition at line 155 of file linear_programming_constraint.h.

◆ SetObjectiveCoefficient()

void operations_research::sat::LinearProgrammingConstraint::SetObjectiveCoefficient	(	IntegerVariable	ivar,
		IntegerValue	coeff )

Set the coefficient of the variable in the objective. Calling it twice will overwrite the previous value.

Definition at line 331 of file linear_programming_constraint.cc.

◆ SolutionIsInteger()

bool operations_research::sat::LinearProgrammingConstraint::SolutionIsInteger ( ) const

inline

Definition at line 169 of file linear_programming_constraint.h.

◆ total_num_cut_propagations()

int64_t operations_research::sat::LinearProgrammingConstraint::total_num_cut_propagations ( ) const

inline

Definition at line 210 of file linear_programming_constraint.h.

◆ total_num_eq_propagations()

int64_t operations_research::sat::LinearProgrammingConstraint::total_num_eq_propagations ( ) const

inline

Definition at line 213 of file linear_programming_constraint.h.

◆ total_num_simplex_iterations()

int64_t operations_research::sat::LinearProgrammingConstraint::total_num_simplex_iterations ( ) const

inline

Stats.

Definition at line 207 of file linear_programming_constraint.h.

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

ortools/sat/linear_programming_constraint.h
ortools/sat/linear_programming_constraint.cc

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ConstraintIndex

Constructor & Destructor Documentation

◆ LinearProgrammingConstraint()

Member Function Documentation

◆ AddCutGenerator()

◆ AddLinearConstraint()

◆ AtOptimal()

◆ average_degeneracy()

◆ ComputeNewLinearConstraint()

◆ constraint_manager()

◆ DimensionString()

◆ EnablePropagation()

◆ GetBasisState()

◆ GetSolutionReducedCost()

◆ GetSolutionValue()

◆ HasSolution()

◆ HeuristicLpReducedCostAverageBranching()

◆ IncrementalPropagate()

◆ integer_variables()

◆ LatestOptimalConstraintOrNull()

◆ LoadBasisState()

◆ num_adjusts()

◆ num_bad_cuts()

◆ num_cut_overflows()

◆ num_lp_changes()

◆ num_scaling_issues()

◆ num_solves()

◆ num_solves_by_status()

◆ NumVariables()

◆ ObjectiveLpLowerBound()

◆ ObjectiveVariable()

◆ OptimalConstraints()

◆ Propagate()

◆ PropagationIsEnabled()

◆ RegisterWith()

◆ SetLevel()

◆ SetMainObjectiveVariable()

◆ SetObjectiveCoefficient()

◆ SolutionIsInteger()

◆ total_num_cut_propagations()

◆ total_num_eq_propagations()

◆ total_num_simplex_iterations()