#include <variables_info.h>

Public Member Functions
	VariablesInfo (const CompactSparseMatrix &matrix)
	Takes references to the linear program data we need.

	VariablesInfo (const VariablesInfo &)=delete
	This type is neither copyable nor movable.

VariablesInfo &	operator= (const VariablesInfo &)=delete

bool	LoadBoundsAndReturnTrueIfUnchanged (const DenseRow &new_lower_bounds, const DenseRow &new_upper_bounds)

bool	LoadBoundsAndReturnTrueIfUnchanged (const DenseRow &variable_lower_bounds, const DenseRow &variable_upper_bounds, const DenseColumn &constraint_lower_bounds, const DenseColumn &constraint_upper_bounds)
	Same for an LP not in equation form.

void	InitializeFromBasisState (ColIndex first_slack, ColIndex num_new_cols, const BasisState &state)

int	ChangeUnusedBasicVariablesToFree (const RowToColMapping &basis)

int	SnapFreeVariablesToBound (Fractional distance, const DenseRow &starting_values)

void	InitializeToDefaultStatus ()

void	UpdateToBasicStatus (ColIndex col)

void	UpdateToNonBasicStatus (ColIndex col, VariableStatus status)

const VariableTypeRow &	GetTypeRow () const

const VariableStatusRow &	GetStatusRow () const

const DenseBitRow &	GetCanIncreaseBitRow () const

const DenseBitRow &	GetCanDecreaseBitRow () const

const DenseBitRow &	GetIsRelevantBitRow () const

const DenseBitRow &	GetIsBasicBitRow () const

const DenseBitRow &	GetNotBasicBitRow () const

const DenseBitRow &	GetNonBasicBoxedVariables () const

const DenseRow &	GetVariableLowerBounds () const
	Returns the variable bounds.

const DenseRow &	GetVariableUpperBounds () const

ColIndex	GetNumberOfColumns () const

void	MakeBoxedVariableRelevant (bool value)

EntryIndex	GetNumEntriesInRelevantColumns () const

Fractional	GetBoundDifference (ColIndex col) const
	Returns the distance between the upper and lower bound of the given column.

void	TransformToDualPhaseIProblem (Fractional dual_feasibility_tolerance, DenseRow::ConstView reduced_costs)

void	EndDualPhaseI (Fractional dual_feasibility_tolerance, DenseRow::ConstView reduced_costs)

Detailed Description

Class responsible for maintaining diverse information for each variable that depend on its bounds and status.

Note(user): Not all information is needed at all time, but it is cheap to maintain it since it only requires a few calls to Update() per simplex iteration.

Definition at line 55 of file variables_info.h.

Constructor & Destructor Documentation

◆ VariablesInfo() [1/2]

operations_research::glop::VariablesInfo::VariablesInfo ( const CompactSparseMatrix & matrix )

explicit

Takes references to the linear program data we need.

Definition at line 26 of file variables_info.cc.

◆ VariablesInfo() [2/2]

