Scippy

SoPlex

Sequential object-oriented simPlex

SPxBasis::Desc Class Reference

Basis descriptor. More...

#include <spxbasis.h>

Public Types

enum  Status {
  P_ON_LOWER = -4, P_ON_UPPER = -2, P_FREE = -1, P_FIXED = P_ON_UPPER + P_ON_LOWER,
  D_FREE = 1, D_ON_UPPER = 2, D_ON_LOWER = 4, D_ON_BOTH = D_ON_LOWER + D_ON_UPPER,
  D_UNDEFINED = 8
}
 Status of a variable. More...
 

Public Member Functions

int nCols () const
 returns number of columns. More...
 
int nRows () const
 returns number of rows. More...
 
int dim () const
 returns dimension. More...
 
int coDim () const
 returns codimension. More...
 
StatusrowStatus (int i)
 
Status rowStatus (int i) const
 returns status of row i. More...
 
const StatusrowStatus (void) const
 returns the array of row Statuses. More...
 
StatuscolStatus (int i)
 
Status colStatus (int i) const
 returns status of column i. More...
 
const StatuscolStatus (void) const
 returns the array of column Statuses. More...
 
Statusstatus (int i)
 
Status status (int i) const
 returns status of variable i. More...
 
const Statusstatus (void) const
 returns the array of variable Statuses. More...
 
StatuscoStatus (int i)
 
Status coStatus (int i) const
 returns status of covariable i. More...
 
const StatuscoStatus (void) const
 returns the array of covariable Statuses. More...
 
void reSize (int rowDim, int colDim)
 resets dimensions. More...
 
void dump () const
 Prints out status. More...
 
bool isConsistent () const
 consistency check. More...
 
 Desc ()
 default constructor More...
 
 Desc (const SPxSolver &base)
 
 Desc (const Desc &old)
 copy constructor More...
 
Descoperator= (const Desc &rhs)
 assignment operator More...
 

Private Attributes

DataArray< Statusrowstat
 status of rows. More...
 
DataArray< Statuscolstat
 status of columns. More...
 
DataArray< Status > * stat
 basis' status. More...
 
DataArray< Status > * costat
 cobasis' status. More...
 

Friends

class SPxBasis
 
std::ostream & operator<< (std::ostream &os, const Status &stat)
 

Detailed Description

Basis descriptor.

Definition at line 104 of file spxbasis.h.

Member Enumeration Documentation

◆ Status

enum Status

Status of a variable.

A basis is described by assigning a Status to all of the LP variables and covariables. This assignment is maintained by the basis Descriptor.

Variables and covariables (slackvariables) may have a primal or dual Status. The first type specifies that a variable is set on a primal bound, while the latter type indicates a dual variable to be set on a bound. If a row variable has a primal status, say P_ON_UPPER, this means that the upper bound of the inequality is set to be tight. Hence, in this case the upper bound must not be infinity.

Equivalently, if the status of a variable is dual, say D_ON_UPPER, it means that the dual variable corresponding to the upper bound inequality of this variable is set to 0.

For a column basis, primal Statuses correspond to nonbasic variables, while dual ones are basic. This is reversed for a row basis. We will now reveal in more detail the significance of variable Statuses.

Primal Variables

Consider a range inequality \(l_r \le a^T x \le u_r\) or bounds on a variable \(l_c \le x_c \le u_c\). The following table reveals what is implied if the corresponding variable or covariable is assigned to a primal Status:

\[ \begin{array}{lcl} l_c \le x_c \le u_c & \mbox{Status}(x_i) & l_r \le a^T x \le u_r \\ \hline x_c = u_c < \infty & \mbox{P\_ON\_UPPER} & a^T x = u_r < \infty \\ x_c = l_c > -\infty & \mbox{P\_ON\_LOWER} & a^T x = l_r > -\infty \\ -\infty < l_c = x_c = u_c < \infty & \mbox{P\_FIXED} & -\infty < l_r = a^T x = u_r < \infty \\ -\infty = l_i < x_i=0 < u_i = \infty & \mbox{P\_FREE} & -\infty = l_r < a^T x = 0 < u_r = \infty \\ \end{array} \]

Note that to determine whether a variable with Status stat is set to its upper bound, one can compute the test (-stat | -P_ON_UPPER). This will yield true even if the variable is fixed, i.e., sitting on both bounds at the same time.

Dual Variables

In principle for implementing the Simplex algorithm it would suffice to use only one dual Status. However, for performance reasons it is advisable to introduce various dual status types, reflecting the structure of the bounds. Given an upper bound \(u\) and a lower bound \(l\) of a constraint or variable, the following table indicates the setting of the dual Status of this variable.

