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

#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.
 
UpdateRowoperator= (const UpdateRow &)=delete
 
void Invalidate ()
 
void ComputeUnitRowLeftInverse (RowIndex leaving_row)
 
void ComputeUpdateRow (RowIndex leaving_row)
 
const ScatteredRowGetUnitRowLeftInverse () const
 
bool IsComputedFor (RowIndex leaving_row) const
 Returns true if ComputeUpdateRow() was called since the last Invalidate().
 
const DenseRowGetCoefficients () const
 
absl::Span< const ColIndex > GetNonZeroPositions () const
 
Fractional GetCoefficient (ColIndex col) const
 
void ComputeFullUpdateRow (RowIndex leaving_row, DenseRow *output) const
 
void SetParameters (const GlopParameters &parameters)
 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 ScatteredRowComputeAndGetUnitRowLeftInverse (RowIndex leaving_row)
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ UpdateRow() [1/2]

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.

◆ UpdateRow() [2/2]

operations_research::glop::UpdateRow::UpdateRow ( const UpdateRow & )
delete

This type is neither copyable nor movable.

Member Function Documentation

◆ ComputeAndGetUnitRowLeftInverse()

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.

◆ ComputeFullUpdateRow()

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.

Note
we use the same algo as ComputeUpdatesColumnWise() here. The others version might be faster, but this is called at most once per solve, so it shouldn't be too bad.

Fills the only position at one in the basic columns.

Fills the non-basic column.

Definition at line 330 of file update_row.cc.

◆ ComputeUnitRowLeftInverse()

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.

Todo
(user): Refactorize if the estimated accuracy is above a threshold.

Definition at line 70 of file update_row.cc.

◆ ComputeUpdateRow()

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.

Todo
(user): So far we didn't generalize the use of drop tolerances everywhere in the solver, so we make sure to not modify unit_row_left_inverse_ that is also used elsewhere. However, because of that, we will not get the exact same result depending on the algortihm used below because the ComputeUpdatesColumnWise() will still use these small entries (no complexity changes).

The case of size 1 happens often enough to deserve special code.

Todo
(user): The impact is not as high as I hopped though, so not too important.

Number of entries that ComputeUpdatesColumnWise() will need to look at.

Note
the thresholds were chosen (more or less) from the result of the microbenchmark tests of this file in September 2013.
Todo
(user): automate the computation of these constants at run-time?

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.

◆ ComputeUpdateRowForBenchmark()

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.

◆ DeterministicTime()

double operations_research::glop::UpdateRow::DeterministicTime ( ) const
inline

Deterministic time used by the scalar product computation of this class.

Definition at line 110 of file update_row.h.

◆ GetCoefficient()

Fractional operations_research::glop::UpdateRow::GetCoefficient ( ColIndex col) const
inline

Definition at line 88 of file update_row.h.

◆ GetCoefficients()

const DenseRow & operations_research::glop::UpdateRow::GetCoefficients ( ) const

Returns the update coefficients and non-zero positions corresponding to the last call to ComputeUpdateRow().

Todo
(user): Consider returning a packed vector of coefficient parallel to GetNonZeroPositions() instead. It should be fast to compute and iteration later should be quicker.

Definition at line 194 of file update_row.cc.

◆ GetNonZeroPositions()

absl::Span< const ColIndex > operations_research::glop::UpdateRow::GetNonZeroPositions ( ) const

Definition at line 196 of file update_row.cc.

◆ GetUnitRowLeftInverse()

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.

◆ Invalidate()

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.

◆ IsComputedFor()

bool operations_research::glop::UpdateRow::IsComputedFor ( RowIndex leaving_row) const
inline

Returns true if ComputeUpdateRow() was called since the last Invalidate().

Definition at line 76 of file update_row.h.

◆ operator=()

UpdateRow & operations_research::glop::UpdateRow::operator= ( const UpdateRow & )
delete

◆ SetParameters()

void operations_research::glop::UpdateRow::SetParameters ( const GlopParameters & parameters)

Sets the algorithm parameters.

Definition at line 200 of file update_row.cc.

◆ StatString()

std::string operations_research::glop::UpdateRow::StatString ( ) const
inline

Returns statistics about this class as a string.

Definition at line 99 of file update_row.h.


The documentation for this class was generated from the following files: