An MPS basis file, known as a BAS file, contains the information needed by ILOG 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.
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, 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.
- Field 1: Indicator specifying status of the named variables in Fields 2 and 3. Acceptable values appear in Table 5.5.
- 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 Complete 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. ILOG 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.