\[ \begin{array}{cl} l \le ... \le u & \mbox{Status} \\ \hline -\infty < l \ne u < \infty & \mbox{D\_ON\_BOTH} \\ -\infty < l \ne u = \infty & \mbox{D\_ON\_UPPER} \\ -\infty = l \ne u < \infty & \mbox{D\_ON\_LOWER} \\ -\infty < l = u < \infty & \mbox{D\_FREE} \\ -\infty = l \ne u = \infty & \mbox{D\_UNDEFINED} \\ \end{array} \]

Note that unbounded primal variables are reflected by an D_UNDEFINED dual variable, since no reduced costs exist for them. To facilitate the assignment of dual Statuses, class SPxBasis provides methods dualStatus(), dualColStatus() and dualRowStatus)().

Enumerator
P_ON_LOWER 

primal variable is set to its lower bound

P_ON_UPPER 

primal variable is set to its upper bound

P_FREE 

primal variable is left free, but unset

P_FIXED 

primal variable is fixed to both bounds

D_FREE 

dual variable is left free, but unset

D_ON_UPPER 

dual variable is set to its upper bound

D_ON_LOWER 

dual variable is set to its lower bound

D_ON_BOTH 

dual variable has two bounds

D_UNDEFINED 

primal or dual variable is undefined

Definition at line 185 of file spxbasis.h.

Constructor & Destructor Documentation

◆ Desc() [1/3]

Desc ( )

default constructor

Definition at line 316 of file spxbasis.h.

References SPxBasis::Desc::operator=().

◆ Desc() [2/3]

◆ Desc() [3/3]

Member Function Documentation

◆ coDim()

int coDim ( ) const

returns codimension.

Definition at line 234 of file spxbasis.h.

References DataArray< T >::size().

◆ colStatus() [1/3]

◆ colStatus() [2/3]

Status colStatus ( int  i) const

returns status of column i.

Definition at line 259 of file spxbasis.h.

◆ colStatus() [3/3]

const Status* colStatus ( void  ) const

returns the array of column Statuses.

Definition at line 264 of file spxbasis.h.

References DataArray< T >::get_const_ptr().

Referenced by SPxBasis::Desc::dump().

◆ coStatus() [1/3]

◆ coStatus() [2/3]

Status coStatus ( int  i) const

returns status of covariable i.

Definition at line 289 of file spxbasis.h.

◆ coStatus() [3/3]

const Status* coStatus ( void  ) const

returns the array of covariable Statuses.

Definition at line 294 of file spxbasis.h.

References SPxBasis::Desc::dump(), DataArray< T >::get_const_ptr(), SPxBasis::Desc::isConsistent(), and SPxBasis::Desc::reSize().

◆ dim()

int dim ( ) const

returns dimension.

Definition at line 229 of file spxbasis.h.

References DataArray< T >::size().

◆ dump()

◆ isConsistent()

◆ nCols()

int nCols ( ) const

◆ nRows()

int nRows ( ) const

◆ operator=()

◆ reSize()

void reSize ( int  rowDim,
int  colDim 
)

◆ rowStatus() [1/3]

◆ rowStatus() [2/3]

Status rowStatus ( int  i) const

returns status of row i.

Definition at line 244 of file spxbasis.h.

◆ rowStatus() [3/3]

const Status* rowStatus ( void  ) const

returns the array of row Statuses.

Definition at line 249 of file spxbasis.h.

References DataArray< T >::get_const_ptr().

Referenced by SPxBasis::Desc::dump().

◆ status() [1/3]

◆ status() [2/3]

Status status ( int  i) const

returns status of variable i.

Definition at line 274 of file spxbasis.h.

◆ status() [3/3]

const Status* status ( void  ) const

returns the array of variable Statuses.

Definition at line 279 of file spxbasis.h.

References DataArray< T >::get_const_ptr().

Referenced by SPxBasis::setOutstream().

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<< ( std::ostream &  os,
const Status stat 
)
friend

Definition at line 144 of file spxdesc.cpp.

Referenced by SPxBasis::setOutstream().

◆ SPxBasis

friend class SPxBasis
friend

Definition at line 199 of file spxbasis.h.

Referenced by SPxBasis::setOutstream().

Member Data Documentation

◆ colstat

◆ costat

DataArray< Status >* costat
private

cobasis' status.

Definition at line 210 of file spxbasis.h.

Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::operator=(), and SPxBasis::setRep().

◆ rowstat

◆ stat

DataArray< Status >* stat
private

basis' status.

Definition at line 209 of file spxbasis.h.

Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::operator=(), and SPxBasis::setRep().