#include <primal_edge_norms.h>

Public Member Functions
	PrimalEdgeNorms (const CompactSparseMatrix &compact_matrix, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)

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

PrimalEdgeNorms &	operator= (const PrimalEdgeNorms &)=delete

void	Clear ()

bool	NeedsBasisRefactorization () const

DenseRow::ConstView	GetSquaredNorms ()

const DenseRow &	GetEdgeSquaredNorms ()

const DenseRow &	GetDevexWeights ()

const DenseRow &	GetMatrixColumnNorms ()

bool	TestEnteringEdgeNormPrecision (ColIndex entering_col, const ScatteredColumn &direction)

void	UpdateBeforeBasisPivot (ColIndex entering_col, ColIndex leaving_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)

void	SetParameters (const GlopParameters &parameters)
	Sets the algorithm parameters.

void	SetPricingRule (GlopParameters::PricingRule rule)
	This changes what GetSquaredNorms() returns.

void	AddRecomputationWatcher (bool *watcher)

std::string	StatString () const
	Returns a string with statistics about this class.

double	DeterministicTime () const
	Deterministic time used by the scalar product computation of this class.

Detailed Description

This class maintains the primal edge squared norms (and other variants) to be used in the primal pricing step. Instead of computing the needed values from scractch at each iteration, it is more efficient to update them incrementally for each basis pivot applied to the simplex basis matrix B.

Terminology:

To each non-basic column 'a' of a matrix A, we can associate an "edge" in the kernel of A equal to 1.0 on the index of 'a' and '-B^{-1}.a' on the basic variables.
'B^{-1}.a' is called the "right inverse" of 'a'.
The entering edge is the edge we are following during a simplex step, and we call "direction" the reverse of this edge restricted to the basic variables, i.e. the right inverse of the entering column.

Papers:

D. Goldfarb, J.K. Reid, "A practicable steepest-edge simplex algorithm" Mathematical Programming 12 (1977) 361-371, North-Holland. http://www.springerlink.com/content/g8335137n3j16934/
J.J. Forrest, D. Goldfarb, "Steepest-edge simplex algorithms for linear programming", Mathematical Programming 57 (1992) 341-374, North-Holland. http://www.springerlink.com/content/q645w3t2q229m248/
Ping-Qi Pan "A fast simplex algorithm for linear programming". http://www.optimization-online.org/DB_FILE/2007/10/1805.pdf
Ping-Qi Pan, "Efficient nested pricing in the simplex algorithm", http://www.optimization-online.org/DB_FILE/2007/10/1810.pdf

Definition at line 59 of file primal_edge_norms.h.

Constructor & Destructor Documentation

◆ PrimalEdgeNorms() [1/2]

operations_research::glop::PrimalEdgeNorms::PrimalEdgeNorms	(	const CompactSparseMatrix &	compact_matrix,
		const VariablesInfo &	variables_info,
		const BasisFactorization &	basis_factorization )

Takes references to the linear program data we need. Note that we assume that the matrix will never change in our back, but the other references are supposed to reflect the correct state.

Definition at line 34 of file primal_edge_norms.cc.

◆ PrimalEdgeNorms() [2/2]

