SoPlex
Sequential object-oriented simPlex
Sequential object-oriented simPlex
Basis descriptor. More...
#include <spxbasis.h>
Public Types | |
Status | |
Status of a variable. | |
| 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 } |
Public Member Functions | |
Access / modification | |
returns number of columns. | |
| int | nCols () const |
| 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... | |
Debugging | |
Prints out status. | |
| void | dump () const |
| bool | isConsistent () const |
| consistency check. More... | |
Construction / destruction | |
default constructor | |
| Desc () | |
| Desc (const SPxSolverBase< R > &base) | |
| Desc (const Desc &old) | |
| copy constructor More... | |
| Desc & | operator= (const Desc &rhs) |
| assignment operator More... | |
Public Attributes | |
| friend | SPxBasisBase< R > |
Private Attributes | |
Data | |
| 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 | |
| template<class T > | |
| std::ostream & | operator<< (std::ostream &os, const Status &stat) |
Basis descriptor.
Definition at line 106 of file spxbasis.h.
| enum Status |
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 SPxBasisBase provides methods dualStatus(), dualColStatus() and dualRowStatus)().
Definition at line 187 of file spxbasis.h.
| Desc | ( | ) |
Definition at line 319 of file spxbasis.h.
References SPxBasisBase< R >::Desc::operator=().
|
explicit |
| int coDim | ( | ) | const |
| Status& colStatus | ( | int | i | ) |
Definition at line 257 of file spxbasis.h.
| Status colStatus | ( | int | i | ) | const |
returns status of column i.
Definition at line 262 of file spxbasis.h.
| const Status* colStatus | ( | void | ) | const |
returns the array of column Statuses.
Definition at line 267 of file spxbasis.h.
References DataArray< T >::get_const_ptr().
| Status& coStatus | ( | int | i | ) |
Definition at line 287 of file spxbasis.h.
| Status coStatus | ( | int | i | ) | const |
returns status of covariable i.
Definition at line 292 of file spxbasis.h.
| const Status* coStatus | ( | void | ) | const |
returns the array of covariable Statuses.
Definition at line 297 of file spxbasis.h.
References SPxBasisBase< R >::Desc::dump(), DataArray< T >::get_const_ptr(), SPxBasisBase< R >::Desc::isConsistent(), and SPxBasisBase< R >::Desc::reSize().
| int dim | ( | ) | const |
| void dump | ( | ) | const |
Referenced by SPxBasisBase< R >::Desc::coStatus(), and SPxBasisBase< R >::unLoad().
| bool isConsistent | ( | ) | const |
consistency check.
Referenced by SPxBasisBase< R >::Desc::coStatus(), and SPxBasisBase< R >::unLoad().
| int nCols | ( | ) | const |
Definition at line 222 of file spxbasis.h.
References DataArray< T >::size().
| int nRows | ( | ) | const |
returns number of rows.
Definition at line 227 of file spxbasis.h.
References DataArray< T >::size().
assignment operator
Referenced by SPxBasisBase< R >::Desc::Desc(), and SPxBasisBase< R >::setOutstream().
| void reSize | ( | int | rowDim, |
| int | colDim | ||
| ) |
resets dimensions.
Referenced by SPxBasisBase< R >::Desc::coStatus().
| Status& rowStatus | ( | int | i | ) |
Definition at line 242 of file spxbasis.h.
| Status rowStatus | ( | int | i | ) | const |
returns status of row i.
Definition at line 247 of file spxbasis.h.
| const Status* rowStatus | ( | void | ) | const |
returns the array of row Statuses.
Definition at line 252 of file spxbasis.h.
References DataArray< T >::get_const_ptr().
| Status& status | ( | int | i | ) |
Definition at line 272 of file spxbasis.h.
| Status status | ( | int | i | ) | const |
returns status of variable i.
Definition at line 277 of file spxbasis.h.
| const Status* status | ( | void | ) | const |
returns the array of variable Statuses.
Definition at line 282 of file spxbasis.h.
References DataArray< T >::get_const_ptr().
Referenced by SPxBasisBase< R >::setOutstream().
|
friend |
Referenced by SPxBasisBase< R >::setOutstream().
status of columns.
Definition at line 211 of file spxbasis.h.
cobasis' status.
Definition at line 213 of file spxbasis.h.
status of rows.
Definition at line 210 of file spxbasis.h.
| friend SPxBasisBase< R > |
Definition at line 201 of file spxbasis.h.
basis' status.
Definition at line 212 of file spxbasis.h.