#include <linear_constraint_manager.h>

Classes
struct	ConstraintInfo

Public Member Functions
	LinearConstraintManager (Model *model)

	~LinearConstraintManager ()

	DEFINE_STRONG_INDEX_TYPE (ConstraintIndex)

ConstraintIndex	Add (LinearConstraint ct, bool *added=nullptr)

bool	AddCut (LinearConstraint ct, std::string type_name, std::string extra_info="")

bool	UpdateConstraintLb (glop::RowIndex index_in_lp, IntegerValue new_lb)
	These must be level zero bounds.

bool	UpdateConstraintUb (glop::RowIndex index_in_lp, IntegerValue new_ub)

void	SetObjectiveCoefficient (IntegerVariable var, IntegerValue coeff)

bool	ChangeLp (glop::BasisState solution_state, int num_new_constraints=nullptr)

void	AddAllConstraintsToLp ()

const util_intops::StrongVector< ConstraintIndex, ConstraintInfo > &	AllConstraints () const
	All the constraints managed by this class.

const std::vector< ConstraintIndex > &	LpConstraints () const

const util_intops::StrongVector< IntegerVariable, double > &	LpValues ()
	To simplify CutGenerator api.

int64_t	num_constraints () const
	Stats.

int64_t	num_constraint_updates () const

int64_t	num_simplifications () const

int64_t	num_merged_constraints () const

int64_t	num_shortened_constraints () const

int64_t	num_split_constraints () const

int64_t	num_coeff_strenghtening () const

int64_t	num_cuts () const

int64_t	num_add_cut_calls () const

const absl::btree_map< std::string, int > &	type_to_num_cuts () const

bool	DebugCheckConstraint (const LinearConstraint &cut)

Detailed Description

This class holds a list of globally valid linear constraints and has some logic to decide which one should be part of the LP relaxation. We want more for a better relaxation, but for efficiency we do not want to have too much constraints while solving the LP.

This class is meant to contain all the initial constraints of the LP relaxation and to get new cuts as they are generated. Thus, it can both manage cuts but also only add the initial constraints lazily if there is too many of them.

Definition at line 60 of file linear_constraint_manager.h.

Constructor & Destructor Documentation

◆ LinearConstraintManager()

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

inlineexplicit

Definition at line 96 of file linear_constraint_manager.h.

◆ ~LinearConstraintManager()

operations_research::sat::LinearConstraintManager::~LinearConstraintManager ( )

Definition at line 67 of file linear_constraint_manager.cc.

Member Function Documentation

◆ Add()

LinearConstraintManager::ConstraintIndex operations_research::sat::LinearConstraintManager::Add	(	LinearConstraint	ct,
		bool *	added = nullptr )

Because sometimes we split a == constraint in two (>= and <=), it makes sense to detect duplicate constraints and merge bounds. This is also relevant if we regenerate identical cuts for some reason.

If an identical constraint exists, only updates its bound.

Definition at line 132 of file linear_constraint_manager.cc.

◆ AddAllConstraintsToLp()

void operations_research::sat::LinearConstraintManager::AddAllConstraintsToLp ( )

This can be called initially to add all the current constraint to the LP returned by GetLp().

Definition at line 764 of file linear_constraint_manager.cc.

◆ AddCut()

bool operations_research::sat::LinearConstraintManager::AddCut	(	LinearConstraint	ct,
		std::string	type_name,
		std::string	extra_info = "" )

Same as Add(), but logs some information about the newly added constraint. Cuts are also handled slightly differently than normal constraints.

Returns true if a new cut was added and false if this cut is not efficacious or if it is a duplicate of an already existing one.

Same as Add(), but logs some information about the newly added constraint. Cuts are also handled slightly differently than normal constraints.

Only add cut with sufficient efficacy.

Todo: (user): We could prevent overflow by dividing more. Note that mainly happen with super large variable domain since we usually restrict the size of the generated coefficients in our cuts. So it shouldn't be that important.

We only mark the constraint as a cut if it is not an update of an already existing one.

