Google OR-Tools v9.14
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...

Detailed Description

Entry point of the revised simplex algorithm implementation.

Definition at line 132 of file revised_simplex.h.

#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)
void SetRandom (absl::BitGenRef random)
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)

Constructor & Destructor Documentation

◆ RevisedSimplex() [1/2]

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

Definition at line 105 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 136 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 3915 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 3894 of file revised_simplex.cc.

◆ DeterministicTime()

double operations_research::glop::RevisedSimplex::DeterministicTime ( ) const
Todo
(user): Count what is missing.

Definition at line 812 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 789 of file revised_simplex.cc.

◆ GetBasisFactorization()

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

Definition at line 791 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 756 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 762 of file revised_simplex.cc.

◆ GetDualRay()

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

Definition at line 779 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 784 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 746 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 726 of file revised_simplex.cc.

◆ GetObjectiveValue()

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

Definition at line 722 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 775 of file revised_simplex.cc.

◆ GetProblemNumCols()

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

Definition at line 732 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 730 of file revised_simplex.cc.

◆ GetProblemStatus()

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

Definition at line 718 of file revised_simplex.cc.

◆ GetReducedCost()

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

Definition at line 738 of file revised_simplex.cc.

◆ GetReducedCosts()

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

Definition at line 742 of file revised_simplex.cc.

◆ GetState()

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

Definition at line 754 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 750 of file revised_simplex.cc.

◆ GetVariableValue()

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

Definition at line 734 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 142 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 260 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 158 of file revised_simplex.cc.

◆ MutableLowerBounds()

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

Definition at line 265 of file revised_simplex.h.

◆ MutableTransposedMatrixWithSlack()

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

Definition at line 261 of file revised_simplex.h.

◆ MutableUpperBounds()

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

Definition at line 268 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 2677 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 3691 of file revised_simplex.cc.

◆ SetRandom()

void operations_research::glop::RevisedSimplex::SetRandom ( absl::BitGenRef random)
Note
SetParameters() calls SetRandom() on its implementation, so if you want to set the parameters and then set the random generator, you should call SetRandom() after SetParameters().

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 153 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 204 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: