BAS file format: advanced basis

The BAS file format supports an advanced basis.

An MPS basis file, known as a BAS file, contains the information needed by CPLEX to define an advanced basis. Like an MPS file, the BAS file begins with a NAME indicator record and ends with an ENDATA record.

Tip:

A BAS file is a text-based format that relies on each variable and each constraint having a name. If you anticipate reading and writing BAS files, you must assign a unique name to each variable (column) and to each constraint (row) when you create the model. See also CPXERR_BAD_NAME.

A basis defines a list of basic structural variables and row variables. A structural variable is one of the variables (columns) defined in the MPS problem file. A row variable is actually the slack, surplus, or artificial variable associated with a row.

For linear programs, the total number of basic variables—both structural and row—is equal to the number of rows in the constraint matrix. Additionally, the number of basic structural variables is equal to the number of nonbasic row variables. By convention, an MPS basis file is built on the assumption that all row variables are basic and that all structural variables are nonbasic with values at their lower bound. The data records in a BAS file list structural and row variables that violate this assumption. This convention minimizes the size of the BAS file.

For quadratic programs, since the basis corresponds to an augmented linear system involving the optimality conditions for the convex QP, the total number of basic variables can exceed the number of rows and so not all basic variables can be paired with a nonbasic row variable.

Table 1. Status indicators for variables in a BAS file
Value	Status
`XU`	Variable 1 is basic; variable 2 is nonbasic at its upper bound
`XL`	Variable 1 is basic; variable 2 is nonbasic at its lower bound
`UL`	Variable 1 is nonbasic and is at its upper bound
`LL`	Variable 1 is nonbasic and is at its lower bound
`BS`	Variable 1 is basic.

Field 1: Indicator specifying status of the named variables in Fields 2 and 3. Acceptable values appear in Table 1.

Field 2: Variable 1 identifier

Field 3: Variable 2 identifier (ignored if Field 1 is UL , LL or BS )

Variable 1 specifies a structural variable identifier which has entered the basis. By convention, this structural variable must displace one of the row variables. Variable 2 is a row variable that has left the basis. No relationship between structural variables entering the basis and row variables leaving the basis is implied within the BAS file.

In the Example of MPS file format, variables x2 and x3 are basic and the two constraints (row variables) are nonbasic. Also, x1 was forced to its upper limit of 40. The optimal basis for that example appears in the following sample. CPLEX adds the number of iterations to the NAME record. The iteration count is useful if the basis file was automatically generated during a previously aborted run. The XL indicator in the first two data records indicates that x3 and x2 are basic and that the row variables for c1 and c2 are nonbasic at their lower bound. The third record shows that structural variable x1 is nonbasic and at its upper bound.


NAME          example2.bas  Iterations 3  Rows 2  Cols 3
 XL x3        c1
 XL x2        c2
 UL x1
ENDATA