Todo: (user): Use better heuristic here for detecting good cuts and mark them undeletable.

Definition at line 236 of file linear_constraint_manager.cc.

◆ AllConstraints()

const util_intops::StrongVector< ConstraintIndex, ConstraintInfo > & operations_research::sat::LinearConstraintManager::AllConstraints ( ) const

inline

All the constraints managed by this class.

Definition at line 150 of file linear_constraint_manager.h.

◆ ChangeLp()

bool operations_research::sat::LinearConstraintManager::ChangeLp	(	glop::BasisState *	solution_state,
		int *	num_new_constraints = nullptr )

Heuristic to decides what LP is best solved next. We use the model lp solutions as an heuristic, and it should usually be updated with the last known solution before this call.

The current solution state is used for detecting inactive constraints. It is also updated correctly on constraint deletion/addition so that the simplex can be fully iterative on restart by loading this modified state.

Returns true iff LpConstraints() will return a different LP than before.

We keep any constraints that is already present, and otherwise, we add the ones that are currently not satisfied by at least "tolerance" to the set of potential new constraints.

Inprocessing of the constraint.

Note: the canonicalization shouldn't be needed since the order of the variable is not changed by the simplification, and we only reduce the coefficients at both end of the spectrum.

Todo: (user): Because we simplified this constraint, it is possible that it is now a duplicate of another one. Merge them.

ComputeActivity() often represent the bulk of the time spent in ChangeLP().

Bump activities of active constraints in LP.

Update the increment counter.

Remove constraints from the current LP that have been inactive for a while. We do that after we computed new_constraints so we do not need to iterate over the just deleted constraints.

Note: the algo below is in O(limit * new_constraint). In order to limit spending too much time on this, we first sort all the constraints with an imprecise score (no orthogonality), then limit the size of the vector of constraints to precisely score, then we do the actual scoring.

On problem crossword_opt_grid-19.05_dict-80_sat with linearization_level=2, new_constraint.size() > 1.5M.

Todo: (user): This blowup factor could be adaptative w.r.t. the constraint limit.

Iterate through all new constraints and select the one with the best score.

Todo: (user): find better algo, this does 1000 * 4000 scalar product!

Checks the time limit, and returns if the lp has changed.

NOTE(user): It is safe to not add this constraint as the constraint that is almost parallel to this constraint is present in the LP or is inactive for a long time and is removed from the LP. In either case, this constraint is not adding significant value and is only making the LP larger.

Todo: (user): Experiment with different weights or different functions for computing score.

Add the best constraint in the LP.

Note: it is important for LP incremental solving that the old constraints stays at the same position in this list (and thus in the returned GetLp()).

Abort the addition loop.

We update the solution sate to match the new LP size.

Todo: (user): Instead of comparing num_deletable_constraints with cut limit, compare number of deletable constraints not in lp against the limit.

The LP changed only if we added new constraints or if some constraints already inside changed (simplification or tighter bounds).

Definition at line 516 of file linear_constraint_manager.cc.

◆ DebugCheckConstraint()

bool operations_research::sat::LinearConstraintManager::DebugCheckConstraint ( const LinearConstraint & cut )

If a debug solution has been loaded, this checks if the given constraint cut it or not. Returns true if and only if everything is fine and the cut does not violate the loaded solution.

Definition at line 772 of file linear_constraint_manager.cc.

◆ DEFINE_STRONG_INDEX_TYPE()

operations_research::sat::LinearConstraintManager::DEFINE_STRONG_INDEX_TYPE ( ConstraintIndex )

Add a new constraint to the manager. Note that we canonicalize constraints and merge the bounds of constraints with the same terms. We also perform basic preprocessing. If added is given, it will be set to true if this constraint was actually a new one and to false if it was dominated by an already existing one.

◆ LpConstraints()

const std::vector< ConstraintIndex > & operations_research::sat::LinearConstraintManager::LpConstraints ( ) const

inline

The set of constraints indices in AllConstraints() that should be part of the next LP to solve.

Definition at line 156 of file linear_constraint_manager.h.

◆ LpValues()

