The MPS format can also be used to specify some predefined basis for an LP problem, i.e. to specify which rows and columns are basic and which are non-basic.
As in the MPS format, a number of fields are defined on fixed column positions:
Field: 1 2 3 4 5 6 Columns: 2-3 5-12 15-22 25-36 40-47 50-61
The order of a basis file in the MPS format is:
Any line with an asterisk (*) in Column 1 is treated as a comment.
The NAME card can have anything you want, starting in column 15.
lp_solve sets the number of iterations, the number of rows and number of columns of the model to the NAME record.
The eight character names used to specify variables and constraints entities are fixed format. Names are not automatically justified, so blanks are treated just like other characters. For example "ROW1 " is not the same as " ROW1 ". (Note that some optimisers do not permit blanks in names.) No case conversion is performed, so "row1 " is different from "ROW1 ".
Each data card specifies either a pair "basic column--non-basic row" or a non-basic column. All the data cards have the following format.
'XL' in the field 1 means that a column, whose name is given in
the field 2, is basic, and a row, whose name is given in the field 3,
is non-basic and placed on its lower bound.
'XU' in the field 1 means that a column, whose name is given in
the field 2, is basic, and a row, whose name is given in the field 3,
is non-basic and placed on its upper bound.
'LL' in the field 1 means that a column, whose name is given in
the field 3, is non-basic and placed on its lower bound.
'UL' in the field 1 means that a column, whose name is given in
the field 3, is non-basic and placed on its upper bound.
The field 2 contains a column name.
If the indicator given in the field 1 is 'XL' or 'XU',
the field 3 contains a row name. Otherwise, if the indicator is
'LL' or 'UL', the field 3 is not used and should be empty.
The field 4, 5, and 6 are not used and should be empty.
| 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 |
Field 1: Indicator specifying status of the named variables in Fields 2 and 3.
Field 2: Variable 1 identifier
Field 3: Variable 2 identifier (ignored if Field 1 is UL or LL)
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.
A basis file in the MPS format acts like a patch: it doesn't specify a basis completely, instead that it is just shows in what a given basis differs from the "standard" basis, where all rows (auxiliary variables) are assumed to be basic and all columns (structural variables) are assumed to be non-basic.
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. 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.
Example:
*000000001111111111222222222233333333334444444444555555555566 *234567890123456789012345678901234567890123456789012345678901 NAME TESTPROB Iterations 0 Rows 3 Cols 3 XL ZTHREE LIM2 UL XONE ENDATA