#include <basis_representation.h>

Public Member Functions
	BasisFactorization (const CompactSparseMatrix compact_matrix, const RowToColMapping basis)

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

BasisFactorization &	operator= (const BasisFactorization &)=delete

virtual	~BasisFactorization ()

void	SetParameters (const GlopParameters &parameters)
	Sets the parameters for this component.

const ColumnPermutation &	GetColumnPermutation () const

void	SetColumnPermutationToIdentity ()

void	Clear ()

ABSL_MUST_USE_RESULT Status	Initialize ()

RowToColMapping	ComputeInitialBasis (const std::vector< ColIndex > &candidates)

RowIndex	GetNumberOfRows () const
	Return the number of rows in the basis.

ABSL_MUST_USE_RESULT Status	Refactorize ()

ABSL_MUST_USE_RESULT Status	ForceRefactorization ()

bool	IsRefactorized () const
	Returns true if the factorization was just recomputed.

ABSL_MUST_USE_RESULT Status	Update (ColIndex entering_col, RowIndex leaving_variable_row, const ScatteredColumn &direction)

void	LeftSolve (ScatteredRow *y) const
	Left solves the system y.B = rhs, where y initially contains rhs.

void	LeftSolveForUnitRow (ColIndex j, ScatteredRow *y) const

void	TemporaryLeftSolveForUnitRow (ColIndex j, ScatteredRow *y) const
	Same as LeftSolveForUnitRow() but does not update any internal data.

void	RightSolve (ScatteredColumn *d) const
	Right solves the system B.d = a where the input is the initial value of d.

void	RightSolveForProblemColumn (ColIndex col, ScatteredColumn *d) const

const DenseColumn &	RightSolveForTau (const ScatteredColumn &a) const

Fractional	RightSolveSquaredNorm (const ColumnView &a) const

Fractional	DualEdgeSquaredNorm (RowIndex row) const

Fractional	ComputeOneNormConditionNumber () const

Fractional	ComputeInfinityNormConditionNumber () const

Fractional	ComputeInfinityNormConditionNumberUpperBound () const

Fractional	ComputeOneNorm () const

Fractional	ComputeInfinityNorm () const

Fractional	ComputeInverseOneNorm () const

Fractional	ComputeInverseInfinityNorm () const
	Computes the infinity-norm of the inverse of B.

std::string	StatString () const

void	ResetStats ()

double	DeterministicTime () const

int	NumUpdates () const
	Returns the number of updates since last refactorization.

Detailed Description

A basis factorization is the product of an eta factorization and a L.U decomposition, i.e. B = L.U.E_0.E_1. ... .E_{k-1} It is used to solve two systems:

B.d = a where a is the entering column.
y.B = c where c is the objective row.

To speed-up and improve stability the factorization is refactorized at least every 'refactorization_period' updates.

This class does not take ownership of the underlying matrix and basis, and thus they must outlive this class (and keep the same address in memory).

Definition at line 160 of file basis_representation.h.

Constructor & Destructor Documentation

◆ BasisFactorization() [1/2]

operations_research::glop::BasisFactorization::BasisFactorization	(	const CompactSparseMatrix *	compact_matrix,
		const RowToColMapping *	basis )

BasisFactorization

Definition at line 187 of file basis_representation.cc.

◆ BasisFactorization() [2/2]

operations_research::glop::BasisFactorization::BasisFactorization ( const BasisFactorization & )

delete

This type is neither copyable nor movable.

◆ ~BasisFactorization()

operations_research::glop::BasisFactorization::~BasisFactorization ( )

virtualdefault

Member Function Documentation

◆ Clear()

void operations_research::glop::BasisFactorization::Clear ( )

Clears the factorization and resets it to an identity matrix of size given by matrix_.num_rows().

Definition at line 203 of file basis_representation.cc.

◆ ComputeInfinityNorm()

Fractional operations_research::glop::BasisFactorization::ComputeInfinityNorm ( ) const

Computes the infinity-norm of B. The infinity-norm A is defined as max_i sum_j a_ij http://en.wikipedia.org/wiki/Matrix_norm

Definition at line 542 of file basis_representation.cc.

◆ ComputeInfinityNormConditionNumber()

Fractional operations_research::glop::BasisFactorization::ComputeInfinityNormConditionNumber ( ) const

Definition at line 602 of file basis_representation.cc.

◆ ComputeInfinityNormConditionNumberUpperBound()

Fractional operations_research::glop::BasisFactorization::ComputeInfinityNormConditionNumberUpperBound ( ) const

Definition at line 607 of file basis_representation.cc.

◆ ComputeInitialBasis()

RowToColMapping operations_research::glop::BasisFactorization::ComputeInitialBasis ( const std::vector< ColIndex > & candidates )

This mainly forward the call to LuFactorization::ComputeInitialBasis().

Note: once this is called, one would need to call Initialize() to actually create the factorization. The only side effect of this is to update the deterministic time.

Todo: (user): This "double" factorization is a bit inefficient, and we should probably Initialize() right away the factorization with the new basis, but more code is needed for that. It is also not that easy also because we want to permute all the added slack first.

