Scippy

SoPlex

Sequential object-oriented simPlex

SPxScaler< R > Class Template Referenceabstract

LP scaler abstract base class.Instances of classes derived from SPxScaler may be loaded to SoPlex in order to scale LPs before solving them. SoPlex will load() itself to the SPxScaler and then call scale(). Generally any SPxLP can be loaded to a SPxScaler for scale()ing it. The scaling can be undone by calling unscale(). More...

#include <spxscaler.h>

Public Member Functions

virtual int computeScaleExp (const SVectorBase< R > &vec, const DataArray< int > &oldScaleExp) const
 compute a single scaling vector , e.g. of a newly added row More...
 
virtual void applyScaling (SPxLPBase< R > &lp)
 applies m_colscale and m_rowscale to the lp. More...
 
Construction / destruction
 SPxScaler (const char *name, bool colFirst=false, bool doBoth=true, SPxOut *spxout=NULL)
 constructor More...
 
 SPxScaler (const SPxScaler &)
 copy constructor More...
 
SPxScaleroperator= (const SPxScaler &)
 assignment operator More...
 
virtual ~SPxScaler ()
 destructor. More...
 
virtual SPxScalerclone () const =0
 clone function for polymorphism More...
 
Access / modification
virtual const char * getName () const
 get name of scaler More...
 
virtual void setOrder (bool colFirst)
 set scaling order More...
 
virtual void setBoth (bool both)
 set wether column and row scaling should be performed More...
 
virtual void setOutstream (SPxOut &newOutstream)
 set message handler More...
 
virtual void setRealParam (R param, const char *name="realparam")
 set R parameter More...
 
virtual void setIntParam (int param, const char *name="intparam")
 set int parameter More...
 
Scaling
virtual void scale (SPxLPBase< R > &lp, bool persistent=true)=0
 scale SPxLP. More...
 
virtual void unscale (SPxLPBase< R > &lp)
 unscale SPxLP More...
 
virtual int getColScaleExp (int i) const
 returns scaling factor for column i More...
 
virtual int getRowScaleExp (int i) const
 returns scaling factor for row i More...
 
virtual void getColUnscaled (const SPxLPBase< R > &lp, int i, DSVectorBase< R > &vec) const
 gets unscaled column i More...
 
virtual R getColMaxAbsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns maximum absolute value of unscaled column i More...
 
virtual R getColMinAbsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns minumum absolute value of unscaled column i More...
 
virtual R upperUnscaled (const SPxLPBase< R > &lp, int i) const
 returns unscaled upper bound i More...
 
virtual void getUpperUnscaled (const SPxLPBase< R > &lp, VectorBase< R > &vec) const
 returns unscaled upper bound vector of lp More...
 
virtual R lowerUnscaled (const SPxLPBase< R > &lp, int i) const
 returns unscaled lower bound i More...
 
virtual void getLowerUnscaled (const SPxLPBase< R > &lp, VectorBase< R > &vec) const
 gets unscaled lower bound vector More...
 
virtual R maxObjUnscaled (const SPxLPBase< R > &lp, int i) const
 returns unscaled objective function coefficient of i More...
 
virtual void getMaxObjUnscaled (const SPxLPBase< R > &lp, VectorBase< R > &vec) const
 gets unscaled objective function More...
 
virtual void getRowUnscaled (const SPxLPBase< R > &lp, int i, DSVectorBase< R > &vec) const
 returns unscaled row i More...
 
virtual R getRowMaxAbsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns maximum absolute value of unscaled row i More...
 
virtual R getRowMinAbsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns minimum absolute value of unscaled row i More...
 
virtual R rhsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns unscaled right hand side i More...
 
virtual void getRhsUnscaled (const SPxLPBase< R > &lp, VectorBase< R > &vec) const
 gets unscaled right hand side vector More...
 
