glpk08.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

%* glpk08.tex *%

\chapter{MPS Format}
\label{champs}

\section{Fixed MPS Format}
\label{secmps}

The MPS format\footnote{The MPS format was developed in 1960's by IBM
as input format for their mathematical programming system MPS/360.
Today the MPS format is a most widely used format understood by most
mathematical programming packages. This appendix describes only the
features of the MPS format, which are implemented in the GLPK package.}
is intended for coding LP/MIP problem data. This format assumes the
formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp},
page \pageref{seclp}).

{\it MPS file} is a text file, which contains two types of
cards\footnote{In 1960's MPS file was a deck of 80-column punched cards,
so the author decided to keep the word ``card'', which may be understood
as ``line of text file''.}: indicator cards and data cards.

Indicator cards determine a kind of succeeding data. Each indicator card
has one word in uppercase letters beginning in column 1.

Data cards contain problem data. Each data card is divided into six
fixed fields:

\begin{center}
\begin{tabular}{lcccccc}
& Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\
\hline
Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\
Contents & Code & Name & Name & Number & Name & Number \\
\end{tabular}
\end{center}

On a particular data card some fields may be optional.

Names are used to identify rows, columns, and some vectors (see below).

Aligning the indicator code in the field 1 to the left margin is
optional.

All names specified in the fields 2, 3, and 5 should contain from 1 up
to 8 arbitrary characters (except control characters). If a name is
placed in the field 3 or 5, its first character should not be the dollar
sign `\verb|$|'. If a name contains spaces, the spaces are ignored.

All numerical values in the fields 4 and 6 should be coded in the form
$sxx$\verb|E|$syy$, where $s$ is the plus `\verb|+|' or the minus
`\verb|-|' sign, $xx$ is a real number with optional decimal point,
$yy$ is an integer decimal exponent. Any number should contain up to 12
characters. If the sign $s$ is omitted, the plus sign is assumed. The
exponent part is optional. If a number contains spaces, the spaces are
ignored.

If a card has the asterisk `\verb|*|' in the column 1, this card is
considered as a comment and ignored. Besides, if the first character in
the field 3 or 5 is the dollar sign `\verb|$|', all characters from the
dollar sign to the end of card are considered as a comment and ignored.

MPS file should contain cards in the following order:

$\bullet$ NAME indicator card;

$\bullet$ ROWS indicator card;

$\bullet$ data cards specifying rows (constraints);

$\bullet$ COLUMNS indicator card;

$\bullet$ data cards specifying columns (structural variables) and
constraint coefficients;

$\bullet$ RHS indicator card;

$\bullet$ data cards specifying right-hand sides of constraints;

$\bullet$ RANGES indicator card;

$\bullet$ data cards specifying ranges for double-bounded constraints;

$\bullet$ BOUNDS indicator card;

$\bullet$ data cards specifying types and bounds of structural
variables;

$\bullet$ ENDATA indicator card.

{\it Section} is a group of cards consisting of an indicator card and
data cards succeeding this indicator card. For example, the ROWS section
consists of the ROWS indicator card and data cards specifying rows.

The sections RHS, RANGES, and BOUNDS are optional and may be omitted.

\section{Free MPS Format}

{\it Free MPS format} is an improved version of the standard (fixed)
MPS format described above.\footnote{This format was developed in the
beginning of 1990's by IBM as an alternative to the standard fixed MPS
format for Optimization Subroutine Library (OSL).} Note that all
changes in free MPS format concern only the coding of data while the
structure of data is the same for both fixed and free versions of the
MPS format.

In free MPS format indicator and data records\footnote{{\it Record} in
free MPS format has the same meaning as {\it card} in fixed MPS format.}
may have arbitrary length not limited to 80 characters. Fields of data
records have no predefined positions, i.e. the fields may begin in any
position, except position 1, which must be blank, and must be separated
from each other by one or more blanks. However, the fields must appear
in the same order as in fixed MPS format.

Symbolic names in fields 2, 3, and 5 may be longer than 8
characters\footnote{GLPK allows symbolic names having up to 255
characters.}
and must not contain embedded blanks.

Numeric values in fields 4 and 6 are limited to 12 characters and must
not contain embedded blanks.

Only six fields on each data record are used. Any other fields are
ignored.

If the first character of any field (not necessarily fields 3 and 5)
is the dollar sign (\$), all characters from the dollar sign to the end
of record are considered as a comment and ignored.

\section{NAME indicator card}

The NAME indicator card should be the first card in the MPS file (except
optional comment cards, which may precede the NAME card). This card
should contain the word \verb|NAME| in the columns 1---4 and the problem
name in the field 3. The problem name is optional and may be omitted.

\section{ROWS section}
\label{secrows}

The ROWS section should start with the indicator card, which contains
the word \verb|ROWS| in the columns 1---4.

Each data card in the ROWS section specifies one row (constraint) of the
problem. All these data cards have the following format.

`\verb|N|' in the field 1 means that the row is free (unbounded):
$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
< +\infty;$$

`\verb|L|' in the field 1 means that the row is of ``less than or equal
to'' type:
$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
\leq b_i;$$

`\verb|G|' in the field 1 means that the row is of ``greater than or
equal to'' type:
$$b_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
< +\infty;$$

