#include <variable_values.h>

Public Member Functions
	VariableValues (const GlopParameters &parameters, const CompactSparseMatrix &matrix, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization, DualEdgeNorms dual_edge_norms, DynamicMaximum< RowIndex > dual_prices)

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

VariableValues &	operator= (const VariableValues &)=delete

Fractional	Get (ColIndex col) const
	Getters for the variable values.

const DenseRow &	GetDenseRow () const

void	SetNonBasicVariableValueFromStatus (ColIndex col)

void	ResetAllNonBasicVariableValues (const DenseRow &free_initial_values)

void	RecomputeBasicVariableValues ()

Fractional	ComputeMaximumPrimalResidual () const

Fractional	ComputeMaximumPrimalInfeasibility () const

Fractional	ComputeSumOfPrimalInfeasibilities () const

void	UpdateOnPivoting (const ScatteredColumn &direction, ColIndex entering_col, Fractional step)

void	UpdateGivenNonBasicVariables (absl::Span< const ColIndex > cols_to_update, bool update_basic_variables)

void	RecomputeDualPrices (bool put_more_importance_on_norm=false)

void	UpdateDualPrices (absl::Span< const RowIndex > row)

template<typename Rows >
bool	UpdatePrimalPhaseICosts (const Rows &rows, DenseRow *objective)

void	Set (ColIndex col, Fractional value)
	Sets the variable value of a given column.

std::string	StatString () const
	Parameters and stats functions.

Detailed Description

Class holding all the variable values and responsible for updating them. The variable values 'x' are such that 'A.x = 0' where A is the linear program matrix. This is because slack variables with bounds corresponding to the constraints bounds were added to the linear program matrix A.

Some remarks:

For convenience, the variable values are stored in a DenseRow and indexed by ColIndex, like the variables and the columns of A.
During the dual-simplex, all non-basic variable values are at their exact bounds or exactly at 0.0 for a free variable.
During the primal-simplex, the non-basic variable values may not be exactly at their bounds because of bound-shifting during degenerate simplex pivoting which is implemented by not setting the variable values exactly at their bounds to have a lower primal residual error.

Definition at line 49 of file variable_values.h.

Constructor & Destructor Documentation

◆ VariableValues() [1/2]

operations_research::glop::VariableValues::VariableValues	(	const GlopParameters &	parameters,
		const CompactSparseMatrix &	matrix,
		const RowToColMapping &	basis,
		const VariablesInfo &	variables_info,
		const BasisFactorization &	basis_factorization,
		DualEdgeNorms *	dual_edge_norms,
		DynamicMaximum< RowIndex > *	dual_prices )

Definition at line 38 of file variable_values.cc.

◆ VariableValues() [2/2]