virtual R lhsUnscaled (const SPxLPBase< R > &lp, int i) const
 returns unscaled left hand side i of lp More...
 
virtual void getLhsUnscaled (const SPxLPBase< R > &lp, VectorBase< R > &vec) const
 returns unscaled left hand side vector of lp More...
 
virtual R getCoefUnscaled (const SPxLPBase< R > &lp, int row, int col) const
 returns unscaled coefficient of lp More...
 
virtual void unscalePrimal (const SPxLPBase< R > &lp, VectorBase< R > &x) const
 unscale dense primal solution vector given in x. More...
 
virtual void unscaleSlacks (const SPxLPBase< R > &lp, VectorBase< R > &s) const
 unscale dense slack vector given in s. More...
 
virtual void unscaleDual (const SPxLPBase< R > &lp, VectorBase< R > &pi) const
 unscale dense dual solution vector given in pi. More...
 
virtual void unscaleRedCost (const SPxLPBase< R > &lp, VectorBase< R > &r) const
 unscale dense reduced cost vector given in r. More...
 
virtual void unscalePrimalray (const SPxLPBase< R > &lp, VectorBase< R > &ray) const
 unscale primal ray given in ray. More...
 
virtual void unscaleDualray (const SPxLPBase< R > &lp, VectorBase< R > &ray) const
 unscale dual ray given in ray. More...
 
virtual void scaleObj (const SPxLPBase< R > &lp, VectorBase< R > &origObj) const
 apply scaling to objective function vector origObj. More...
 
virtual R scaleObj (const SPxLPBase< R > &lp, int i, R origObj) const
 returns scaled objective function coefficient origObj. More...
 
virtual R scaleElement (const SPxLPBase< R > &lp, int row, int col, R val) const
 returns scaled LP element in row and col. More...
 
virtual R scaleLower (const SPxLPBase< R > &lp, int col, R lower) const
 returns scaled lower bound of column col. More...
 
virtual R scaleUpper (const SPxLPBase< R > &lp, int col, R upper) const
 returns scaled upper bound of column col. More...
 
virtual R scaleLhs (const SPxLPBase< R > &lp, int row, R lhs) const
 returns scaled left hand side of row row. More...
 
virtual R scaleRhs (const SPxLPBase< R > &lp, int row, R rhs) const
 returns scaled right hand side of row row. More...
 
virtual R minAbsColscale () const
 absolute smallest column scaling factor More...
 
virtual R maxAbsColscale () const
 absolute biggest column scaling factor More...
 
virtual R minAbsRowscale () const
 absolute smallest row scaling factor More...
 
virtual R maxAbsRowscale () const
 absolute biggest row scaling factor More...
 
virtual R maxColRatio (const SPxLPBase< R > &lp) const
 maximum ratio between absolute biggest and smallest element in any column. More...
 
virtual R maxRowRatio (const SPxLPBase< R > &lp) const
 maximum ratio between absolute biggest and smallest element in any row. More...
 
void computeExpVec (const std::vector< R > &vec, DataArray< int > &vecExp)
 round vector entries to power of 2 More...
 
Debugging
virtual bool isConsistent () const
 consistency check More...
 

Protected Member Functions

Protected helpers
virtual void setup (SPxLPBase< R > &lp)
 clear and setup scaling arrays in the LP More...
 

Protected Attributes

Data
const char * m_name
 Name of the scaler. More...
 
DataArray< int > * m_activeColscaleExp
 pointer to currently active column scaling factors More...
 
DataArray< int > * m_activeRowscaleExp
 pointer to currently active row scaling factors More...
 
bool m_colFirst
 do column scaling first More...
 
bool m_doBoth
 do columns and rows More...
 
SPxOutspxout
 message handler More...
 

Friends

template<class T >
std::ostream & operator<< (std::ostream &s, const SPxScaler< T > &sc)
 

Detailed Description

template<class R>
class soplex::SPxScaler< R >