operations_research::glop::VariablesInfo::VariablesInfo ( const VariablesInfo & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ ChangeUnusedBasicVariablesToFree()

int operations_research::glop::VariablesInfo::ChangeUnusedBasicVariablesToFree ( const RowToColMapping & basis )

Changes to the FREE status any column with a BASIC status not listed in the basis. Returns their number. Also makes sure all the columns listed in basis are marked as basic. Note that if a variable is fixed, we set its status to FIXED_VALUE not FREE.

Definition at line 170 of file variables_info.cc.

◆ EndDualPhaseI()

void operations_research::glop::VariablesInfo::EndDualPhaseI	(	Fractional	dual_feasibility_tolerance,
		DenseRow::ConstView	reduced_costs )

This is to clear the memory of the saved bounds since it is no longer needed.

Restore the type and update all other fields.

We make sure that the old fixed variables that are now boxed are dual feasible.

Todo: (user): When there is a choice, use the previous status that might have been warm-started ? but then this is not high priority since warm-starting with a non-dual feasible basis seems unfrequent.

Definition at line 443 of file variables_info.cc.

◆ GetBoundDifference()

Fractional operations_research::glop::VariablesInfo::GetBoundDifference ( ColIndex col ) const

inline

Returns the distance between the upper and lower bound of the given column.

Definition at line 145 of file variables_info.h.

◆ GetCanDecreaseBitRow()

const DenseBitRow & operations_research::glop::VariablesInfo::GetCanDecreaseBitRow ( ) const

Definition at line 305 of file variables_info.cc.

◆ GetCanIncreaseBitRow()

const DenseBitRow & operations_research::glop::VariablesInfo::GetCanIncreaseBitRow ( ) const

Definition at line 301 of file variables_info.cc.

◆ GetIsBasicBitRow()

const DenseBitRow & operations_research::glop::VariablesInfo::GetIsBasicBitRow ( ) const

Definition at line 313 of file variables_info.cc.

◆ GetIsRelevantBitRow()

const DenseBitRow & operations_research::glop::VariablesInfo::GetIsRelevantBitRow ( ) const

Definition at line 309 of file variables_info.cc.

◆ GetNonBasicBoxedVariables()

const DenseBitRow & operations_research::glop::VariablesInfo::GetNonBasicBoxedVariables ( ) const

Definition at line 319 of file variables_info.cc.

◆ GetNotBasicBitRow()

const DenseBitRow & operations_research::glop::VariablesInfo::GetNotBasicBitRow ( ) const

Definition at line 315 of file variables_info.cc.

◆ GetNumberOfColumns()

ColIndex operations_research::glop::VariablesInfo::GetNumberOfColumns ( ) const

inline

Definition at line 134 of file variables_info.h.

◆ GetNumEntriesInRelevantColumns()

EntryIndex operations_research::glop::VariablesInfo::GetNumEntriesInRelevantColumns ( ) const

This is used in UpdateRow to decide whether to compute it using the row-wise or column-wise representation.

Definition at line 323 of file variables_info.cc.

◆ GetStatusRow()

const VariableStatusRow & operations_research::glop::VariablesInfo::GetStatusRow ( ) const

Definition at line 297 of file variables_info.cc.

◆ GetTypeRow()

const VariableTypeRow & operations_research::glop::VariablesInfo::GetTypeRow ( ) const

Various getter, see the corresponding member declaration below for more information.

Definition at line 293 of file variables_info.cc.

◆ GetVariableLowerBounds()

const DenseRow & operations_research::glop::VariablesInfo::GetVariableLowerBounds ( ) const

inline

Returns the variable bounds.

Definition at line 131 of file variables_info.h.

◆ GetVariableUpperBounds()

const DenseRow & operations_research::glop::VariablesInfo::GetVariableUpperBounds ( ) const

inline

Definition at line 132 of file variables_info.h.

◆ InitializeFromBasisState()

void operations_research::glop::VariablesInfo::InitializeFromBasisState	(	ColIndex	first_slack,
		ColIndex	num_new_cols,
		const BasisState &	state )

Initializes the status according to the given BasisState. Incompatible statuses will be corrected, and we transform the state correctly if new columns / rows were added. Note however that one will need to update the BasisState with deletions to preserve the status of unchanged columns.

Compute the status for all the columns (note that the slack variables are already added at the end of the matrix at this stage).

Start with the given "warm" status from the BasisState if it exists.

Remove incompatibilities between the warm status and the current state.

Because we just called ResetStatusInfo(), we optimize the call to UpdateToNonBasicStatus(col) here. In an incremental setting with almost no work per call, the update of all the DenseBitRow are visible.

Definition at line 112 of file variables_info.cc.

◆ InitializeToDefaultStatus()

void operations_research::glop::VariablesInfo::InitializeToDefaultStatus ( )

Sets all variables status to their lowest magnitude bounds. Note that there will be no basic variable after this is called.

Definition at line 217 of file variables_info.cc.

◆ LoadBoundsAndReturnTrueIfUnchanged() [1/2]

bool operations_research::glop::VariablesInfo::LoadBoundsAndReturnTrueIfUnchanged	(	const DenseRow &	new_lower_bounds,
		const DenseRow &	new_upper_bounds )

Updates the internal bounds and recomputes the variable types from the bounds (this is the only function that changes them).

Returns true iff the existing bounds didn't change. Except if the bounds AND underlying matrix didn't change, one will need to call one of the two Initialize*() methods below before using this class.

Optim if nothing changed.

Definition at line 29 of file variables_info.cc.

◆ LoadBoundsAndReturnTrueIfUnchanged() [2/2]

bool operations_research::glop::VariablesInfo::LoadBoundsAndReturnTrueIfUnchanged	(	const DenseRow &	variable_lower_bounds,
		const DenseRow &	variable_upper_bounds,
		const DenseColumn &	constraint_lower_bounds,
		const DenseColumn &	constraint_upper_bounds )

Same for an LP not in equation form.

Copy bounds of the variables.

Copy bounds of the slack.

Definition at line 49 of file variables_info.cc.

◆ MakeBoxedVariableRelevant()

void operations_research::glop::VariablesInfo::MakeBoxedVariableRelevant ( bool value )

Changes whether or not a non-basic boxed variable is 'relevant' and will be returned as such by GetIsRelevantBitRow().

Definition at line 243 of file variables_info.cc.

◆ operator=()

VariablesInfo & operations_research::glop::VariablesInfo::operator= ( const VariablesInfo & )

delete

◆ SnapFreeVariablesToBound()

int operations_research::glop::VariablesInfo::SnapFreeVariablesToBound	(	Fractional	distance,
		const DenseRow &	starting_values )

Loops over all the free variables, and if such a variable has bounds and its starting value is closer to its closest bound than the given distance, change the status to move this variable to that bound. Returns the number of changes. The variable for which starting_values is not provided are considered at zero.

This is mainly useful if non-zero starting values are provided. It allows to move all the variables close to their bounds at once instead of having to move them one by one with simplex pivots later. Of course, by doing that we usually introduce a small primal infeasibility that might need correction.

If one uses a large distance, then all such variables will start at their bound if they have one.

Definition at line 191 of file variables_info.cc.

◆ TransformToDualPhaseIProblem()

void operations_research::glop::VariablesInfo::TransformToDualPhaseIProblem	(	Fractional	dual_feasibility_tolerance,
		DenseRow::ConstView	reduced_costs )

This is used for the (SP) method of "Progress in the dual simplex method for large scale LP problems: practical dual phase I algorithms". Achim Koberstein & Uwe H. Suhl.

This just set the bounds according to the variable types:

Boxed variables get fixed at [0,0].
Upper bounded variables get [-1, 0] bounds
Lower bounded variables get [0, 1] bounds
Free variables get [-1000, 1000] to heuristically move them to the basis. I.e. they cost in the dual infeasibility minimization problem is multiplied by 1000.

It then update the status to get an initial dual feasible solution, and then one just have to apply the phase II algo on this problem to try to find a feasible solution to the original problem.

Optimization: When a variable become basic, its non-zero bounds are relaxed. This is a bit hacky as it requires that the status is updated before the bounds are read (which is the case). It is however an important optimization.

Todo: (user): Shall we re-add the bound when the variable is moved out of the base? it is not needed, but might allow for more bound flips?

Transform the bound and type to get a new problem. If this problem has an optimal value of 0.0, then the problem is dual feasible. And more importantly, by keeping the same basis, we have a feasible solution of the original problem.

Make sure we start with a feasible dual solution. If the reduced cost is close to zero, we keep the "default" status.

Definition at line 392 of file variables_info.cc.

◆ UpdateToBasicStatus()

void operations_research::glop::VariablesInfo::UpdateToBasicStatus ( ColIndex col )

Updates the information of the given variable. Note that it is not needed to call this if the status or the bound of a variable didn't change.

Todo: (user): A bit annoying that we need to test this even if we don't use the dual. But the cost is minimal.

Definition at line 257 of file variables_info.cc.

◆ UpdateToNonBasicStatus()

void operations_research::glop::VariablesInfo::UpdateToNonBasicStatus	(	ColIndex	col,
		VariableStatus	status )

Definition at line 274 of file variables_info.cc.

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

ortools/glop/variables_info.h
ortools/glop/variables_info.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ VariablesInfo() [1/2]

◆ VariablesInfo() [2/2]

Member Function Documentation

◆ ChangeUnusedBasicVariablesToFree()

◆ EndDualPhaseI()

◆ GetBoundDifference()

◆ GetCanDecreaseBitRow()

◆ GetCanIncreaseBitRow()

◆ GetIsBasicBitRow()

◆ GetIsRelevantBitRow()

◆ GetNonBasicBoxedVariables()

◆ GetNotBasicBitRow()

◆ GetNumberOfColumns()

◆ GetNumEntriesInRelevantColumns()

◆ GetStatusRow()

◆ GetTypeRow()

◆ GetVariableLowerBounds()

◆ GetVariableUpperBounds()

◆ InitializeFromBasisState()

◆ InitializeToDefaultStatus()

◆ LoadBoundsAndReturnTrueIfUnchanged() [1/2]

◆ LoadBoundsAndReturnTrueIfUnchanged() [2/2]

◆ MakeBoxedVariableRelevant()

◆ operator=()

◆ SnapFreeVariablesToBound()

◆ TransformToDualPhaseIProblem()

◆ UpdateToBasicStatus()

◆ UpdateToNonBasicStatus()