#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)

bool	AddLinearConstraint (LinearConstraint ct)

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

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
	From outside, the lp should be seen as containing all extended variables.

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 137 of file linear_programming_constraint.h.

Member Typedef Documentation

◆ ConstraintIndex

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

Definition at line 140 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.

Todo: (user): We shouldn't need to add variable from the orbit here in the presence of symmetry. However they can still appear in cut, so it is a bit tricky and require some refactoring to be tried.

Complete the extended variables with the orbit afterwards.

We use the "extended" vector for lp_solution_/lp_reduced_cost_.

Definition at line 278 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 833 of file linear_programming_constraint.cc.

◆ AddLinearConstraint()

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

Add a new linear constraint to this LP. Return false if we prove infeasibility of the global model.

If we added a folded constraints, lets add it to the CP propagators. This is important as this should tighten the bounds of the orbit sum vars.

Definition at line 378 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 185 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 214 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 2351 of file linear_programming_constraint.cc.

◆ constraint_manager()

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

inline

Definition at line 241 of file linear_programming_constraint.h.

◆ DimensionString()

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

Definition at line 2934 of file linear_programming_constraint.cc.

◆ 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 258 of file linear_programming_constraint.h.

◆ GetBasisState()

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

inline

Definition at line 264 of file linear_programming_constraint.h.

◆ GetSolutionValue()

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

Definition at line 904 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 177 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 2862 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 837 of file linear_programming_constraint.cc.

◆ integer_variables()

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

inline

Definition at line 200 of file linear_programming_constraint.h.

◆ LatestOptimalConstraintOrNull()

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

inline

Important: this is only temporarily valid.

Definition at line 246 of file linear_programming_constraint.h.

◆ LoadBasisState()

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

inline

Definition at line 265 of file linear_programming_constraint.h.

◆ num_adjusts()

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

inline

Definition at line 229 of file linear_programming_constraint.h.

◆ num_bad_cuts()

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

inline

Definition at line 231 of file linear_programming_constraint.h.

◆ num_cut_overflows()

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

inline

Definition at line 230 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 235 of file linear_programming_constraint.h.

◆ num_scaling_issues()

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

inline

Definition at line 232 of file linear_programming_constraint.h.

◆ num_solves()

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

inline

Definition at line 228 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 237 of file linear_programming_constraint.h.

◆ NumVariables()

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

inline

From outside, the lp should be seen as containing all extended variables.

Definition at line 197 of file linear_programming_constraint.h.

◆ ObjectiveLpLowerBound()

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

inline

Definition at line 186 of file linear_programming_constraint.h.

◆ ObjectiveVariable()

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

inline

Definition at line 167 of file linear_programming_constraint.h.

◆ OptimalConstraints()

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

inline

Definition at line 251 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 2122 of file linear_programming_constraint.cc.

◆ PropagationIsEnabled()

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

inline

Definition at line 262 of file linear_programming_constraint.h.

◆ RegisterWith()

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

Copy objective data to the constraint_manager_.

Note(user): the sort is not really needed but 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 408 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.

Add the fixed variables. They might have been skipped when we did the linear relaxation of the model, but cut generators expect all variables to have an LP value.

Implements operations_research::ReversibleInterface.

Definition at line 788 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 157 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 469 of file linear_programming_constraint.cc.

◆ SolutionIsInteger()

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

inline

Definition at line 179 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 222 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 225 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 219 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()

◆ 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()