Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::glop::RevisedSimplex Class Reference

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.
 
RevisedSimplexoperator= (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 DenseRowGetReducedCosts () const
 
Fractional GetDualValue (RowIndex row) const
 
Fractional GetConstraintActivity (RowIndex row) const
 
VariableStatus GetVariableStatus (ColIndex col) const
 
ConstraintStatus GetConstraintStatus (RowIndex row) const
 
const BasisStateGetState () const
 
double DeterministicTime () const
 
bool objective_limit_reached () const
 
DenseColumn::ConstView GetDualSquaredNorms ()
 
const DenseBitRowGetNotBasicBitRow () const
 
const DenseRowGetPrimalRay () const
 
const DenseColumnGetDualRay () const
 
const DenseRowGetDualRayRowCombination () const
 This is the "dual ray" linear combination of the matrix rows.
 
ColIndex GetBasis (RowIndex row) const
 
const ScatteredRowGetUnitRowLeftInverse (RowIndex row)
 
RowToColMapping GetBasisVector () const
 
const BasisFactorizationGetBasisFactorization () 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 CompactSparseMatrixMatrixWithSlack () const
 
CompactSparseMatrixMutableTransposedMatrixWithSlack ()
 
DenseRowMutableLowerBounds ()
 
DenseRowMutableUpperBounds ()
 
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: