Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::glop::DualEdgeNorms Class Reference

#include <dual_edge_norms.h>

Public Member Functions

 DualEdgeNorms (const BasisFactorization &basis_factorization)
 Takes references to the linear program data we need.
 
 DualEdgeNorms (const DualEdgeNorms &)=delete
 This type is neither copyable nor movable.
 
DualEdgeNorms & operator= (const DualEdgeNorms &)=delete
 
void Clear ()
 
void ResizeOnNewRows (RowIndex new_size)
 
bool NeedsBasisRefactorization () const
 
DenseColumn::ConstView GetEdgeSquaredNorms ()
 
void UpdateDataOnBasisPermutation (const ColumnPermutation &col_perm)
 Updates the norms if the columns of the basis where permuted.
 
bool TestPrecision (RowIndex leaving_row, const ScatteredRow &unit_row_left_inverse)
 
void UpdateBeforeBasisPivot (ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, const ScatteredRow &unit_row_left_inverse)
 
void SetParameters (const GlopParameters &parameters)
 Sets the algorithm parameters.
 
std::string StatString () const
 Stats related functions.
 

Detailed Description

This class maintains the dual edge squared norms to be used in the dual steepest edge pricing. The dual edge u_i associated with a basic variable of row index i is such that u_i.B = e_i where e_i is the unit row vector with a 1.0 at position i and B the current basis. We call such vector u_i an unit row left inverse, and it can be computed by

basis_factorization.LeftSolveForUnitRow(i, &u_i);

Instead of computing each |u_i| at every iteration, it is more efficient to update them incrementally for each basis pivot applied to B. See the code or the papers below for details:

J.J. Forrest, D. Goldfarb, "Steepest-edge simplex algorithms for linear programming", Mathematical Programming 57 (1992) 341-374, North-Holland. http://www.springerlink.com/content/q645w3t2q229m248/

Achim Koberstein, "The dual simplex method, techniques for a fast and stable implementation", PhD, Paderborn, Univ., 2005. http://digital.ub.uni-paderborn.de/hs/download/pdf/3885?originalFilename=true

Definition at line 49 of file dual_edge_norms.h.

Constructor & Destructor Documentation

◆ DualEdgeNorms() [1/2]

operations_research::glop::DualEdgeNorms::DualEdgeNorms ( const BasisFactorization & basis_factorization)
explicit

Takes references to the linear program data we need.

Definition at line 23 of file dual_edge_norms.cc.

◆ DualEdgeNorms() [2/2]

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

This type is neither copyable nor movable.

Member Function Documentation

◆ Clear()

void operations_research::glop::DualEdgeNorms::Clear ( )

Clears, i.e. reset the object to its initial value. This will trigger a full norm recomputation on the next GetEdgeSquaredNorms().

Definition at line 31 of file dual_edge_norms.cc.

◆ GetEdgeSquaredNorms()

DenseColumn::ConstView operations_research::glop::DualEdgeNorms::GetEdgeSquaredNorms ( )

Returns the dual edge squared norms. This is only valid if the caller properly called UpdateBeforeBasisPivot() before each basis pivot, or just called Clear().

Definition at line 37 of file dual_edge_norms.cc.

◆ NeedsBasisRefactorization()

bool operations_research::glop::DualEdgeNorms::NeedsBasisRefactorization ( ) const

If this is true, then the caller must re-factorize the basis before the next call to GetEdgeSquaredNorms(). This is because the latter will recompute the norms from scratch and therefore needs a hightened precision and speed. This also indicates if GetEdgeSquaredNorms() will trigger a recomputation.

Definition at line 27 of file dual_edge_norms.cc.

◆ operator=()

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

◆ ResizeOnNewRows()

void operations_research::glop::DualEdgeNorms::ResizeOnNewRows ( RowIndex new_size)

When we just add new constraints to the matrix and use an incremental solve, we do not need to recompute the norm of the old rows, and the norm of the new ones can be just set to 1 as long as we use identity columns for these.

Definition at line 33 of file dual_edge_norms.cc.

◆ SetParameters()

void operations_research::glop::DualEdgeNorms::SetParameters ( const GlopParameters & parameters)
inline

Sets the algorithm parameters.

Definition at line 101 of file dual_edge_norms.h.

◆ StatString()

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

Stats related functions.

Definition at line 106 of file dual_edge_norms.h.

◆ TestPrecision()

bool operations_research::glop::DualEdgeNorms::TestPrecision ( RowIndex leaving_row,
const ScatteredRow & unit_row_left_inverse )

Computes exactly the norm of the given leaving row, and returns true if it is good enough compared to our current norm. In both case update the current norm with its precise version and decide if we should recompute norms on the next GetEdgeSquaredNorms().

This should only be true if we do not use steepest edge.

|unit_row_left_inverse|^2 is the same as edge_squared_norms_[leaving_row], but with a better precision. If the difference between the two is too large, we trigger a full recomputation.

We just do not want to pivot on a position with an under-estimated norm.

Definition at line 49 of file dual_edge_norms.cc.

◆ UpdateBeforeBasisPivot()

void operations_research::glop::DualEdgeNorms::UpdateBeforeBasisPivot ( ColIndex entering_col,
RowIndex leaving_row,
const ScatteredColumn & direction,
const ScatteredRow & unit_row_left_inverse )

Updates the norms just before a basis pivot is applied:

  • The column at leaving_row will leave the basis and the column at entering_col will enter it.
  • direction is the right inverse of the entering column.
  • unit_row_left_inverse is the left inverse of the unit row with index given by the leaving_row. This is also the leaving dual edge.

No need to update if we will recompute it from scratch later.

Update the norm.

Note
the update formula used is important to maximize the precision. See Koberstein's PhD section 8.2.2.1.

Avoid 0.0 norms (The 1e-4 is the value used by Koberstein).

Todo
(user): use a more precise lower bound depending on the column norm? We can do that with Cauchy-Swartz inequality: (edge . leaving_column)^2 = 1.0 < |edge|^2 * |leaving_column|^2

Definition at line 82 of file dual_edge_norms.cc.

◆ UpdateDataOnBasisPermutation()

void operations_research::glop::DualEdgeNorms::UpdateDataOnBasisPermutation ( const ColumnPermutation & col_perm)

Updates the norms if the columns of the basis where permuted.

Definition at line 42 of file dual_edge_norms.cc.

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