![]() |
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
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 ¶meters) |
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) |
Entry point of the revised simplex algorithm implementation.
Definition at line 132 of file revised_simplex.h.
operations_research::glop::RevisedSimplex::RevisedSimplex | ( | ) |
Definition at line 103 of file revised_simplex.cc.
|
delete |
This type is neither copyable nor movable.
|
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.
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.
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.
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).
Definition at line 3883 of file revised_simplex.cc.
double operations_research::glop::RevisedSimplex::DeterministicTime | ( | ) | const |
Definition at line 809 of file revised_simplex.cc.
ColIndex operations_research::glop::RevisedSimplex::GetBasis | ( | RowIndex | row | ) | const |
Returns the index of the column in the basis and the basis factorization.
Definition at line 786 of file revised_simplex.cc.
const BasisFactorization & operations_research::glop::RevisedSimplex::GetBasisFactorization | ( | ) | const |
Definition at line 788 of file revised_simplex.cc.
|
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.
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.
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.
const DenseColumn & operations_research::glop::RevisedSimplex::GetDualRay | ( | ) | const |
Definition at line 776 of file revised_simplex.cc.
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.
|
inline |
Definition at line 191 of file revised_simplex.h.
Fractional operations_research::glop::RevisedSimplex::GetDualValue | ( | RowIndex | row | ) | const |
Definition at line 743 of file revised_simplex.cc.
|
inline |
Definition at line 195 of file revised_simplex.h.
int64_t operations_research::glop::RevisedSimplex::GetNumberOfIterations | ( | ) | const |
Definition at line 723 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetObjectiveValue | ( | ) | const |
Definition at line 719 of file revised_simplex.cc.
|
inline |
Definition at line 142 of file revised_simplex.h.
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.
Definition at line 772 of file revised_simplex.cc.
ColIndex operations_research::glop::RevisedSimplex::GetProblemNumCols | ( | ) | const |
Definition at line 729 of file revised_simplex.cc.
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.
ProblemStatus operations_research::glop::RevisedSimplex::GetProblemStatus | ( | ) | const |
Definition at line 715 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetReducedCost | ( | ColIndex | col | ) | const |
Definition at line 735 of file revised_simplex.cc.
const DenseRow & operations_research::glop::RevisedSimplex::GetReducedCosts | ( | ) | const |
Definition at line 739 of file revised_simplex.cc.
const BasisState & operations_research::glop::RevisedSimplex::GetState | ( | ) | const |
Definition at line 751 of file revised_simplex.cc.
|
inline |
Definition at line 220 of file revised_simplex.h.
VariableStatus operations_research::glop::RevisedSimplex::GetVariableStatus | ( | ColIndex | col | ) | const |
Definition at line 747 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetVariableValue | ( | ColIndex | col | ) | const |
Definition at line 731 of file revised_simplex.cc.
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.
Definition at line 141 of file revised_simplex.cc.
|
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.
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.
|
inline |
Definition at line 260 of file revised_simplex.h.
|
inline |
Definition at line 256 of file revised_simplex.h.
|
inline |
Definition at line 263 of file revised_simplex.h.
|
inline |
Definition at line 189 of file revised_simplex.h.
|
delete |
void operations_research::glop::RevisedSimplex::SetIntegralityScale | ( | ColIndex | col, |
Fractional | scale ) |
Definition at line 2674 of file revised_simplex.cc.
|
inline |
Definition at line 250 of file revised_simplex.h.
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.
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.
Status operations_research::glop::RevisedSimplex::Solve | ( | const LinearProgram & | lp, |
TimeLimit * | time_limit ) |
Solves the given linear program.
We accept two forms of LinearProgram:
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.
std::string operations_research::glop::RevisedSimplex::StatString | ( | ) |
Returns statistics about this class as a string.
Definition at line 3647 of file revised_simplex.cc.