Entry point of the revised simplex algorithm implementation. More...

#include <revised_simplex.h>

Public Member Functions
	RevisedSimplex ()

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

RevisedSimplex &	operator= (const RevisedSimplex &)=delete

void	SetParameters (const GlopParameters &parameters)
	Sets or gets the algorithm parameters to be used on the next Solve().

const GlopParameters &	GetParameters () const

ABSL_MUST_USE_RESULT Status	Solve (const LinearProgram &lp, TimeLimit *time_limit)

void	ClearStateForNextSolve ()

void	LoadStateForNextSolve (const BasisState &state)
	Uses the given state as a warm-start for the next Solve() call.

void	SetStartingVariableValuesForNextSolve (const DenseRow &values)

RowIndex	GetProblemNumRows () const
	Getters to retrieve all the information computed by the last Solve().

ColIndex	GetProblemNumCols () const

ProblemStatus	GetProblemStatus () const

Fractional	GetObjectiveValue () const

int64_t	GetNumberOfIterations () const

Fractional	GetVariableValue (ColIndex col) const

Fractional	GetReducedCost (ColIndex col) const

const DenseRow &	GetReducedCosts () const

Fractional	GetDualValue (RowIndex row) const

Fractional	GetConstraintActivity (RowIndex row) const

VariableStatus	GetVariableStatus (ColIndex col) const

ConstraintStatus	GetConstraintStatus (RowIndex row) const

const BasisState &	GetState () const

double	DeterministicTime () const

bool	objective_limit_reached () const

DenseColumn::ConstView	GetDualSquaredNorms ()

const DenseBitRow &	GetNotBasicBitRow () const

const DenseRow &	GetPrimalRay () const

const DenseColumn &	GetDualRay () const

const DenseRow &	GetDualRayRowCombination () const
	This is the "dual ray" linear combination of the matrix rows.

ColIndex	GetBasis (RowIndex row) const

const ScatteredRow &	GetUnitRowLeftInverse (RowIndex row)

RowToColMapping	GetBasisVector () const

const BasisFactorization &	GetBasisFactorization () const

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

RowMajorSparseMatrix	ComputeDictionary (const DenseRow *column_scales)

void	ComputeBasicVariablesForState (const LinearProgram &linear_program, const BasisState &state)

void	ClearIntegralityScales ()

void	SetIntegralityScale (ColIndex col, Fractional scale)

void	SetLogger (SolverLogger *logger)

const CompactSparseMatrix &	MatrixWithSlack () const

CompactSparseMatrix *	MutableTransposedMatrixWithSlack ()

DenseRow *	MutableLowerBounds ()

DenseRow *	MutableUpperBounds ()

ABSL_MUST_USE_RESULT Status	MinimizeFromTransposedMatrixWithSlack (const DenseRow &objective, Fractional objective_scaling_factor, Fractional objective_offset, TimeLimit *time_limit)

Detailed Description

Entry point of the revised simplex algorithm implementation.

Definition at line 132 of file revised_simplex.h.

Constructor & Destructor Documentation

◆ RevisedSimplex() [1/2]

operations_research::glop::RevisedSimplex::RevisedSimplex ( )

Definition at line 103 of file revised_simplex.cc.

◆ RevisedSimplex() [2/2]

operations_research::glop::RevisedSimplex::RevisedSimplex ( const RevisedSimplex & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ ClearIntegralityScales()

void operations_research::glop::RevisedSimplex::ClearIntegralityScales ( )

inline

This is used in a MIP context to polish the final basis. We assume that the columns for which SetIntegralityScale() has been called correspond to integral variable once multiplied by the given factor.

Definition at line 247 of file revised_simplex.h.

◆ ClearStateForNextSolve()

void operations_research::glop::RevisedSimplex::ClearStateForNextSolve ( )

Do not use the current solution as a warm-start for the next Solve(). The next Solve() will behave as if the class just got created.

Definition at line 135 of file revised_simplex.cc.

◆ ComputeBasicVariablesForState()

void operations_research::glop::RevisedSimplex::ComputeBasicVariablesForState	(	const LinearProgram &	linear_program,
		const BasisState &	state )

Initializes the matrix for the given 'linear_program' and 'state' and computes the variable values for basic variables using non-basic variables.

Definition at line 3904 of file revised_simplex.cc.

◆ ComputeDictionary()

util_intops::StrongVector< RowIndex, SparseRow > operations_research::glop::RevisedSimplex::ComputeDictionary ( const DenseRow * column_scales )

Computes the dictionary B^-1*N on-the-fly row by row. Returns the resulting matrix as a vector of sparse rows so that it is easy to use it on the left side in the matrix multiplication. Runs in O(num_non_zeros_in_matrix).

Todo: (user): Use row scales as well.

Definition at line 3883 of file revised_simplex.cc.

◆ DeterministicTime()

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

Todo: (user): Count what is missing.

Definition at line 809 of file revised_simplex.cc.

◆ GetBasis()

ColIndex operations_research::glop::RevisedSimplex::GetBasis ( RowIndex row ) const

Returns the index of the column in the basis and the basis factorization.

Note: the order of the column in the basis is important since it is the one used by the various solve functions provided by the BasisFactorization class.

Definition at line 786 of file revised_simplex.cc.

◆ GetBasisFactorization()

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

Definition at line 788 of file revised_simplex.cc.

◆ GetBasisVector()

RowToColMapping operations_research::glop::RevisedSimplex::GetBasisVector ( ) const

inline

Returns a copy of basis_ vector for outside applications (like cuts) to have the correspondence between rows and columns of the dictionary.

Definition at line 226 of file revised_simplex.h.

◆ GetConstraintActivity()

Fractional operations_research::glop::RevisedSimplex::GetConstraintActivity ( RowIndex row ) const

Note the negative sign since the slack variable is such that constraint_activity + slack_value = 0.

Definition at line 753 of file revised_simplex.cc.

◆ GetConstraintStatus()

ConstraintStatus operations_research::glop::RevisedSimplex::GetConstraintStatus ( RowIndex row ) const

The status of the given constraint is the same as the status of the associated slack variable with a change of sign.

Definition at line 759 of file revised_simplex.cc.

◆ GetDualRay()

const DenseColumn & operations_research::glop::RevisedSimplex::GetDualRay ( ) const

Definition at line 776 of file revised_simplex.cc.

◆ GetDualRayRowCombination()

const DenseRow & operations_research::glop::RevisedSimplex::GetDualRayRowCombination ( ) const

This is the "dual ray" linear combination of the matrix rows.

Definition at line 781 of file revised_simplex.cc.

◆ GetDualSquaredNorms()

DenseColumn::ConstView operations_research::glop::RevisedSimplex::GetDualSquaredNorms ( )

inline

Definition at line 191 of file revised_simplex.h.

◆ GetDualValue()

Fractional operations_research::glop::RevisedSimplex::GetDualValue ( RowIndex row ) const

Definition at line 743 of file revised_simplex.cc.

◆ GetNotBasicBitRow()

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

inline

Definition at line 195 of file revised_simplex.h.

◆ GetNumberOfIterations()

int64_t operations_research::glop::RevisedSimplex::GetNumberOfIterations ( ) const

Definition at line 723 of file revised_simplex.cc.

◆ GetObjectiveValue()

Fractional operations_research::glop::RevisedSimplex::GetObjectiveValue ( ) const

Definition at line 719 of file revised_simplex.cc.

◆ GetParameters()

const GlopParameters & operations_research::glop::RevisedSimplex::GetParameters ( ) const

inline

Definition at line 142 of file revised_simplex.h.

◆ GetPrimalRay()

const DenseRow & operations_research::glop::RevisedSimplex::GetPrimalRay ( ) const

If the problem status is PRIMAL_UNBOUNDED (respectively DUAL_UNBOUNDED), then the solver has a corresponding primal (respectively dual) ray to show the unboundness. From a primal (respectively dual) feasible solution any positive multiple of this ray can be added to the solution and keep it feasible. Moreover, by doing so, the objective of the problem will improve and its magnitude will go to infinity.

Note: when the problem is DUAL_UNBOUNDED, the dual ray is also known as the Farkas proof of infeasibility of the problem.

Definition at line 772 of file revised_simplex.cc.

◆ GetProblemNumCols()

ColIndex operations_research::glop::RevisedSimplex::GetProblemNumCols ( ) const

Definition at line 729 of file revised_simplex.cc.

◆ GetProblemNumRows()

RowIndex operations_research::glop::RevisedSimplex::GetProblemNumRows ( ) const

Getters to retrieve all the information computed by the last Solve().

Definition at line 727 of file revised_simplex.cc.

◆ GetProblemStatus()

ProblemStatus operations_research::glop::RevisedSimplex::GetProblemStatus ( ) const

Definition at line 715 of file revised_simplex.cc.

◆ GetReducedCost()

Fractional operations_research::glop::RevisedSimplex::GetReducedCost ( ColIndex col ) const

Definition at line 735 of file revised_simplex.cc.

◆ GetReducedCosts()

const DenseRow & operations_research::glop::RevisedSimplex::GetReducedCosts ( ) const

Definition at line 739 of file revised_simplex.cc.

◆ GetState()

const BasisState & operations_research::glop::RevisedSimplex::GetState ( ) const

Definition at line 751 of file revised_simplex.cc.

◆ GetUnitRowLeftInverse()

const ScatteredRow & operations_research::glop::RevisedSimplex::GetUnitRowLeftInverse ( RowIndex row )

inline

Definition at line 220 of file revised_simplex.h.

◆ GetVariableStatus()

VariableStatus operations_research::glop::RevisedSimplex::GetVariableStatus ( ColIndex col ) const

Definition at line 747 of file revised_simplex.cc.

◆ GetVariableValue()

Fractional operations_research::glop::RevisedSimplex::GetVariableValue ( ColIndex col ) const

Definition at line 731 of file revised_simplex.cc.

◆ LoadStateForNextSolve()

void operations_research::glop::RevisedSimplex::LoadStateForNextSolve ( const BasisState & state )

Uses the given state as a warm-start for the next Solve() call.

We avoid marking the state as set externally if it is the same as the current one.

Todo: (user): Add comparison operator.

Definition at line 141 of file revised_simplex.cc.

◆ MatrixWithSlack()

const CompactSparseMatrix & operations_research::glop::RevisedSimplex::MatrixWithSlack ( ) const

inline

Advanced usage. For fast incremental call to the solver, it is better not to use LinearProgram at all. This api allows to directly modify the internal data of glop and then call solve.

Definition at line 255 of file revised_simplex.h.

◆ MinimizeFromTransposedMatrixWithSlack()

Status operations_research::glop::RevisedSimplex::MinimizeFromTransposedMatrixWithSlack	(	const DenseRow &	objective,
		Fractional	objective_scaling_factor,
		Fractional	objective_offset,
		TimeLimit *	time_limit )

The source of truth is the transposed matrix.

Copy objective

Initialize variable infos from the mutated bounds.

Fast track if we just changed variable bounds.

Definition at line 157 of file revised_simplex.cc.

◆ MutableLowerBounds()

DenseRow * operations_research::glop::RevisedSimplex::MutableLowerBounds ( )

inline

Definition at line 260 of file revised_simplex.h.

◆ MutableTransposedMatrixWithSlack()

CompactSparseMatrix * operations_research::glop::RevisedSimplex::MutableTransposedMatrixWithSlack ( )

inline

Definition at line 256 of file revised_simplex.h.

◆ MutableUpperBounds()

DenseRow * operations_research::glop::RevisedSimplex::MutableUpperBounds ( )

inline

Definition at line 263 of file revised_simplex.h.

◆ objective_limit_reached()

bool operations_research::glop::RevisedSimplex::objective_limit_reached ( ) const

inline

Definition at line 189 of file revised_simplex.h.

◆ operator=()

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

delete

◆ SetIntegralityScale()

void operations_research::glop::RevisedSimplex::SetIntegralityScale	(	ColIndex	col,
		Fractional	scale )

Definition at line 2674 of file revised_simplex.cc.

◆ SetLogger()

void operations_research::glop::RevisedSimplex::SetLogger ( SolverLogger * logger )

inline

Definition at line 250 of file revised_simplex.h.

◆ SetParameters()

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

Sets or gets the algorithm parameters to be used on the next Solve().

Definition at line 3683 of file revised_simplex.cc.

◆ SetStartingVariableValuesForNextSolve()

void operations_research::glop::RevisedSimplex::SetStartingVariableValuesForNextSolve ( const DenseRow & values )

Advanced usage. While constructing the initial basis, if this is called then we will use these values as the initial starting value for the FREE variables.

Definition at line 152 of file revised_simplex.cc.

◆ Solve()

Status operations_research::glop::RevisedSimplex::Solve	(	const LinearProgram &	lp,
		TimeLimit *	time_limit )

Solves the given linear program.

We accept two forms of LinearProgram:

The lp can be in the equations form Ax = 0 created by LinearProgram::AddSlackVariablesForAllRows(), i.e. the rightmost square submatrix of A is an identity matrix, all its columns have been marked as slack variables, and the bounds of all constraints have been set to 0.
If not, we will convert it internally while copying it to the internal structure used.

By default, the algorithm tries to exploit the computation done during the last Solve() call. It will analyze the difference of the new linear program and try to use the previously computed solution as a warm-start. To disable this behavior or give explicit warm-start data, use one of the State*() functions below.

Definition at line 203 of file revised_simplex.cc.

◆ StatString()

std::string operations_research::glop::RevisedSimplex::StatString ( )

Returns statistics about this class as a string.

Definition at line 3647 of file revised_simplex.cc.

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

ortools/glop/revised_simplex.h
ortools/glop/revised_simplex.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ RevisedSimplex() [1/2]

◆ RevisedSimplex() [2/2]

Member Function Documentation

◆ ClearIntegralityScales()

◆ ClearStateForNextSolve()

◆ ComputeBasicVariablesForState()

◆ ComputeDictionary()

◆ DeterministicTime()

◆ GetBasis()

◆ GetBasisFactorization()

◆ GetBasisVector()

◆ GetConstraintActivity()

◆ GetConstraintStatus()

◆ GetDualRay()

◆ GetDualRayRowCombination()

◆ GetDualSquaredNorms()

◆ GetDualValue()

◆ GetNotBasicBitRow()

◆ GetNumberOfIterations()

◆ GetObjectiveValue()

◆ GetParameters()

◆ GetPrimalRay()

◆ GetProblemNumCols()

◆ GetProblemNumRows()

◆ GetProblemStatus()

◆ GetReducedCost()

◆ GetReducedCosts()

◆ GetState()

◆ GetUnitRowLeftInverse()

◆ GetVariableStatus()

◆ GetVariableValue()

◆ LoadStateForNextSolve()

◆ MatrixWithSlack()

◆ MinimizeFromTransposedMatrixWithSlack()

◆ MutableLowerBounds()

◆ MutableTransposedMatrixWithSlack()

◆ MutableUpperBounds()

◆ objective_limit_reached()

◆ operator=()

◆ SetIntegralityScale()

◆ SetLogger()

◆ SetParameters()

◆ SetStartingVariableValuesForNextSolve()

◆ Solve()

◆ StatString()