Definition at line 223 of file basis_representation.cc.

◆ ComputeInverseInfinityNorm()

Fractional operations_research::glop::BasisFactorization::ComputeInverseInfinityNorm ( ) const

Computes the infinity-norm of the inverse of B.

Get a column of the matrix inverse.

Compute sum_j inverse_ij.

Compute max_i sum_j inverse_ij

Definition at line 573 of file basis_representation.cc.

◆ ComputeInverseOneNorm()

Fractional operations_research::glop::BasisFactorization::ComputeInverseOneNorm ( ) const

Computes the 1-norm of the inverse of B. For this we iteratively solve B.x = e_j, where e_j is the jth unit vector. The result of this computation is the jth column of B^-1.

Todo: (user): try to merge the computation of the norm of inverses with that of MatrixView. Maybe use a wrapper class for InverseMatrix.

Get a column of the matrix inverse.

Compute sum_i inverse_ij.

Compute max_j sum_i inverse_ij

Definition at line 551 of file basis_representation.cc.

◆ ComputeOneNorm()

Fractional operations_research::glop::BasisFactorization::ComputeOneNorm ( ) const

Computes the 1-norm of B. The 1-norm A is defined as max_j sum_i a_ij http://en.wikipedia.org/wiki/Matrix_norm

Definition at line 536 of file basis_representation.cc.

◆ ComputeOneNormConditionNumber()

Fractional operations_research::glop::BasisFactorization::ComputeOneNormConditionNumber ( ) const

Computes the condition number of B. For a given norm, this is the matrix norm times the norm of its inverse. A condition number greater than 1E7 will lead to precision problems.

Definition at line 597 of file basis_representation.cc.

◆ DeterministicTime()

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

The deterministic time used by this class. It is incremented for each solve and each factorization.

Definition at line 615 of file basis_representation.cc.

◆ DualEdgeSquaredNorm()

Fractional operations_research::glop::BasisFactorization::DualEdgeSquaredNorm ( RowIndex row ) const

Returns the norm of (B^T)^{-1}.e_row where e is an unit vector. This is a bit faster and avoids polluting the stats of LeftSolve(). It can be called only when IsRefactorized() is true.

Definition at line 517 of file basis_representation.cc.

◆ ForceRefactorization()

Status operations_research::glop::BasisFactorization::ForceRefactorization ( )

Like Refactorize(), but do it even if IsRefactorized() is true. Call this if the underlying basis_ changed and Update() wasn't called.

Definition at line 239 of file basis_representation.cc.

◆ GetColumnPermutation()

const ColumnPermutation & operations_research::glop::BasisFactorization::GetColumnPermutation ( ) const

inline

Returns the column permutation used by the LU factorization. This call only makes sense if the basis was just refactorized.

Definition at line 182 of file basis_representation.h.

◆ GetNumberOfRows()

RowIndex operations_research::glop::BasisFactorization::GetNumberOfRows ( ) const

inline

Return the number of rows in the basis.

Definition at line 218 of file basis_representation.h.

◆ Initialize()

Status operations_research::glop::BasisFactorization::Initialize ( )

Clears the factorization and initializes the class using the current matrix_ and basis_. This is fast if IsIdentityBasis() is true, otherwise it will trigger a refactorization and will return an error if the matrix could not be factorized.

Definition at line 216 of file basis_representation.cc.

◆ IsRefactorized()

bool operations_research::glop::BasisFactorization::IsRefactorized ( ) const

Returns true if the factorization was just recomputed.

Definition at line 232 of file basis_representation.cc.

◆ LeftSolve()

void operations_research::glop::BasisFactorization::LeftSolve ( ScatteredRow * y ) const

Left solves the system y.B = rhs, where y initially contains rhs.

Definition at line 348 of file basis_representation.cc.

◆ LeftSolveForUnitRow()

void operations_research::glop::BasisFactorization::LeftSolveForUnitRow	(	ColIndex	j,
		ScatteredRow *	y ) const

Left solves the system y.B = e_j, where e_j has only 1 non-zero coefficient of value 1.0 at position 'j'.

If the leaving index is the same, we can reuse the column! Note also that since we do a left solve for a unit row using an upper triangular matrix, all positions in front of the unit will be zero (modulo the column permutation).

We only keep the intermediate result needed for the optimized tau_ computation if it was computed after the last time this was called.

Definition at line 406 of file basis_representation.cc.

◆ NumUpdates()

int operations_research::glop::BasisFactorization::NumUpdates ( ) const

inline

Returns the number of updates since last refactorization.

Definition at line 311 of file basis_representation.h.

◆ operator=()

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

delete

◆ Refactorize()

Status operations_research::glop::BasisFactorization::Refactorize ( )

Clears eta factorization and refactorizes LU. Nothing happens if this is called on an already refactorized basis. Returns an error if the matrix could not be factorized: i.e. not a basis.

Definition at line 234 of file basis_representation.cc.

◆ ResetStats()

void operations_research::glop::BasisFactorization::ResetStats ( )