operations_research::glop::VariableValues::VariableValues ( const VariableValues & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ ComputeMaximumPrimalInfeasibility()

Fractional operations_research::glop::VariableValues::ComputeMaximumPrimalInfeasibility ( ) const

Computes the maximum bound error for all the variables, defined as the distance of the current value of the variable to its interval [lower bound, upper bound]. The infeasibility is thus equal to 0.0 if the current value falls within the bounds, to the distance to lower_bound (resp. upper_bound), if the current value is below (resp. above) lower_bound (resp. upper_bound).

Definition at line 144 of file variable_values.cc.

◆ ComputeMaximumPrimalResidual()

Fractional operations_research::glop::VariableValues::ComputeMaximumPrimalResidual ( ) const

Computes the infinity norm of A.x where A is the linear_program matrix and x is the variable values column.

Definition at line 132 of file variable_values.cc.

◆ ComputeSumOfPrimalInfeasibilities()

Fractional operations_research::glop::VariableValues::ComputeSumOfPrimalInfeasibilities ( ) const

Definition at line 161 of file variable_values.cc.

◆ Get()

Fractional operations_research::glop::VariableValues::Get ( ColIndex col ) const

inline

Getters for the variable values.

Definition at line 64 of file variable_values.h.

◆ GetDenseRow()

const DenseRow & operations_research::glop::VariableValues::GetDenseRow ( ) const

inline

Definition at line 65 of file variable_values.h.

◆ operator=()

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

delete

◆ RecomputeBasicVariableValues()

void operations_research::glop::VariableValues::RecomputeBasicVariableValues ( )

Recomputes the value of the basic variables from the non-basic ones knowing that the linear program matrix A times the variable values vector must be zero. It is better to call this when the basis is refactorized. This is checked in debug mode.

This makes sure that they will be recomputed if needed.

Definition at line 113 of file variable_values.cc.

◆ RecomputeDualPrices()

void operations_research::glop::VariableValues::RecomputeDualPrices ( bool put_more_importance_on_norm = false )

Functions dealing with the primal-infeasible basic variables. A basic variable is primal-infeasible if its infeasibility is stricly greater than the primal feasibility tolerance. These are exactly the dual "prices" once recalled by the norms. This is only used during the dual simplex.

This information is only available after a call to RecomputeDualPrices() and has to be kept in sync by calling UpdateDualPrices() for the rows that changed values.

Todo: (user): On some problem like stp3d.mps or pds-100.mps, using different price like abs(infeasibility) / squared_norms give better result. Some solver switch according to a criteria like all entry are +1/-1, the column have no more than 24 non-zero and the average column size is no more than 6! Understand and implement some variant of this? I think the gain is mainly because of using sparser vectors?

Definition at line 253 of file variable_values.cc.

◆ ResetAllNonBasicVariableValues()

void operations_research::glop::VariableValues::ResetAllNonBasicVariableValues ( const DenseRow & free_initial_values )

Calls SetNonBasicVariableValueFromStatus() on all non-basic variables. We accept any size for free_initial_values, for columns col that are valid indices, free_initial_values[col] will be used instead of 0.0 for a free column. If free_initial_values is empty, then we have the default behavior of starting at zero for all FREE variables.

Note(user): It is okay to always use the same value to reset a FREE variable because as soon as a FREE variable value is modified, this variable shouldn't be FREE anymore. It will either move to a bound or enter the basis, these are the only options.

Definition at line 86 of file variable_values.cc.

◆ Set()

void operations_research::glop::VariableValues::Set	(	ColIndex	col,
		Fractional	value )

inline

Sets the variable value of a given column.

Definition at line 145 of file variable_values.h.

◆ SetNonBasicVariableValueFromStatus()

void operations_research::glop::VariableValues::SetNonBasicVariableValueFromStatus ( ColIndex col )

Sets the value of a non-basic variable to the exact value implied by its current status. Note that the basic variable values are NOT updated by this function and it is up to the client to call RecomputeBasicVariableValues().

Note: there is no default value in the switch() statement above to get a compile-time error if a value is missing.

Definition at line 54 of file variable_values.cc.

◆ StatString()

std::string operations_research::glop::VariableValues::StatString ( ) const

inline

Parameters and stats functions.

Definition at line 148 of file variable_values.h.

◆ UpdateDualPrices()

void operations_research::glop::VariableValues::UpdateDualPrices ( absl::Span< const RowIndex > row )

Note(user): this is the same as the code in RecomputeDualPrices(), but we do need the clear part.

Definition at line 292 of file variable_values.cc.

◆ UpdateGivenNonBasicVariables()

void operations_research::glop::VariableValues::UpdateGivenNonBasicVariables	(	absl::Span< const ColIndex >	cols_to_update,
		bool	update_basic_variables )

Batch version of SetNonBasicVariableValueFromStatus(). This function also updates the basic variable values and infeasibility statuses if update_basic_variables is true. The update is done in an incremental way and is thus more efficient than calling afterwards RecomputeBasicVariableValues() and RecomputeDualPrices().

Definition at line 203 of file variable_values.cc.

◆ UpdateOnPivoting()

void operations_research::glop::VariableValues::UpdateOnPivoting	(	const ScatteredColumn &	direction,
		ColIndex	entering_col,
		Fractional	step )

Updates the variable during a simplex pivot:

step * direction is subtracted from the basic variables value.
step is added to the entering column value.

Note(user): Some positions are ignored during the primal ratio test:

The rows for which direction_[row] < tolerance.
The non-zeros of direction_ignored_position_ in case of degeneracy. Such positions may result in basic variables going out of their bounds by more than the allowed tolerance. We could choose not to update these variables or not make them take out-of-bound values, but this would introduce artificial errors.

Note: there is no need to call variables_info_.Update() on basic variables when they change values. Note also that the status of entering_col will be updated later.

Definition at line 178 of file variable_values.cc.

◆ UpdatePrimalPhaseICosts()

template<typename Rows >

bool operations_research::glop::VariableValues::UpdatePrimalPhaseICosts	(	const Rows &	rows,
		DenseRow *	objective )

The primal phase I objective is related to the primal infeasible information above. The cost of a basic column will be 1 if the variable is above its upper bound by strictly more than the primal tolerance, and -1 if it is lower than its lower bound by strictly less than the same tolerance.

Returns true iff some cost changed.

Definition at line 188 of file variable_values.h.

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

ortools/glop/variable_values.h
ortools/glop/variable_values.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ VariableValues() [1/2]

◆ VariableValues() [2/2]

Member Function Documentation

◆ ComputeMaximumPrimalInfeasibility()

◆ ComputeMaximumPrimalResidual()

◆ ComputeSumOfPrimalInfeasibilities()

◆ Get()

◆ GetDenseRow()

◆ operator=()

◆ RecomputeBasicVariableValues()

◆ RecomputeDualPrices()

◆ ResetAllNonBasicVariableValues()

◆ Set()

◆ SetNonBasicVariableValueFromStatus()

◆ StatString()

◆ UpdateDualPrices()

◆ UpdateGivenNonBasicVariables()

◆ UpdateOnPivoting()

◆ UpdatePrimalPhaseICosts()