LP scaler abstract base class.

Instances of classes derived from SPxScaler may be loaded to SoPlex in order to scale LPs before solving them. SoPlex will load() itself to the SPxScaler and then call scale(). Generally any SPxLP can be loaded to a SPxScaler for scale()ing it. The scaling can be undone by calling unscale().

Mathematically, the scaling of a constraint matrix A can be written as \( A' = R A C \), with \( R \) and \( C \), being diagonal matrices corresponding to the row and column scale factors, respectively. Besides the constraints matrix, also the upper and lower bounds of both columns and rows need to be scaled.

Note that by default scaling is performed both before and after presolving and the former scaling factors are retained during branch-and-bound (persistent scaling). However, while within SoPlex the scaled problem is used, data accessed through the soplex.cpp interface is provided w.r.t. the original problem (i.e., in unscaled form). For instance, consider a scaled constraints matrix A' that is extended by artificial slack variables to the matrix (A',I). A basis \( B' = [(A',I)P]_{[1:m][1:m] }\) (with P being a permutation matrix) for the scaled problem corresponds to the basis \( B = R^{-1} [(A',I)P]_{[1:m][1:m]} [P^{T} \tilde{C}^{-1} P]_{[1:m][1:m] } \). In this equation, \( \tilde{C} \) is of the form

\[ \begin{array}{cc} C & 0 \\ O & R^{-1} \end{array} \]

Note that in SoPlex only scaling factors \( 2^k, k \in \mathbb{Z} \) are used.

Definition at line 77 of file spxscaler.h.

Constructor & Destructor Documentation

◆ SPxScaler() [1/2]

SPxScaler ( const char *  name,
bool  colFirst = false,
bool  doBoth = true,
SPxOut spxout = NULL 
)
explicit

constructor

◆ SPxScaler() [2/2]

SPxScaler ( const SPxScaler< R > &  )

copy constructor

◆ ~SPxScaler()

virtual ~SPxScaler ( )
virtual

destructor.

Member Function Documentation

◆ applyScaling()

virtual void applyScaling ( SPxLPBase< R > &  lp)
virtual

applies m_colscale and m_rowscale to the lp.

◆ clone()

virtual SPxScaler* clone ( ) const
pure virtual

clone function for polymorphism

Implemented in SPxGeometSC< R >, SPxEquiliSC< R >, and SPxLeastSqSC< R >.

◆ computeExpVec()

void computeExpVec ( const std::vector< R > &  vec,
DataArray< int > &  vecExp 
)

round vector entries to power of 2

Referenced by SPxScaler< R >::setOutstream().

◆ computeScaleExp()

virtual int computeScaleExp ( const SVectorBase< R > &  vec,
const DataArray< int > &  oldScaleExp 
) const
virtual

compute a single scaling vector , e.g. of a newly added row

◆ getCoefUnscaled()

virtual R getCoefUnscaled ( const SPxLPBase< R > &  lp,
int  row,
int  col 
) const
virtual

returns unscaled coefficient of lp

Referenced by SPxScaler< R >::setOutstream().

◆ getColMaxAbsUnscaled()

virtual R getColMaxAbsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns maximum absolute value of unscaled column i

Referenced by SPxScaler< R >::setOutstream().

◆ getColMinAbsUnscaled()

virtual R getColMinAbsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns minumum absolute value of unscaled column i

Referenced by SPxScaler< R >::setOutstream().

◆ getColScaleExp()

virtual int getColScaleExp ( int  i) const
virtual

returns scaling factor for column i

Referenced by SPxScaler< R >::setOutstream().

◆ getColUnscaled()

virtual void getColUnscaled ( const SPxLPBase< R > &  lp,
int  i,
DSVectorBase< R > &  vec 
) const
virtual

gets unscaled column i

Referenced by SPxScaler< R >::setOutstream().

◆ getLhsUnscaled()

virtual void getLhsUnscaled ( const SPxLPBase< R > &  lp,
VectorBase< R > &  vec 
) const
virtual

returns unscaled left hand side vector of lp

Referenced by SPxScaler< R >::setOutstream().

◆ getLowerUnscaled()

virtual void getLowerUnscaled ( const SPxLPBase< R > &  lp,
VectorBase< R > &  vec 
) const
virtual

gets unscaled lower bound vector

Referenced by SPxScaler< R >::setOutstream().

◆ getMaxObjUnscaled()

virtual void getMaxObjUnscaled ( const SPxLPBase< R > &  lp,
VectorBase< R > &  vec 
) const
virtual

gets unscaled objective function

Referenced by SPxScaler< R >::setOutstream().

◆ getName()

virtual const char* getName ( ) const
virtual

get name of scaler

◆ getRhsUnscaled()

virtual void getRhsUnscaled ( const SPxLPBase< R > &  lp,
VectorBase< R > &  vec 
) const
virtual

gets unscaled right hand side vector

Referenced by SPxScaler< R >::setOutstream().

◆ getRowMaxAbsUnscaled()

virtual R getRowMaxAbsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns maximum absolute value of unscaled row i

Referenced by SPxScaler< R >::setOutstream().

◆ getRowMinAbsUnscaled()

virtual R getRowMinAbsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns minimum absolute value of unscaled row i

Referenced by SPxScaler< R >::setOutstream().

◆ getRowScaleExp()

virtual int getRowScaleExp ( int  i) const
virtual

returns scaling factor for row i

Referenced by SPxScaler< R >::setOutstream().

◆ getRowUnscaled()

virtual void getRowUnscaled ( const SPxLPBase< R > &  lp,
int  i,
DSVectorBase< R > &  vec 
) const
virtual

returns unscaled row i

Referenced by SPxScaler< R >::setOutstream().

◆ getUpperUnscaled()

virtual void getUpperUnscaled ( const SPxLPBase< R > &  lp,
VectorBase< R > &  vec 
) const
virtual

returns unscaled upper bound vector of lp

Referenced by SPxScaler< R >::setOutstream().

◆ isConsistent()

virtual bool isConsistent ( ) const
virtual

consistency check

Referenced by SPxScaler< R >::setOutstream().

◆ lhsUnscaled()

virtual R lhsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns unscaled left hand side i of lp

Referenced by SPxScaler< R >::setOutstream().

◆ lowerUnscaled()

virtual R lowerUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns unscaled lower bound i

Referenced by SPxScaler< R >::setOutstream().

◆ maxAbsColscale()

virtual R maxAbsColscale ( ) const
virtual

absolute biggest column scaling factor

Referenced by SPxScaler< R >::setOutstream().

◆ maxAbsRowscale()

virtual R maxAbsRowscale ( ) const
virtual

absolute biggest row scaling factor

Referenced by SPxScaler< R >::setOutstream().

◆ maxColRatio()

virtual R maxColRatio ( const SPxLPBase< R > &  lp) const
virtual

maximum ratio between absolute biggest and smallest element in any column.

Referenced by SPxScaler< R >::setOutstream().

◆ maxObjUnscaled()

virtual R maxObjUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns unscaled objective function coefficient of i

Referenced by SPxScaler< R >::setOutstream().

◆ maxRowRatio()

virtual R maxRowRatio ( const SPxLPBase< R > &  lp) const
virtual

maximum ratio between absolute biggest and smallest element in any row.

Referenced by SPxScaler< R >::setOutstream().

◆ minAbsColscale()

virtual R minAbsColscale ( ) const
virtual

absolute smallest column scaling factor

Referenced by SPxScaler< R >::setOutstream().

◆ minAbsRowscale()

virtual R minAbsRowscale ( ) const
virtual

absolute smallest row scaling factor

Referenced by SPxScaler< R >::setOutstream().

◆ operator=()

SPxScaler& operator= ( const SPxScaler< R > &  )

assignment operator

◆ rhsUnscaled()

virtual R rhsUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns unscaled right hand side i

Referenced by SPxScaler< R >::setOutstream().

◆ scale()

virtual void scale ( SPxLPBase< R > &  lp,
bool  persistent = true 
)
pure virtual

scale SPxLP.

Implemented in SPxGeometSC< R >, SPxEquiliSC< R >, and SPxLeastSqSC< R >.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleElement()

virtual R scaleElement ( const SPxLPBase< R > &  lp,
int  row,
int  col,
val 
) const
virtual

returns scaled LP element in row and col.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleLhs()

virtual R scaleLhs ( const SPxLPBase< R > &  lp,
int  row,
lhs 
) const
virtual

returns scaled left hand side of row row.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleLower()

virtual R scaleLower ( const SPxLPBase< R > &  lp,
int  col,
lower 
) const
virtual

returns scaled lower bound of column col.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleObj() [1/2]

virtual void scaleObj ( const SPxLPBase< R > &  lp,
VectorBase< R > &  origObj 
) const
virtual

apply scaling to objective function vector origObj.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleObj() [2/2]

virtual R scaleObj ( const SPxLPBase< R > &  lp,
int  i,
origObj 
) const
virtual

returns scaled objective function coefficient origObj.

◆ scaleRhs()

virtual R scaleRhs ( const SPxLPBase< R > &  lp,
int  row,
rhs 
) const
virtual

returns scaled right hand side of row row.

Referenced by SPxScaler< R >::setOutstream().

◆ scaleUpper()

virtual R scaleUpper ( const SPxLPBase< R > &  lp,
int  col,
upper 
) const
virtual

returns scaled upper bound of column col.

Referenced by SPxScaler< R >::setOutstream().

◆ setBoth()

virtual void setBoth ( bool  both)
virtual

set wether column and row scaling should be performed

◆ setIntParam()

virtual void setIntParam ( int  param,
const char *  name = "intparam" 
)
virtual

set int parameter

Reimplemented in SPxLeastSqSC< R >.

Referenced by SPxScaler< R >::setOutstream().

◆ setOrder()

virtual void setOrder ( bool  colFirst)
virtual

set scaling order

◆ setOutstream()

virtual void setOutstream ( SPxOut newOutstream)
virtual

set message handler

Definition at line 141 of file spxscaler.h.

References SPxScaler< R >::computeExpVec(), SPxScaler< R >::getCoefUnscaled(), SPxScaler< R >::getColMaxAbsUnscaled(), SPxScaler< R >::getColMinAbsUnscaled(), SPxScaler< R >::getColScaleExp(), SPxScaler< R >::getColUnscaled(), SPxScaler< R >::getLhsUnscaled(), SPxScaler< R >::getLowerUnscaled(), SPxScaler< R >::getMaxObjUnscaled(), SPxScaler< R >::getRhsUnscaled(), SPxScaler< R >::getRowMaxAbsUnscaled(), SPxScaler< R >::getRowMinAbsUnscaled(), SPxScaler< R >::getRowScaleExp(), SPxScaler< R >::getRowUnscaled(), SPxScaler< R >::getUpperUnscaled(), SPxScaler< R >::isConsistent(), SPxScaler< R >::lhsUnscaled(), SPxScaler< R >::lowerUnscaled(), SPxScaler< R >::maxAbsColscale(), SPxScaler< R >::maxAbsRowscale(), SPxScaler< R >::maxColRatio(), SPxScaler< R >::maxObjUnscaled(), SPxScaler< R >::maxRowRatio(), SPxScaler< R >::minAbsColscale(), SPxScaler< R >::minAbsRowscale(), SPxScaler< R >::rhsUnscaled(), SPxScaler< R >::scale(), SPxScaler< R >::scaleElement(), SPxScaler< R >::scaleLhs(), SPxScaler< R >::scaleLower(), SPxScaler< R >::scaleObj(), SPxScaler< R >::scaleRhs(), SPxScaler< R >::scaleUpper(), SPxScaler< R >::setIntParam(), SPxScaler< R >::setRealParam(), SPxScaler< R >::unscale(), SPxScaler< R >::unscaleDual(), SPxScaler< R >::unscaleDualray(), SPxScaler< R >::unscalePrimal(), SPxScaler< R >::unscalePrimalray(), SPxScaler< R >::unscaleRedCost(), SPxScaler< R >::unscaleSlacks(), and SPxScaler< R >::upperUnscaled().

◆ setRealParam()

virtual void setRealParam ( param,
const char *  name = "realparam" 
)
virtual

set R parameter

Reimplemented in SPxLeastSqSC< R >.

Referenced by SPxScaler< R >::setOutstream().

◆ setup()

virtual void setup ( SPxLPBase< R > &  lp)
protectedvirtual

clear and setup scaling arrays in the LP

◆ unscale()

virtual void unscale ( SPxLPBase< R > &  lp)
virtual

unscale SPxLP

Referenced by SPxScaler< R >::setOutstream().

◆ unscaleDual()

virtual void unscaleDual ( const SPxLPBase< R > &  lp,
VectorBase< R > &  pi 
) const
virtual

unscale dense dual solution vector given in pi.

Referenced by SPxScaler< R >::setOutstream().

◆ unscaleDualray()

virtual void unscaleDualray ( const SPxLPBase< R > &  lp,
VectorBase< R > &  ray 
) const
virtual

unscale dual ray given in ray.

Referenced by SPxScaler< R >::setOutstream().

◆ unscalePrimal()

virtual void unscalePrimal ( const SPxLPBase< R > &  lp,
VectorBase< R > &  x 
) const
virtual

unscale dense primal solution vector given in x.

Referenced by SPxScaler< R >::setOutstream().

◆ unscalePrimalray()

virtual void unscalePrimalray ( const SPxLPBase< R > &  lp,
VectorBase< R > &  ray 
) const
virtual

unscale primal ray given in ray.

Referenced by SPxScaler< R >::setOutstream().

◆ unscaleRedCost()

virtual void unscaleRedCost ( const SPxLPBase< R > &  lp,
VectorBase< R > &  r 
) const
virtual

unscale dense reduced cost vector given in r.

Referenced by SPxScaler< R >::setOutstream().

◆ unscaleSlacks()

virtual void unscaleSlacks ( const SPxLPBase< R > &  lp,
VectorBase< R > &  s 
) const
virtual

unscale dense slack vector given in s.

Referenced by SPxScaler< R >::setOutstream().

◆ upperUnscaled()

virtual R upperUnscaled ( const SPxLPBase< R > &  lp,
int  i 
) const
virtual

returns unscaled upper bound i

Referenced by SPxScaler< R >::setOutstream().

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<< ( std::ostream &  s,
const SPxScaler< T > &  sc 
)
friend

Member Data Documentation

◆ m_activeColscaleExp

DataArray< int >* m_activeColscaleExp
protected

pointer to currently active column scaling factors

Definition at line 85 of file spxscaler.h.

◆ m_activeRowscaleExp

DataArray< int >* m_activeRowscaleExp
protected

pointer to currently active row scaling factors

Definition at line 86 of file spxscaler.h.

◆ m_colFirst

bool m_colFirst
protected

do column scaling first

Definition at line 87 of file spxscaler.h.

◆ m_doBoth

bool m_doBoth
protected

do columns and rows

Definition at line 88 of file spxscaler.h.

◆ m_name

const char* m_name
protected

Name of the scaler.

Definition at line 84 of file spxscaler.h.

◆ spxout

SPxOut* spxout
protected

message handler

Definition at line 89 of file spxscaler.h.