Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
#include <update_row.h>
Public Member Functions | |
UpdateRow (const CompactSparseMatrix &matrix, const CompactSparseMatrix &transposed_matrix, const VariablesInfo &variables_info, const RowToColMapping &basis, const BasisFactorization &basis_factorization) | |
Takes references to the linear program data we need. | |
UpdateRow (const UpdateRow &)=delete | |
This type is neither copyable nor movable. | |
UpdateRow & | operator= (const UpdateRow &)=delete |
void | Invalidate () |
void | ComputeUnitRowLeftInverse (RowIndex leaving_row) |
void | ComputeUpdateRow (RowIndex leaving_row) |
const ScatteredRow & | GetUnitRowLeftInverse () const |
bool | IsComputedFor (RowIndex leaving_row) const |
Returns true if ComputeUpdateRow() was called since the last Invalidate(). | |
const DenseRow & | GetCoefficients () const |
absl::Span< const ColIndex > | GetNonZeroPositions () const |
Fractional | GetCoefficient (ColIndex col) const |
void | ComputeFullUpdateRow (RowIndex leaving_row, DenseRow *output) const |
void | SetParameters (const GlopParameters ¶meters) |
Sets the algorithm parameters. | |
std::string | StatString () const |
Returns statistics about this class as a string. | |
void | ComputeUpdateRowForBenchmark (const DenseRow &lhs, const std::string &algorithm) |
double | DeterministicTime () const |
Deterministic time used by the scalar product computation of this class. | |
const ScatteredRow & | ComputeAndGetUnitRowLeftInverse (RowIndex leaving_row) |
During a simplex iteration, when the basis 'leaving_row' has been selected, one of the main quantities needed in the primal or dual simplex algorithm is called the update row.
By definition, update_row[col] is the coefficient at position 'leaving_row' in the current basis of the column 'col' of the matrix A.
One efficient way to compute it is to compute the left inverse by B of the unit vector with a one at the given leaving_row, and then to take the scalar product of this left inverse with all the columns of A: update_row[col] = (unit_{leaving_row} . B^{-1}) . A_col
Definition at line 44 of file update_row.h.
operations_research::glop::UpdateRow::UpdateRow | ( | const CompactSparseMatrix & | matrix, |
const CompactSparseMatrix & | transposed_matrix, | ||
const VariablesInfo & | variables_info, | ||
const RowToColMapping & | basis, | ||
const BasisFactorization & | basis_factorization ) |
Takes references to the linear program data we need.
Definition at line 34 of file update_row.cc.
|
delete |
This type is neither copyable nor movable.
const ScatteredRow & operations_research::glop::UpdateRow::ComputeAndGetUnitRowLeftInverse | ( | RowIndex | leaving_row | ) |
This returns the asked unit row left inverse. It temporarily invalidate the class state by calling Invalidate().
Definition at line 62 of file update_row.cc.
void operations_research::glop::UpdateRow::ComputeFullUpdateRow | ( | RowIndex | leaving_row, |
DenseRow * | output ) const |
Computes the update row including all position and fill output with it. We only use this when ComputeUnitRowLeftInverse() has already been called and we CHECK that.
Fills the only position at one in the basic columns.
Fills the non-basic column.
Definition at line 330 of file update_row.cc.
void operations_research::glop::UpdateRow::ComputeUnitRowLeftInverse | ( | RowIndex | leaving_row | ) |
Computes the left inverse of the given unit row, and stores it in unit_row_left_inverse_. The result is computed only once if leaving_row do not change, this until the next Invalidate() call.
Definition at line 70 of file update_row.cc.
void operations_research::glop::UpdateRow::ComputeUpdateRow | ( | RowIndex | leaving_row | ) |
Computes the relevant coefficients (See GetIsRelevantBitRow() in VariablesInfo) of the update row. The result is only computed once if leaving_row do not change, this until the next Invalidate() call.
Number of entries that ComputeUpdatesRowWise() will need to look at.
Because we are about to do an expensive matrix-vector product, we make sure we drop small entries in the vector for the row-wise algorithm. We also computes its non-zeros to simplify the code below.
The case of size 1 happens often enough to deserve special code.
Number of entries that ComputeUpdatesColumnWise() will need to look at.
We use a multiplicative factor because these entries are often widely spread in memory. There is also some overhead to each fp operations.
Definition at line 87 of file update_row.cc.
void operations_research::glop::UpdateRow::ComputeUpdateRowForBenchmark | ( | const DenseRow & | lhs, |
const std::string & | algorithm ) |
Only used for testing. Computes as the update row the product 'lhs' times the linear program matrix given at construction. Only the relevant columns matter (see VariablesInfo) and 'algorithm' can be one of "column", "row" or "row_hypersparse".
Definition at line 178 of file update_row.cc.
|
inline |
Deterministic time used by the scalar product computation of this class.
Definition at line 110 of file update_row.h.
|
inline |
Definition at line 88 of file update_row.h.
const DenseRow & operations_research::glop::UpdateRow::GetCoefficients | ( | ) | const |
Returns the update coefficients and non-zero positions corresponding to the last call to ComputeUpdateRow().
Definition at line 194 of file update_row.cc.
absl::Span< const ColIndex > operations_research::glop::UpdateRow::GetNonZeroPositions | ( | ) | const |
Definition at line 196 of file update_row.cc.
const ScatteredRow & operations_research::glop::UpdateRow::GetUnitRowLeftInverse | ( | ) | const |
Returns the left inverse of the unit row as computed by the last call to ComputeUpdateRow().
Definition at line 58 of file update_row.cc.
void operations_research::glop::UpdateRow::Invalidate | ( | ) |
Invalidates the current update row and unit_row_left_inverse so the next call to ComputeUpdateRow() will recompute everything and not just return right away.
Definition at line 52 of file update_row.cc.
|
inline |
Returns true if ComputeUpdateRow() was called since the last Invalidate().
Definition at line 76 of file update_row.h.
void operations_research::glop::UpdateRow::SetParameters | ( | const GlopParameters & | parameters | ) |
Sets the algorithm parameters.
Definition at line 200 of file update_row.cc.
|
inline |
Returns statistics about this class as a string.
Definition at line 99 of file update_row.h.