![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
Entry point of the revised simplex algorithm implementation. More...
Entry point of the revised simplex algorithm implementation.
Definition at line 132 of file revised_simplex.h.
#include <revised_simplex.h>
operations_research::glop::RevisedSimplex::RevisedSimplex | ( | ) |
Definition at line 105 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 136 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 3915 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 3894 of file revised_simplex.cc.
double operations_research::glop::RevisedSimplex::DeterministicTime | ( | ) | const |
Definition at line 812 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 789 of file revised_simplex.cc.
const BasisFactorization & operations_research::glop::RevisedSimplex::GetBasisFactorization | ( | ) | const |
Definition at line 791 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 756 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 762 of file revised_simplex.cc.
const DenseColumn & operations_research::glop::RevisedSimplex::GetDualRay | ( | ) | const |
Definition at line 779 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 784 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 746 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 726 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetObjectiveValue | ( | ) | const |
Definition at line 722 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 775 of file revised_simplex.cc.
ColIndex operations_research::glop::RevisedSimplex::GetProblemNumCols | ( | ) | const |
Definition at line 732 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 730 of file revised_simplex.cc.
ProblemStatus operations_research::glop::RevisedSimplex::GetProblemStatus | ( | ) | const |
Definition at line 718 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetReducedCost | ( | ColIndex | col | ) | const |
Definition at line 738 of file revised_simplex.cc.
const DenseRow & operations_research::glop::RevisedSimplex::GetReducedCosts | ( | ) | const |
Definition at line 742 of file revised_simplex.cc.
const BasisState & operations_research::glop::RevisedSimplex::GetState | ( | ) | const |
Definition at line 754 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 750 of file revised_simplex.cc.
Fractional operations_research::glop::RevisedSimplex::GetVariableValue | ( | ColIndex | col | ) | const |
Definition at line 734 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 142 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 260 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 158 of file revised_simplex.cc.
|
inline |
Definition at line 265 of file revised_simplex.h.
|
inline |
Definition at line 261 of file revised_simplex.h.
|
inline |
Definition at line 268 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 2677 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 3691 of file revised_simplex.cc.
void operations_research::glop::RevisedSimplex::SetRandom | ( | absl::BitGenRef | random | ) |
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 153 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 204 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.