operations_research::glop::PrimalEdgeNorms::PrimalEdgeNorms ( const PrimalEdgeNorms & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddRecomputationWatcher()

void operations_research::glop::PrimalEdgeNorms::AddRecomputationWatcher ( bool * watcher )

inline

Registers a boolean that will be set to true each time the norms are or will be recomputed. This allows anyone that depends on this to know that it cannot just assume an incremental changes and needs to updates its data. Important: UpdateBeforeBasisPivot() will not trigger this.

Definition at line 139 of file primal_edge_norms.h.

◆ Clear()

void operations_research::glop::PrimalEdgeNorms::Clear ( )

Clears, i.e. resets the object to its initial value. This will trigger a recomputation for the next Get*() method call.

Definition at line 49 of file primal_edge_norms.cc.

◆ DeterministicTime()

double operations_research::glop::PrimalEdgeNorms::DeterministicTime ( ) const

inline

Deterministic time used by the scalar product computation of this class.

Definition at line 145 of file primal_edge_norms.h.

◆ GetDevexWeights()

const DenseRow & operations_research::glop::PrimalEdgeNorms::GetDevexWeights ( )

Returns an approximation of the edges norms "devex". This is only valid if the caller properly called UpdateBeforeBasisPivot() before each basis pivot, or if this is the first call to this function after a Clear().

Definition at line 78 of file primal_edge_norms.cc.

◆ GetEdgeSquaredNorms()

const DenseRow & operations_research::glop::PrimalEdgeNorms::GetEdgeSquaredNorms ( )

Returns the primal edge squared norms. This is only valid if the caller properly called UpdateBeforeBasisPivot() before each basis pivot, or if this is the first call to this function after a Clear(). Note that only the relevant columns are filled.

Definition at line 73 of file primal_edge_norms.cc.

◆ GetMatrixColumnNorms()

const DenseRow & operations_research::glop::PrimalEdgeNorms::GetMatrixColumnNorms ( )

Returns the L2 norms of all the columns of A.

Note: this is currently not cleared by Clear().

Definition at line 83 of file primal_edge_norms.cc.

◆ GetSquaredNorms()

DenseRow::ConstView operations_research::glop::PrimalEdgeNorms::GetSquaredNorms ( )

Depending on the SetPricingRule(), this returns one of the "norms" vector below. Note that all norms are squared.

Definition at line 62 of file primal_edge_norms.cc.

◆ NeedsBasisRefactorization()

bool operations_research::glop::PrimalEdgeNorms::NeedsBasisRefactorization ( ) const

If this is true, then the caller must re-factorize the basis before the next call to GetEdgeSquaredNorms(). This is because the latter will recompute the norms from scratch and therefore needs a hightened precision and speed.

Definition at line 57 of file primal_edge_norms.cc.

◆ operator=()

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

delete

◆ SetParameters()

void operations_research::glop::PrimalEdgeNorms::SetParameters ( const GlopParameters & parameters )

inline

Sets the algorithm parameters.

Definition at line 126 of file primal_edge_norms.h.

◆ SetPricingRule()

void operations_research::glop::PrimalEdgeNorms::SetPricingRule ( GlopParameters::PricingRule rule )

inline

This changes what GetSquaredNorms() returns.

Definition at line 131 of file primal_edge_norms.h.

◆ StatString()

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

inline

Returns a string with statistics about this class.

Definition at line 142 of file primal_edge_norms.h.

◆ TestEnteringEdgeNormPrecision()

bool operations_research::glop::PrimalEdgeNorms::TestEnteringEdgeNormPrecision	(	ColIndex	entering_col,
		const ScatteredColumn &	direction )

Compares the current entering edge norm with its precise version (using the direction that wasn't avaible before) and triggers a full recomputation if the precision is not good enough (see recompute_edges_norm_threshold in GlopParameters). As a side effect, this replace the entering_col edge norm with its precise version.

Returns false if the old norm is less that 0.25 the new one. We might want to change the leaving variable if this happens.

Recompute the squared norm of the edge used during this iteration, i.e. the entering edge.

Definition at line 88 of file primal_edge_norms.cc.

◆ UpdateBeforeBasisPivot()

void operations_research::glop::PrimalEdgeNorms::UpdateBeforeBasisPivot	(	ColIndex	entering_col,
		ColIndex	leaving_col,
		RowIndex	leaving_row,
		const ScatteredColumn &	direction,
		UpdateRow *	update_row )

Updates any internal data BEFORE the given simplex pivot is applied to B.

Note

no updates are needed in case of a bound flip. The arguments are in order:

The index of the entering non-basic column of A.
The index in B of the leaving basic variable.
The 'direction', i.e. the right inverse of the entering column.
The update row (see UpdateRow), which will only be computed if needed.

Resets devex weights once in a while. If so, no need to update them before.

Definition at line 119 of file primal_edge_norms.cc.

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

ortools/glop/primal_edge_norms.h
ortools/glop/primal_edge_norms.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ PrimalEdgeNorms() [1/2]

◆ PrimalEdgeNorms() [2/2]

Member Function Documentation

◆ AddRecomputationWatcher()

◆ Clear()

◆ DeterministicTime()

◆ GetDevexWeights()

◆ GetEdgeSquaredNorms()

◆ GetMatrixColumnNorms()

◆ GetSquaredNorms()

◆ NeedsBasisRefactorization()

◆ operator=()

◆ SetParameters()

◆ SetPricingRule()

◆ StatString()

◆ TestEnteringEdgeNormPrecision()

◆ UpdateBeforeBasisPivot()