3.2.5 The Definition of Variables and Groups

In the MPS
standard, the constraint
matrix, the matrix of linear elements,
is input by columns;
firstly the names of the constraints
are specified in the `ROWS`
section and then variable names
and the corresponding matrix coefficients are set one at a time in the
`COLUMNS`
section. While there is some justification for this form
of matrix entry for linear programming
problems -- the principal solution algorithm for such problems, the
simplex method [3], is usually column oriented -- there
seems no good reason why the coefficients of linear elements
might not also be input by rows.
After all, it is more natural to think of
specifying the constraints
for a problem one at a time. Furthermore,
requiring that a complete row or column has been specified before the
next may be processed is unnecessarily restrictive.

We thus allow the data to be input in a either a group-wise (row-wise)
or variable-wise (column-wise) fashion. In a group/row-wise scheme,
one or two coefficients and their variable/column names are specified
for a given group/row; for a variable/column-wise scheme, one or two
coefficients and their group/row names are specified for a given
variable/column. We do, however, still require that in a group/row-wise
storage scheme, the names of all the variables/rows *which appear
in linear elements*
are completely specified before the coefficients
are input. Similarly, in a variable/column-wise storage scheme, the
names of all the groups/rows *which have a linear element*
must be
completely specified before the coefficients are input. This allows
for some checking of the input data.

If the groups/rows are specified first, there is no requirement that variables/columns are input one at a time (but of course they may be). When processing the data file, variable/column names should be inspected to see if they are new or where they have appeared before. Likewise, if the variables/columns are specified first, there is no requirement that groups/rows are ordered on input. The coordinates of new data values can then be stored as a linked triple (group/row, variable/column, value). Conversion from such a component-wise input scheme to a row or column based storage scheme may be performed very efficiently if desired (see [5, pp30-31], and subroutine MC39 in the Harwell Subroutine Library).

If a variable/column-wise input scheme is to be adopted, the data file
will contain a `GROUPS/ROWS/CONSTRAINTS`
indicator card
and section followed by a `VARIABLES/COLUMNS`
card and section. The
allowed data cards are discussed in Section 3.2.6 and
Section 3.2.7. If a group/row-wise input scheme is to be
adopted, the data file will contain a `VARIABLES/COLUMNS`
indicator card
and section followed by a `GROUPS/ROWS/CONSTRAINTS`
card and section. The data cards
for this scheme are discussed in
Section 3.2.8 and Section 3.2.9.