const util_intops::StrongVector< IntegerVariable, double > & operations_research::sat::LinearConstraintManager::LpValues ( )

inline

To simplify CutGenerator api.

Definition at line 161 of file linear_constraint_manager.h.

◆ num_add_cut_calls()

int64_t operations_research::sat::LinearConstraintManager::num_add_cut_calls ( ) const

inline

Definition at line 176 of file linear_constraint_manager.h.

◆ num_coeff_strenghtening()

int64_t operations_research::sat::LinearConstraintManager::num_coeff_strenghtening ( ) const

inline

Definition at line 174 of file linear_constraint_manager.h.

◆ num_constraint_updates()

int64_t operations_research::sat::LinearConstraintManager::num_constraint_updates ( ) const

inline

Definition at line 167 of file linear_constraint_manager.h.

◆ num_constraints()

int64_t operations_research::sat::LinearConstraintManager::num_constraints ( ) const

inline

Stats.

Definition at line 166 of file linear_constraint_manager.h.

◆ num_cuts()

int64_t operations_research::sat::LinearConstraintManager::num_cuts ( ) const

inline

Definition at line 175 of file linear_constraint_manager.h.

◆ num_merged_constraints()

int64_t operations_research::sat::LinearConstraintManager::num_merged_constraints ( ) const

inline

Definition at line 169 of file linear_constraint_manager.h.

◆ num_shortened_constraints()

int64_t operations_research::sat::LinearConstraintManager::num_shortened_constraints ( ) const

inline

Definition at line 170 of file linear_constraint_manager.h.

◆ num_simplifications()

int64_t operations_research::sat::LinearConstraintManager::num_simplifications ( ) const

inline

Definition at line 168 of file linear_constraint_manager.h.

◆ num_split_constraints()

int64_t operations_research::sat::LinearConstraintManager::num_split_constraints ( ) const

inline

Definition at line 173 of file linear_constraint_manager.h.

◆ SetObjectiveCoefficient()

void operations_research::sat::LinearConstraintManager::SetObjectiveCoefficient	(	IntegerVariable	var,
		IntegerValue	coeff )

The objective is used as one of the criterion to score cuts. The more a cut is parallel to the objective, the better its score is.

Currently this should only be called once per IntegerVariable (Checked). It is easy to support dynamic modification if it becomes needed.

Definition at line 341 of file linear_constraint_manager.cc.

◆ type_to_num_cuts()

const absl::btree_map< std::string, int > & operations_research::sat::LinearConstraintManager::type_to_num_cuts ( ) const

inline

Definition at line 178 of file linear_constraint_manager.h.

◆ UpdateConstraintLb()

bool operations_research::sat::LinearConstraintManager::UpdateConstraintLb	(	glop::RowIndex	index_in_lp,
		IntegerValue	new_lb )

These must be level zero bounds.

Definition at line 181 of file linear_constraint_manager.cc.

◆ UpdateConstraintUb()

bool operations_research::sat::LinearConstraintManager::UpdateConstraintUb	(	glop::RowIndex	index_in_lp,
		IntegerValue	new_ub )

Definition at line 192 of file linear_constraint_manager.cc.

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

ortools/sat/linear_constraint_manager.h
ortools/sat/linear_constraint_manager.cc

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LinearConstraintManager()

◆ ~LinearConstraintManager()

Member Function Documentation

◆ Add()

◆ AddAllConstraintsToLp()

◆ AddCut()

◆ AllConstraints()

◆ ChangeLp()

◆ DebugCheckConstraint()

◆ DEFINE_STRONG_INDEX_TYPE()

◆ LpConstraints()

◆ LpValues()

◆ num_add_cut_calls()

◆ num_coeff_strenghtening()

◆ num_constraint_updates()

◆ num_constraints()

◆ num_cuts()

◆ num_merged_constraints()

◆ num_shortened_constraints()

◆ num_simplifications()

◆ num_split_constraints()

◆ SetObjectiveCoefficient()

◆ type_to_num_cuts()

◆ UpdateConstraintLb()

◆ UpdateConstraintUb()