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... | |
Status & | rowStatus (int i) |
Status | rowStatus (int i) const |
returns status of row i . More... | |
const Status * | rowStatus (void) const |
returns the array of row Statuses. More... | |
Status & | colStatus (int i) |
Status | colStatus (int i) const |
returns status of column i . More... | |
const Status * | colStatus (void) const |
returns the array of column Statuses. More... | |
Status & | status (int i) |
Status | status (int i) const |
returns status of variable i . More... | |
const Status * | status (void) const |
returns the array of variable Statuses. More... | |
Status & | coStatus (int i) |
Status | coStatus (int i) const |
returns status of covariable i . More... | |
const Status * | coStatus (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... | |
Desc & | operator= (const Desc &rhs) |
assignment operator More... | |
Private Attributes | |
DataArray< Status > | rowstat |
status of rows. More... | |
DataArray< Status > | colstat |
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) |
Basis descriptor.
Definition at line 104 of file spxbasis.h.
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. <b>Dual Variables</b> 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 \form#55 and a lower bound \form#56 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 #Status%es, class SPxBasis provides methods #dualStatus(), #dualColStatus() and #dualRowStatus)().
Definition at line 185 of file spxbasis.h.
Desc | ( | ) |
default constructor
Definition at line 316 of file spxbasis.h.
References SPxBasis::Desc::operator=().
Definition at line 25 of file spxdesc.cpp.
References SPxBasis::Desc::colstat, SPxSolver::COLUMN, SPxBasis::Desc::costat, SPxBasis::Desc::isConsistent(), SPxLPBase< R >::nCols(), SPxLPBase< R >::nRows(), SPxSolver::rep(), SPxBasis::Desc::reSize(), SPxSolver::ROW, SPxBasis::Desc::rowstat, and SPxBasis::Desc::stat.
copy constructor
Definition at line 45 of file spxdesc.cpp.
References SPxBasis::Desc::colstat, SPxBasis::Desc::costat, SPxBasis::Desc::isConsistent(), SPxBasis::Desc::rowstat, and SPxBasis::Desc::stat.
int coDim | ( | ) | const |
Status& colStatus | ( | int | i | ) |
Definition at line 254 of file spxbasis.h.
Referenced by SPxBasis::addedCols(), SPxSolver::changeLowerStatus(), SPxSolver::changeUpperStatus(), SoPlex::checkBasisDualFeasibility(), SPxSolver::computeFrhsXtra(), SPxBasis::dump(), SPxBoundFlippingRT::flipAndUpdate(), SPxWeightST::generate(), SPxSolver::getBasis(), SPxSolver::getEnterVals(), SPxSolver::getEnterVals2(), SPxSolver::getLeaveVals(), SPxSolver::getLeaveVals2(), SPxSolver::getPrimal(), SPxBasis::isConsistent(), SPxSolver::leave(), SPxBasis::loadDesc(), SPxSolver::nonbasicValue(), SPxSolver::performSolutionPolishing(), SPxSolver::rejectLeave(), SPxBasis::removedCol(), SPxBasis::removedCols(), SPxBasis::restoreInitialBasis(), SPxWeightPR::selectEnter(), SPxFastRT::selectLeave(), SPxSolver::setBasis(), SPxSolver::setDualColBounds(), soplex::setDualStatus(), SPxWeightST::setPrimalStatus(), SPxSolver::ungetEnterVal(), SPxSolver::unShift(), and SPxBasis::writeBasis().
Status colStatus | ( | int | i | ) | const |
returns status of column i
.
Definition at line 259 of file spxbasis.h.
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().
Status& coStatus | ( | int | i | ) |
Definition at line 284 of file spxbasis.h.
Referenced by SPxSolver::computeCoTest(), SPxSolver::computeFrhs2(), SPxBoundFlippingRT::flipAndUpdate(), SPxSolver::rejectEnter(), and SPxSolver::updateCoTest().
Status coStatus | ( | int | i | ) | const |
returns status of covariable i
.
Definition at line 289 of file spxbasis.h.
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().
int dim | ( | ) | const |
void dump | ( | ) | const |
Prints out status.
Definition at line 113 of file spxdesc.cpp.
References SPxBasis::Desc::colStatus(), SPxBasis::Desc::nCols(), SPxBasis::Desc::nRows(), and SPxBasis::Desc::rowStatus().
Referenced by SoPlex::_performOptIRStable(), SPxBasis::Desc::coStatus(), SPxBasis::readBasis(), SPxBasis::unLoad(), and SPxBasis::writeBasis().
bool isConsistent | ( | ) | const |
consistency check.
Definition at line 130 of file spxdesc.cpp.
References SPxBasis::Desc::colstat, DataArray< T >::isConsistent(), and SPxBasis::Desc::rowstat.
Referenced by SPxBasis::Desc::coStatus(), SPxBasis::Desc::Desc(), SPxBasis::isConsistent(), SPxBasis::Desc::operator=(), and SPxBasis::unLoad().
int nCols | ( | ) | const |
returns number of columns.
Definition at line 219 of file spxbasis.h.
References DataArray< T >::size().
Referenced by SPxBasis::Desc::dump(), SPxBasis::dump(), SPxBasis::isConsistent(), SPxBasis::isDescValid(), SPxBasis::loadDesc(), and SPxBasis::removedCols().
int nRows | ( | ) | const |
returns number of rows.
Definition at line 224 of file spxbasis.h.
References DataArray< T >::size().
Referenced by SPxBasis::Desc::dump(), SPxBasis::dump(), SPxBasis::isConsistent(), SPxBasis::isDescValid(), SPxBasis::loadDesc(), and SPxBasis::removedRows().
SPxBasis::Desc & operator= | ( | const Desc & | rhs | ) |
assignment operator
Definition at line 67 of file spxdesc.cpp.
References SPxBasis::Desc::colstat, SPxBasis::Desc::costat, SPxBasis::Desc::isConsistent(), SPxBasis::Desc::rowstat, and SPxBasis::Desc::stat.
Referenced by SPxBasis::Desc::Desc(), and SPxBasis::setOutstream().
void reSize | ( | int | rowDim, |
int | colDim | ||
) |
resets dimensions.
Definition at line 94 of file spxdesc.cpp.
References SPxBasis::Desc::colstat, SPxBasis::Desc::D_UNDEFINED, DataArray< T >::reSize(), SPxBasis::Desc::rowstat, and DataArray< T >::size().
Referenced by SPxBasis::Desc::coStatus(), SPxBasis::Desc::Desc(), and SPxBasis::reDim().
Status& rowStatus | ( | int | i | ) |
Definition at line 239 of file spxbasis.h.
Referenced by SoPlex::_identifyComplementaryDualFixedPrimalVars(), SoPlex::_identifyComplementaryPrimalFixedPrimalVars(), SoPlex::_updateDecompComplementaryDualProblem(), SoPlex::_updateDecompComplementaryPrimalProblem(), SPxBasis::addedRows(), SPxSolver::changeLhsStatus(), SPxSolver::changeRhsStatus(), SoPlex::checkBasisDualFeasibility(), SPxSolver::computeFrhs(), SPxBasis::dump(), SPxBoundFlippingRT::flipAndUpdate(), SPxSolver::getBasis(), SPxSolver::getEnterVals(), SPxSolver::getEnterVals2(), SoPlex::getExpectedDualVariableSign(), SPxSolver::getLeaveVals(), SPxSolver::getLeaveVals2(), SoPlex::getOriginalProblemBasisColStatus(), SoPlex::getOriginalProblemBasisRowStatus(), SoPlex::getOrigVarFixedDirection(), SPxSolver::getSlacks(), SPxBasis::isConsistent(), SPxSolver::leave(), SPxBasis::loadDesc(), SPxSolver::nonbasicValue(), SPxSolver::performSolutionPolishing(), SPxSolver::rejectLeave(), SPxBasis::removedRow(), SPxBasis::removedRows(), SPxBasis::restoreInitialBasis(), SPxWeightPR::selectEnter(), SPxSolver::setBasis(), SPxSolver::setDualColBounds(), soplex::setDualStatus(), SPxWeightST::setPrimalStatus(), SPxSolver::ungetEnterVal(), SPxSolver::unShift(), and SPxBasis::writeBasis().
Status rowStatus | ( | int | i | ) | const |
returns status of row i
.
Definition at line 244 of file spxbasis.h.
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& status | ( | int | i | ) |
Definition at line 269 of file spxbasis.h.
Referenced by SPxSolver::computeFrhs1(), SPxSolver::computeTest(), SPxBoundFlippingRT::flipAndUpdate(), SPxSolver::rejectEnter(), and SPxSolver::updateTest().
Status status | ( | int | i | ) | const |
returns status of variable i
.
Definition at line 274 of file spxbasis.h.
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().
|
friend |
Definition at line 139 of file spxdesc.cpp.
Referenced by SPxBasis::setOutstream().
|
friend |
Definition at line 199 of file spxbasis.h.
Referenced by SPxBasis::setOutstream().
status of columns.
Definition at line 208 of file spxbasis.h.
Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::isConsistent(), SPxBasis::isDescValid(), SPxBasis::Desc::operator=(), SPxBasis::readBasis(), SPxBasis::Desc::reSize(), and SPxBasis::setRep().
cobasis' status.
Definition at line 210 of file spxbasis.h.
Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::operator=(), and SPxBasis::setRep().
status of rows.
Definition at line 207 of file spxbasis.h.
Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::isConsistent(), SPxBasis::isDescValid(), SPxBasis::Desc::operator=(), SPxBasis::readBasis(), SPxBasis::Desc::reSize(), and SPxBasis::setRep().
basis' status.
Definition at line 209 of file spxbasis.h.
Referenced by SPxBasis::Desc::Desc(), SPxBasis::Desc::operator=(), and SPxBasis::setRep().