glpk08.tex

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

\begin{tabular}{@{}ll}
\verb|LO| & sets $l_j$ to $s_j$; \\
\verb|UP| & sets $u_j$ to $s_j$; \\
\verb|FX| & sets both $l_j$ and $u_j$ to $s_j$; \\
\verb|FR| & sets $l_j$ to $-\infty$ and $u_j$ to $+\infty$; \\
\verb|MI| & sets $l_j$ to $-\infty$; \\
\verb|PL| & sets $u_j$ to $+\infty$. \\
\end{tabular}

\section{ENDATA indicator card}

The ENDATA indicator card should be the last card of MPS file (except
optional comment cards, which may follow the ENDATA card). This card
should contain the word \verb|ENDATA| in the columns 1---6.

\section{Specifying objective function}

It is impossible to explicitly specify the objective function and
optimization direction in the MPS file. However, the following implicit
rule is used by default: the first row of \verb|N| type is considered
as a row of the objective function (i.e. the objective function is the
corresponding auxiliary variable), which should be {\it minimized}.

GLPK also allows specifying a constant term of the objective function
as a right-hand side of the corresponding row in the RHS section.

\section{Example of MPS file}
\label{secmpsex}

In order to illustrate what the MPS format is, consider the following
example of LP problem:

\medskip
\noindent minimize
$$
value = .03\ bin_1 + .08\ bin_2 + .17\ bin_3 + .12\ bin_4 + .15\ bin_5
+ .21\ al + .38\ si
$$

\noindent subject to linear constraints
$$
\begin{array}{@{}l@{\:}l@{}}
yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 +
         \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al +
         \ \ \ \ \;si \\
FE    &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5
         + .01\ al + .03\ si \\
CU    &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5
         + .01\ al \\
MN    &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5
         \\
MG    &= .02\ bin_1 + .03\ bin_2
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\
AL    &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5
         + .97\ al \\
SI    &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5
         + .01\ al + .97\ si \\
\end{array}
$$
and bounds of (auxiliary and structural) variables
$$
\begin{array}{r@{\ }l@{\ }l@{\ }l@{\ }rcr@{\ }l@{\ }l@{\ }l@{\ }r}
&&yield&=&2000&&0&\leq&bin_1&\leq&200\\
-\infty&<&FE&\leq&60&&0&\leq&bin_2&\leq&2500\\
-\infty&<&CU&\leq&100&&400&\leq&bin_3&\leq&800\\
-\infty&<&MN&\leq&40&&100&\leq&bin_4&\leq&700\\
-\infty&<&MG&\leq&30&&0&\leq&bin_5&\leq&1500\\
1500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\
250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\
\end{array}
$$

A complete MPS file which specifies data for this example is shown
below (the first two comment lines show card positions).

\begin{verbatim}
*000000001111111111222222222233333333334444444444555555555566
*234567890123456789012345678901234567890123456789012345678901
NAME          PLAN
ROWS
 N  VALUE
 E  YIELD
 L  FE
 L  CU
 L  MN
 L  MG
 G  AL
 L  SI
COLUMNS
    BIN1      VALUE           .03000   YIELD          1.00000
              FE              .15000   CU              .03000
              MN              .02000   MG              .02000
              AL              .70000   SI              .02000
    BIN2      VALUE           .08000   YIELD          1.00000
              FE              .04000   CU              .05000
              MN              .04000   MG              .03000
              AL              .75000   SI              .06000
    BIN3      VALUE           .17000   YIELD          1.00000
              FE              .02000   CU              .08000
              MN              .01000   AL              .80000
              SI              .08000
    BIN4      VALUE           .12000   YIELD          1.00000
              FE              .04000   CU              .02000
              MN              .02000   AL              .75000
              SI              .12000
    BIN5      VALUE           .15000   YIELD          1.00000
              FE              .02000   CU              .06000
              MN              .02000   MG              .01000
              AL              .80000   SI              .02000
    ALUM      VALUE           .21000   YIELD          1.00000
              FE              .01000   CU              .01000
              AL              .97000   SI              .01000
    SILICON   VALUE           .38000   YIELD          1.00000
              FE              .03000   SI              .97000
RHS
    RHS1      YIELD       2000.00000   FE            60.00000
              CU           100.00000   MN            40.00000
              SI           300.00000
              MG            30.00000   AL          1500.00000
RANGES
    RNG1      SI            50.00000
BOUNDS
 UP BND1      BIN1         200.00000
 UP           BIN2        2500.00000
 LO           BIN3         400.00000
 UP           BIN3         800.00000
 LO           BIN4         100.00000
 UP           BIN4         700.00000
 UP           BIN5        1500.00000
ENDATA
\end{verbatim}

\section{MIP features}

The MPS format provides two ways for introducing integer variables into
the problem.

The first way is most general and based on using special marker cards
INTORG and INTEND. These marker cards are placed in the COLUMNS section.
The INTORG card indicates the start of a group of integer variables
(columns), and the card INTEND indicates the end of the group. The MPS
file may contain arbitrary number of the marker cards.

The marker cards have the same format as the data cards (see Section
\ref{secmps}, page \pageref{secmps}).

The fields 1, 2, and 6 are not used and should be empty.

The field 2 should contain a marker name. This name may be arbitrary.

The field 3 should contain the word \verb|'MARKER'| (including
apostrophes).

The field 5 should contain either the word \verb|'INTORG'| (including
apostrophes) for the marker card, which begins a group of integer
columns, or the word \verb|'INTEND'| (including apostrophes) for the
marker card, which ends the group.

The second way is less general but more convenient in some cases. It
allows the user declaring integer columns using three additional types
of bounds, which are specified in the field 1 of data cards in the
BOUNDS section (see Section \ref{secbounds}, page \pageref{secbounds}):

\begin{tabular}{@{}lp{112.3mm}@{}}
\verb|LI| & lower integer. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
field 3, is of integer kind. In this case an lower bound of the
column should be specified in field 4 (like in the case of \verb|LO|
bound type). \\
\verb|UI| & upper integer. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
field 3, is of integer kind. In this case an upper bound of the
column should be specified in field 4 (like in the case of \verb|UP|
bound type). \\
\end{tabular}

\pagebreak

\begin{tabular}{@{}lp{112.3mm}@{}}
\verb|BV| & binary variable. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
the field 3, is of integer kind, its lower bound is zero, and its upper
bound is one (thus, such variable being of integer kind can have only
two values zero and one). In this case a numeric value specified in the
field 4 is ignored and may be omitted.\\
\end{tabular}

Consider the following example of MIP problem:

\medskip

\noindent
\hspace{1in} minimize
$$Z = 3 x_1 + 7 x_2 - x_3 + x4$$
\hspace{1in} subject to linear constraints
$$
\begin{array}{c}
\nonumber r_1 = 2   x_1 - \ \ x_2 + \ \ x_3 - \ \;x_4 \\
\nonumber r_2 = \ \;x_1 - \ \;x_2 - 6   x_3 + 4   x_4 \\
\nonumber r_3 = 5   x_1 +   3 x_2 \ \ \ \ \ \ \ \ \ + \ \ x_4 \\
\end{array}
$$
\hspace{1in} and bound of variables
$$
\begin{array}{cccl}
\nonumber 1 \leq r_1 < +\infty && 0 \leq x_1 \leq 4 &{\rm(continuous)}\\
\nonumber 8 \leq r_2 < +\infty && 2 \leq x_2 \leq 5 &{\rm(integer)}   \\
\nonumber 5 \leq r_3 < +\infty && 0 \leq x_3 \leq 1 &{\rm(integer)}   \\
\nonumber                      && 3 \leq x_4 \leq 8 &{\rm(continuous)}\\
\end{array}
$$

The corresponding MPS file may look like the following:

\begin{verbatim}
NAME          SAMP1
ROWS
 N  Z
 G  R1
 G  R2
 G  R3
COLUMNS
    X1        R1                2.0    R2                 1.0
    X1        R3                5.0    Z                  3.0
    MARK0001  'MARKER'                 'INTORG'
    X2        R1               -1.0    R2                -1.0
    X2        R3                3.0    Z                  7.0
    X3        R1                1.0    R2                -6.0
    X3        Z                -1.0
    MARK0002  'MARKER'                 'INTEND'
    X4        R1               -1.0    R2                 4.0
    X4        R3                1.0    Z                  1.0
RHS
    RHS1      R1                1.0
    RHS1      R2                8.0
    RHS1      R3                5.0
BOUNDS
 UP BND1      X1                4.0
 LO BND1      X2                2.0
 UP BND1      X2                5.0
 UP BND1      X3                1.0
 LO BND1      X4                3.0
 UP BND1      X4                8.0
ENDATA
\end{verbatim}

The same example may be coded without INTORG/INTEND markers using the
bound type UI for the variable $x_2$ and the bound type BV for the
variable $x_3$:

\begin{verbatim}
NAME          SAMP2
ROWS
 N  Z
 G  R1
 G  R2
 G  R3
COLUMNS
    X1        R1                2.0    R2                 1.0
    X1        R3                5.0    Z                  3.0
    X2        R1               -1.0    R2                -1.0
    X2        R3                3.0    Z                  7.0
    X3        R1                1.0    R2                -6.0
    X3        Z                -1.0
    X4        R1               -1.0    R2                 4.0
    X4        R3                1.0    Z                  1.0
RHS
    RHS1      R1                1.0
    RHS1      R2                8.0
    RHS1      R3                5.0
BOUNDS
 UP BND1      X1                4.0
 LO BND1      X2                2.0
 UI BND1      X2                5.0
 BV BND1      X3
 LO BND1      X4                3.0
 UP BND1      X4                8.0
ENDATA
\end{verbatim}

\section{Specifying predefined basis}
\label{secbas}

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.

The order of a basis file in the MPS format is:

$\bullet$ NAME indicator card;

$\bullet$ data cards (can appear in arbitrary order);

$\bullet$ ENDATA indicator card.

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.

`\verb|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.

`\verb|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.

`\verb|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.

`\verb|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 `\verb|XL|' or `\verb|XU|',
the field 3 contains a row name. Otherwise, if the indicator is
`\verb|LL|' or `\verb|UL|', the field 3 is not used and should be empty.

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

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.

As an example here is a basis file that specifies an optimal basis
for the example LP problem given in Section \ref{secmpsex},
Page \pageref{secmpsex}:

\pagebreak

\begin{verbatim}
*000000001111111111222222222233333333334444444444555555555566
*234567890123456789012345678901234567890123456789012345678901
NAME          PLAN
 XL BIN2      YIELD
 XL BIN3      FE
 XL BIN4      MN
 XL ALUM      AL
 XL SILICON   SI
 LL BIN1
 LL BIN5
ENDATA
\end{verbatim}

%* eof *%