inline

Definition at line 304 of file basis_representation.h.

◆ RightSolve()

void operations_research::glop::BasisFactorization::RightSolve ( ScatteredColumn * d ) const

Right solves the system B.d = a where the input is the initial value of d.

Definition at line 364 of file basis_representation.cc.

◆ RightSolveForProblemColumn()

void operations_research::glop::BasisFactorization::RightSolveForProblemColumn	(	ColIndex	col,
		ScatteredColumn *	d ) const

Same as RightSolve() for matrix.column(col). This also exploits its sparsity.

Todo: (user): if right_pool_mapping_[col] != kInvalidCol, we can reuse it and just apply the last rank one update since it was computed.

The sort is needed if we want to have the same behavior for the sparse or hyper-sparse version.

Definition at line 474 of file basis_representation.cc.

◆ RightSolveForTau()

const DenseColumn & operations_research::glop::BasisFactorization::RightSolveForTau ( const ScatteredColumn & a ) const

Specialized version for ComputeTau() in DualEdgeNorms. This reuses an intermediate result of the last LeftSolveForUnitRow() in order to save a permutation if it is available. Note that the input 'a' should always be equal to the last result of LeftSolveForUnitRow() and will be used for a DCHECK() or if the intermediate result wasn't kept.

Once used, the intermediate result is overwritten, so RightSolveForTau() can no longer use the optimized algorithm.

Definition at line 380 of file basis_representation.cc.

◆ RightSolveSquaredNorm()

Fractional operations_research::glop::BasisFactorization::RightSolveSquaredNorm ( const ColumnView & a ) const

Returns the norm of B^{-1}.a, this is a specific function because it is a bit faster and it avoids polluting the stats of RightSolve(). It can be called only when IsRefactorized() is true.

Definition at line 509 of file basis_representation.cc.

◆ SetColumnPermutationToIdentity()

void operations_research::glop::BasisFactorization::SetColumnPermutationToIdentity ( )

inline

Sets the column permutation used by the LU factorization to the identity. Hense the Solve() results will be computed without this permutation. This call only makes sense if the basis was just refactorized.

Definition at line 190 of file basis_representation.h.

◆ SetParameters()

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

inline

Sets the parameters for this component.

Definition at line 172 of file basis_representation.h.

◆ StatString()

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

inline

Stats related function.

Note: ResetStats() could be const, but until needed it is not to prevent anyone holding a const BasisFactorization& to call it.

Definition at line 301 of file basis_representation.h.

◆ TemporaryLeftSolveForUnitRow()

void operations_research::glop::BasisFactorization::TemporaryLeftSolveForUnitRow	(	ColIndex	j,
		ScatteredRow *	y ) const

Same as LeftSolveForUnitRow() but does not update any internal data.

Definition at line 461 of file basis_representation.cc.

◆ Update()

Status operations_research::glop::BasisFactorization::Update	(	ColIndex	entering_col,
		RowIndex	leaving_variable_row,
		const ScatteredColumn &	direction )

Updates the factorization. The 'eta' column will be modified with a swap to avoid a copy (only if the standard eta update is used). Returns an error if the matrix could not be factorized: i.e. not a basis.

Note: in addition to the logic here, we also refactorize when we detect numerical imprecisions. There is various tests for that during an iteration.

We try to equilibrate the factorization time with the EXTRA solve time incurred since the last factorization.

Note(user): The deterministic time is not really super precise for now. We tend to undercount the factorization, but this tends to favorize more refactorization which is good for numerical stability.

Note(user): in some rare case (to investigate!) MiddleProductFormUpdate() will trigger a full refactorization. Because of this, it is important to increment num_updates_ first as this counter is used by IsRefactorized().

Definition at line 310 of file basis_representation.cc.

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

ortools/glop/basis_representation.h
ortools/glop/basis_representation.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ BasisFactorization() [1/2]

◆ BasisFactorization() [2/2]

◆ ~BasisFactorization()

Member Function Documentation

◆ Clear()

◆ ComputeInfinityNorm()

◆ ComputeInfinityNormConditionNumber()

◆ ComputeInfinityNormConditionNumberUpperBound()

◆ ComputeInitialBasis()

◆ ComputeInverseInfinityNorm()

◆ ComputeInverseOneNorm()

◆ ComputeOneNorm()

◆ ComputeOneNormConditionNumber()

◆ DeterministicTime()

◆ DualEdgeSquaredNorm()

◆ ForceRefactorization()

◆ GetColumnPermutation()

◆ GetNumberOfRows()

◆ Initialize()

◆ IsRefactorized()

◆ LeftSolve()

◆ LeftSolveForUnitRow()

◆ NumUpdates()

◆ operator=()

◆ Refactorize()

◆ ResetStats()

◆ RightSolve()

◆ RightSolveForProblemColumn()

◆ RightSolveForTau()

◆ RightSolveSquaredNorm()

◆ SetColumnPermutationToIdentity()

◆ SetParameters()

◆ StatString()

◆ TemporaryLeftSolveForUnitRow()

◆ Update()