`\verb|E|' in the field 1 means that the row is of ``equal to'' type:
$$x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} \leq
b_i,$$
where $b_i$ is a right-hand side. Note that each constraint has a
corresponding implictly defined auxiliary variable ($x_i$ above), whose
value is a value of the corresponding linear form, therefore row bounds
can be considered as bounds of such auxiliary variable.

The filed 2 specifies a row name (which is considered as the name of
the corresponding auxiliary variable).

The fields 3, 4, 5, and 6 are not used and should be empty.

Numerical values of all non-zero right-hand sides $b_i$ should be
specified in the RHS section (see below). All double-bounded (ranged)
constraints should be specified in the RANGES section (see below).

\section{COLUMNS section}

The COLUMNS section should start with the indicator card, which contains
the word \verb|COLUMNS| in the columns 1---7.

Each data card in the COLUMNS section specifies one or two constraint
coefficients $a_{ij}$ and also introduces names of columns, i.e. names
of structural variables. All these data cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a column name. If this field is empty, the column
name from the immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a numerical value of the constraint coefficient
$a_{ij}$, which is placed in the corresponding row and column.

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---constraint coefficient'' for the same column.

Elements of the constraint matrix (i.e. constraint coefficients) should
be enumerated in the column wise manner: all elements for the current
column should be specified before elements for the next column. However,
the order of rows in the COLUMNS section may differ from the order of
rows in the ROWS section.

Constraint coefficients not specified in the COLUMNS section are
considered as zeros. Therefore zero coefficients may be omitted,
although it is allowed to explicitly specify them.

\section{RHS section}

The RHS section should start with the indicator card, which contains the
word \verb|RHS| in the columns 1---3.

Each data card in the RHS section specifies one or two right-hand sides
$b_i$ (see Section \ref{secrows}, page \pageref{secrows}). All these
data cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a name of the right-hand side (RHS)
vector\footnote{This feature allows the user to specify several RHS
vectors in the same MPS file. However, before solving the problem a
particular RHS vector should be chosen.}. If this field is empty, the
RHS vector name from the immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a right-hand side $b_i$ for the row, whose name is
specified in the field 3. Depending on the row type $b_i$ is a lower
bound (for the row of \verb|G| type), an upper bound (for the row of
\verb|L| type), or a fixed value (for the row of \verb|E|
type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as
a constant term of the corresponding linear form. Should note, however,
this convention is non-standard.}

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---right-hand side'' for the same RHS vector.

All right-hand sides for the current RHS vector should be specified
before right-hand sides for the next RHS vector. However, the order of
rows in the RHS section may differ from the order of rows in the ROWS
section.

Right-hand sides not specified in the RHS section are considered as
zeros. Therefore zero right-hand sides may be omitted, although it is
allowed to explicitly specify them.

\section{RANGES section}

The RANGES section should start with the indicator card, which contains
the word \verb|RANGES| in the columns 1---6.

Each data card in the RANGES section specifies one or two ranges for
double-side constraints, i.e. for constraints that are of the types
\verb|L| and \verb|G| at the same time:
$$l_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
\leq u_i,$$
where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data
cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a name of the range vector\footnote{This feature
allows the user to specify several range vectors in the same MPS file.
However, before solving the problem a particular range vector should be
chosen.}. If this field is empty, the range vector name from the
immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a range value $r_i$ (see the table below) for the
row, whose name is specified in the field 3.

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---range value'' for the same range vector.

All range values for the current range vector should be specified before
range values for the next range vector. However, the order of rows in
the RANGES section may differ from the order of rows in the ROWS
section.

For each double-side constraint specified in the RANGES section its
lower and upper bounds are determined as follows:

\begin{center}
\begin{tabular}{cccc}
Row type & Sign of $r_i$ & Lower bound & Upper bound \\
\hline
{\tt G} & $+$ or $-$ & $b_i$ & $b_i + |r_i|$ \\
{\tt L} & $+$ or $-$ & $b_i - |r_i|$ & $b_i$ \\
{\tt E} & $+$ & $b_i$ & $b_i + |r_i|$ \\
{\tt E} & $-$ & $b_i - |r_i|$ & $b_i$ \\
\end{tabular}
\end{center}

\noindent
where $b_i$ is a right-hand side specified in the RHS section (if $b_i$
is not specified, it is considered as zero), $r_i$ is a range value
specified in the RANGES section.

\section{BOUNDS section}
\label{secbounds}

The BOUNDS section should start with the indicator card, which contains
the word \verb|BOUNDS| in the columns 1---6.

Each data card in the BOUNDS section specifies one (lower or upper)
bound for one structural variable (column). All these data cards have
the following format.

The indicator in the field 1 specifies the bound type:

\begin{tabular}{@{}ll}
\verb|LO| & lower bound; \\
\verb|UP| & upper bound; \\
\verb|FX| & fixed variable (lower and upper bounds are equal); \\
\verb|FR| & free variable (no bounds); \\
\verb|MI| & no lower bound (lower bound is ``minus infinity''); \\
\verb|PL| & no upper bound (upper bound is ``plus infinity''); \\
\end{tabular}

The field 2 specifies a name of the bound vector\footnote{This feature
allows the user to specify several bound vectors in the same MPS file.
However, before solving the problem a particular bound vector should be
chosen.}. If this field is empty, the bound vector name from the
immediately preceeding data card is assumed.

The field 3 specifies a column name defined in the COLUMNS section.

The field 4 specifies a bound value. If the bound type in the field 1
differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field
4 is ignored and may be omitted.

The fields 5 and 6 are not used and should be empty.

All bound values for the current bound vector should be specified before
bound values for the next bound vector. However, the order of columns in
the BOUNDS section may differ from the order of columns in the COLUMNS
section. Specification of a lower bound should precede specification of
an upper bound for the same column (if both the lower and upper bounds
are explicitly specified).

By default, all columns (structural variables) are non-negative, i.e.
have zero lower bound and no upper bound. Lower ($l_j$) and upper
($u_j$) bounds of some column (structural variable $x_j$) are set in the
following way, where $s_j$ is a corresponding bound value explicitly
specified in the BOUNDS section: