1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/glpk08.tex	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,696 @@
     1.4 +%* glpk08.tex *%
     1.5 +
     1.6 +\chapter{MPS Format}
     1.7 +\label{champs}
     1.8 +
     1.9 +\section{Fixed MPS Format}
    1.10 +\label{secmps}
    1.11 +
    1.12 +The MPS format\footnote{The MPS format was developed in 1960's by IBM
    1.13 +as input format for their mathematical programming system MPS/360.
    1.14 +Today the MPS format is a most widely used format understood by most
    1.15 +mathematical programming packages. This appendix describes only the
    1.16 +features of the MPS format, which are implemented in the GLPK package.}
    1.17 +is intended for coding LP/MIP problem data. This format assumes the
    1.18 +formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp},
    1.19 +page \pageref{seclp}).
    1.20 +
    1.21 +{\it MPS file} is a text file, which contains two types of
    1.22 +cards\footnote{In 1960's MPS file was a deck of 80-column punched cards,
    1.23 +so the author decided to keep the word ``card'', which may be understood
    1.24 +as ``line of text file''.}: indicator cards and data cards.
    1.25 +
    1.26 +Indicator cards determine a kind of succeeding data. Each indicator card
    1.27 +has one word in uppercase letters beginning in column 1.
    1.28 +
    1.29 +Data cards contain problem data. Each data card is divided into six
    1.30 +fixed fields:
    1.31 +
    1.32 +\begin{center}
    1.33 +\begin{tabular}{lcccccc}
    1.34 +& Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\
    1.35 +\hline
    1.36 +Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\
    1.37 +Contents & Code & Name & Name & Number & Name & Number \\
    1.38 +\end{tabular}
    1.39 +\end{center}
    1.40 +
    1.41 +On a particular data card some fields may be optional.
    1.42 +
    1.43 +Names are used to identify rows, columns, and some vectors (see below).
    1.44 +
    1.45 +Aligning the indicator code in the field 1 to the left margin is
    1.46 +optional.
    1.47 +
    1.48 +All names specified in the fields 2, 3, and 5 should contain from 1 up
    1.49 +to 8 arbitrary characters (except control characters). If a name is
    1.50 +placed in the field 3 or 5, its first character should not be the dollar
    1.51 +sign `\verb|$|'. If a name contains spaces, the spaces are ignored.
    1.52 +
    1.53 +All numerical values in the fields 4 and 6 should be coded in the form
    1.54 +$sxx$\verb|E|$syy$, where $s$ is the plus `\verb|+|' or the minus
    1.55 +`\verb|-|' sign, $xx$ is a real number with optional decimal point,
    1.56 +$yy$ is an integer decimal exponent. Any number should contain up to 12
    1.57 +characters. If the sign $s$ is omitted, the plus sign is assumed. The
    1.58 +exponent part is optional. If a number contains spaces, the spaces are
    1.59 +ignored.
    1.60 +
    1.61 +If a card has the asterisk `\verb|*|' in the column 1, this card is
    1.62 +considered as a comment and ignored. Besides, if the first character in
    1.63 +the field 3 or 5 is the dollar sign `\verb|$|', all characters from the
    1.64 +dollar sign to the end of card are considered as a comment and ignored.
    1.65 +
    1.66 +MPS file should contain cards in the following order:
    1.67 +
    1.68 +$\bullet$ NAME indicator card;
    1.69 +
    1.70 +$\bullet$ ROWS indicator card;
    1.71 +
    1.72 +$\bullet$ data cards specifying rows (constraints);
    1.73 +
    1.74 +$\bullet$ COLUMNS indicator card;
    1.75 +
    1.76 +$\bullet$ data cards specifying columns (structural variables) and
    1.77 +constraint coefficients;
    1.78 +
    1.79 +$\bullet$ RHS indicator card;
    1.80 +
    1.81 +$\bullet$ data cards specifying right-hand sides of constraints;
    1.82 +
    1.83 +$\bullet$ RANGES indicator card;
    1.84 +
    1.85 +$\bullet$ data cards specifying ranges for double-bounded constraints;
    1.86 +
    1.87 +$\bullet$ BOUNDS indicator card;
    1.88 +
    1.89 +$\bullet$ data cards specifying types and bounds of structural
    1.90 +variables;
    1.91 +
    1.92 +$\bullet$ ENDATA indicator card.
    1.93 +
    1.94 +{\it Section} is a group of cards consisting of an indicator card and
    1.95 +data cards succeeding this indicator card. For example, the ROWS section
    1.96 +consists of the ROWS indicator card and data cards specifying rows.
    1.97 +
    1.98 +The sections RHS, RANGES, and BOUNDS are optional and may be omitted.
    1.99 +
   1.100 +\section{Free MPS Format}
   1.101 +
   1.102 +{\it Free MPS format} is an improved version of the standard (fixed)
   1.103 +MPS format described above.\footnote{This format was developed in the
   1.104 +beginning of 1990's by IBM as an alternative to the standard fixed MPS
   1.105 +format for Optimization Subroutine Library (OSL).} Note that all
   1.106 +changes in free MPS format concern only the coding of data while the
   1.107 +structure of data is the same for both fixed and free versions of the
   1.108 +MPS format.
   1.109 +
   1.110 +In free MPS format indicator and data records\footnote{{\it Record} in
   1.111 +free MPS format has the same meaning as {\it card} in fixed MPS format.}
   1.112 +may have arbitrary length not limited to 80 characters. Fields of data
   1.113 +records have no predefined positions, i.e. the fields may begin in any
   1.114 +position, except position 1, which must be blank, and must be separated
   1.115 +from each other by one or more blanks. However, the fields must appear
   1.116 +in the same order as in fixed MPS format.
   1.117 +
   1.118 +Symbolic names in fields 2, 3, and 5 may be longer than 8
   1.119 +characters\footnote{GLPK allows symbolic names having up to 255
   1.120 +characters.}
   1.121 +and must not contain embedded blanks.
   1.122 +
   1.123 +Numeric values in fields 4 and 6 are limited to 12 characters and must
   1.124 +not contain embedded blanks.
   1.125 +
   1.126 +Only six fields on each data record are used. Any other fields are
   1.127 +ignored.
   1.128 +
   1.129 +If the first character of any field (not necessarily fields 3 and 5)
   1.130 +is the dollar sign (\$), all characters from the dollar sign to the end
   1.131 +of record are considered as a comment and ignored.
   1.132 +
   1.133 +\section{NAME indicator card}
   1.134 +
   1.135 +The NAME indicator card should be the first card in the MPS file (except
   1.136 +optional comment cards, which may precede the NAME card). This card
   1.137 +should contain the word \verb|NAME| in the columns 1---4 and the problem
   1.138 +name in the field 3. The problem name is optional and may be omitted.
   1.139 +
   1.140 +\section{ROWS section}
   1.141 +\label{secrows}
   1.142 +
   1.143 +The ROWS section should start with the indicator card, which contains
   1.144 +the word \verb|ROWS| in the columns 1---4.
   1.145 +
   1.146 +Each data card in the ROWS section specifies one row (constraint) of the
   1.147 +problem. All these data cards have the following format.
   1.148 +
   1.149 +`\verb|N|' in the field 1 means that the row is free (unbounded):
   1.150 +$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
   1.151 +< +\infty;$$
   1.152 +
   1.153 +`\verb|L|' in the field 1 means that the row is of ``less than or equal
   1.154 +to'' type:
   1.155 +$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
   1.156 +\leq b_i;$$
   1.157 +
   1.158 +`\verb|G|' in the field 1 means that the row is of ``greater than or
   1.159 +equal to'' type:
   1.160 +$$b_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
   1.161 +< +\infty;$$
   1.162 +
   1.163 +`\verb|E|' in the field 1 means that the row is of ``equal to'' type:
   1.164 +$$x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} \leq
   1.165 +b_i,$$
   1.166 +where $b_i$ is a right-hand side. Note that each constraint has a
   1.167 +corresponding implictly defined auxiliary variable ($x_i$ above), whose
   1.168 +value is a value of the corresponding linear form, therefore row bounds
   1.169 +can be considered as bounds of such auxiliary variable.
   1.170 +
   1.171 +The filed 2 specifies a row name (which is considered as the name of
   1.172 +the corresponding auxiliary variable).
   1.173 +
   1.174 +The fields 3, 4, 5, and 6 are not used and should be empty.
   1.175 +
   1.176 +Numerical values of all non-zero right-hand sides $b_i$ should be
   1.177 +specified in the RHS section (see below). All double-bounded (ranged)
   1.178 +constraints should be specified in the RANGES section (see below).
   1.179 +
   1.180 +\section{COLUMNS section}
   1.181 +
   1.182 +The COLUMNS section should start with the indicator card, which contains
   1.183 +the word \verb|COLUMNS| in the columns 1---7.
   1.184 +
   1.185 +Each data card in the COLUMNS section specifies one or two constraint
   1.186 +coefficients $a_{ij}$ and also introduces names of columns, i.e. names
   1.187 +of structural variables. All these data cards have the following format.
   1.188 +
   1.189 +The field 1 is not used and should be empty.
   1.190 +
   1.191 +The field 2 specifies a column name. If this field is empty, the column
   1.192 +name from the immediately preceeding data card is assumed.
   1.193 +
   1.194 +The field 3 specifies a row name defined in the ROWS section.
   1.195 +
   1.196 +The field 4 specifies a numerical value of the constraint coefficient
   1.197 +$a_{ij}$, which is placed in the corresponding row and column.
   1.198 +
   1.199 +The fields 5 and 6 are optional. If they are used, they should contain
   1.200 +a second pair ``row name---constraint coefficient'' for the same column.
   1.201 +
   1.202 +Elements of the constraint matrix (i.e. constraint coefficients) should
   1.203 +be enumerated in the column wise manner: all elements for the current
   1.204 +column should be specified before elements for the next column. However,
   1.205 +the order of rows in the COLUMNS section may differ from the order of
   1.206 +rows in the ROWS section.
   1.207 +
   1.208 +Constraint coefficients not specified in the COLUMNS section are
   1.209 +considered as zeros. Therefore zero coefficients may be omitted,
   1.210 +although it is allowed to explicitly specify them.
   1.211 +
   1.212 +\section{RHS section}
   1.213 +
   1.214 +The RHS section should start with the indicator card, which contains the
   1.215 +word \verb|RHS| in the columns 1---3.
   1.216 +
   1.217 +Each data card in the RHS section specifies one or two right-hand sides
   1.218 +$b_i$ (see Section \ref{secrows}, page \pageref{secrows}). All these
   1.219 +data cards have the following format.
   1.220 +
   1.221 +The field 1 is not used and should be empty.
   1.222 +
   1.223 +The field 2 specifies a name of the right-hand side (RHS)
   1.224 +vector\footnote{This feature allows the user to specify several RHS
   1.225 +vectors in the same MPS file. However, before solving the problem a
   1.226 +particular RHS vector should be chosen.}. If this field is empty, the
   1.227 +RHS vector name from the immediately preceeding data card is assumed.
   1.228 +
   1.229 +The field 3 specifies a row name defined in the ROWS section.
   1.230 +
   1.231 +The field 4 specifies a right-hand side $b_i$ for the row, whose name is
   1.232 +specified in the field 3. Depending on the row type $b_i$ is a lower
   1.233 +bound (for the row of \verb|G| type), an upper bound (for the row of
   1.234 +\verb|L| type), or a fixed value (for the row of \verb|E|
   1.235 +type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as
   1.236 +a constant term of the corresponding linear form. Should note, however,
   1.237 +this convention is non-standard.}
   1.238 +
   1.239 +The fields 5 and 6 are optional. If they are used, they should contain
   1.240 +a second pair ``row name---right-hand side'' for the same RHS vector.
   1.241 +
   1.242 +All right-hand sides for the current RHS vector should be specified
   1.243 +before right-hand sides for the next RHS vector. However, the order of
   1.244 +rows in the RHS section may differ from the order of rows in the ROWS
   1.245 +section.
   1.246 +
   1.247 +Right-hand sides not specified in the RHS section are considered as
   1.248 +zeros. Therefore zero right-hand sides may be omitted, although it is
   1.249 +allowed to explicitly specify them.
   1.250 +
   1.251 +\section{RANGES section}
   1.252 +
   1.253 +The RANGES section should start with the indicator card, which contains
   1.254 +the word \verb|RANGES| in the columns 1---6.
   1.255 +
   1.256 +Each data card in the RANGES section specifies one or two ranges for
   1.257 +double-side constraints, i.e. for constraints that are of the types
   1.258 +\verb|L| and \verb|G| at the same time:
   1.259 +$$l_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
   1.260 +\leq u_i,$$
   1.261 +where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data
   1.262 +cards have the following format.
   1.263 +
   1.264 +The field 1 is not used and should be empty.
   1.265 +
   1.266 +The field 2 specifies a name of the range vector\footnote{This feature
   1.267 +allows the user to specify several range vectors in the same MPS file.
   1.268 +However, before solving the problem a particular range vector should be
   1.269 +chosen.}. If this field is empty, the range vector name from the
   1.270 +immediately preceeding data card is assumed.
   1.271 +
   1.272 +The field 3 specifies a row name defined in the ROWS section.
   1.273 +
   1.274 +The field 4 specifies a range value $r_i$ (see the table below) for the
   1.275 +row, whose name is specified in the field 3.
   1.276 +
   1.277 +The fields 5 and 6 are optional. If they are used, they should contain
   1.278 +a second pair ``row name---range value'' for the same range vector.
   1.279 +
   1.280 +All range values for the current range vector should be specified before
   1.281 +range values for the next range vector. However, the order of rows in
   1.282 +the RANGES section may differ from the order of rows in the ROWS
   1.283 +section.
   1.284 +
   1.285 +For each double-side constraint specified in the RANGES section its
   1.286 +lower and upper bounds are determined as follows:
   1.287 +
   1.288 +\begin{center}
   1.289 +\begin{tabular}{cccc}
   1.290 +Row type & Sign of $r_i$ & Lower bound & Upper bound \\
   1.291 +\hline
   1.292 +{\tt G} & $+$ or $-$ & $b_i$ & $b_i + |r_i|$ \\
   1.293 +{\tt L} & $+$ or $-$ & $b_i - |r_i|$ & $b_i$ \\
   1.294 +{\tt E} & $+$ & $b_i$ & $b_i + |r_i|$ \\
   1.295 +{\tt E} & $-$ & $b_i - |r_i|$ & $b_i$ \\
   1.296 +\end{tabular}
   1.297 +\end{center}
   1.298 +
   1.299 +\noindent
   1.300 +where $b_i$ is a right-hand side specified in the RHS section (if $b_i$
   1.301 +is not specified, it is considered as zero), $r_i$ is a range value
   1.302 +specified in the RANGES section.
   1.303 +
   1.304 +\section{BOUNDS section}
   1.305 +\label{secbounds}
   1.306 +
   1.307 +The BOUNDS section should start with the indicator card, which contains
   1.308 +the word \verb|BOUNDS| in the columns 1---6.
   1.309 +
   1.310 +Each data card in the BOUNDS section specifies one (lower or upper)
   1.311 +bound for one structural variable (column). All these data cards have
   1.312 +the following format.
   1.313 +
   1.314 +The indicator in the field 1 specifies the bound type:
   1.315 +
   1.316 +\begin{tabular}{@{}ll}
   1.317 +\verb|LO| & lower bound; \\
   1.318 +\verb|UP| & upper bound; \\
   1.319 +\verb|FX| & fixed variable (lower and upper bounds are equal); \\
   1.320 +\verb|FR| & free variable (no bounds); \\
   1.321 +\verb|MI| & no lower bound (lower bound is ``minus infinity''); \\
   1.322 +\verb|PL| & no upper bound (upper bound is ``plus infinity''); \\
   1.323 +\end{tabular}
   1.324 +
   1.325 +The field 2 specifies a name of the bound vector\footnote{This feature
   1.326 +allows the user to specify several bound vectors in the same MPS file.
   1.327 +However, before solving the problem a particular bound vector should be
   1.328 +chosen.}. If this field is empty, the bound vector name from the
   1.329 +immediately preceeding data card is assumed.
   1.330 +
   1.331 +The field 3 specifies a column name defined in the COLUMNS section.
   1.332 +
   1.333 +The field 4 specifies a bound value. If the bound type in the field 1
   1.334 +differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field
   1.335 +4 is ignored and may be omitted.
   1.336 +
   1.337 +The fields 5 and 6 are not used and should be empty.
   1.338 +
   1.339 +All bound values for the current bound vector should be specified before
   1.340 +bound values for the next bound vector. However, the order of columns in
   1.341 +the BOUNDS section may differ from the order of columns in the COLUMNS
   1.342 +section. Specification of a lower bound should precede specification of
   1.343 +an upper bound for the same column (if both the lower and upper bounds
   1.344 +are explicitly specified).
   1.345 +
   1.346 +By default, all columns (structural variables) are non-negative, i.e.
   1.347 +have zero lower bound and no upper bound. Lower ($l_j$) and upper
   1.348 +($u_j$) bounds of some column (structural variable $x_j$) are set in the
   1.349 +following way, where $s_j$ is a corresponding bound value explicitly
   1.350 +specified in the BOUNDS section:
   1.351 +
   1.352 +\begin{tabular}{@{}ll}
   1.353 +\verb|LO| & sets $l_j$ to $s_j$; \\
   1.354 +\verb|UP| & sets $u_j$ to $s_j$; \\
   1.355 +\verb|FX| & sets both $l_j$ and $u_j$ to $s_j$; \\
   1.356 +\verb|FR| & sets $l_j$ to $-\infty$ and $u_j$ to $+\infty$; \\
   1.357 +\verb|MI| & sets $l_j$ to $-\infty$; \\
   1.358 +\verb|PL| & sets $u_j$ to $+\infty$. \\
   1.359 +\end{tabular}
   1.360 +
   1.361 +\section{ENDATA indicator card}
   1.362 +
   1.363 +The ENDATA indicator card should be the last card of MPS file (except
   1.364 +optional comment cards, which may follow the ENDATA card). This card
   1.365 +should contain the word \verb|ENDATA| in the columns 1---6.
   1.366 +
   1.367 +\section{Specifying objective function}
   1.368 +
   1.369 +It is impossible to explicitly specify the objective function and
   1.370 +optimization direction in the MPS file. However, the following implicit
   1.371 +rule is used by default: the first row of \verb|N| type is considered
   1.372 +as a row of the objective function (i.e. the objective function is the
   1.373 +corresponding auxiliary variable), which should be {\it minimized}.
   1.374 +
   1.375 +GLPK also allows specifying a constant term of the objective function
   1.376 +as a right-hand side of the corresponding row in the RHS section.
   1.377 +
   1.378 +\section{Example of MPS file}
   1.379 +\label{secmpsex}
   1.380 +
   1.381 +In order to illustrate what the MPS format is, consider the following
   1.382 +example of LP problem:
   1.383 +
   1.384 +\medskip
   1.385 +\noindent minimize
   1.386 +$$
   1.387 +value = .03\ bin_1 + .08\ bin_2 + .17\ bin_3 + .12\ bin_4 + .15\ bin_5
   1.388 ++ .21\ al + .38\ si
   1.389 +$$
   1.390 +
   1.391 +\noindent subject to linear constraints
   1.392 +$$
   1.393 +\begin{array}{@{}l@{\:}l@{}}
   1.394 +yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 +
   1.395 +         \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al +
   1.396 +         \ \ \ \ \;si \\
   1.397 +FE    &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5
   1.398 +         + .01\ al + .03\ si \\
   1.399 +CU    &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5
   1.400 +         + .01\ al \\
   1.401 +MN    &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5
   1.402 +         \\
   1.403 +MG    &= .02\ bin_1 + .03\ bin_2
   1.404 +\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\
   1.405 +AL    &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5
   1.406 +         + .97\ al \\
   1.407 +SI    &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5
   1.408 +         + .01\ al + .97\ si \\
   1.409 +\end{array}
   1.410 +$$
   1.411 +and bounds of (auxiliary and structural) variables
   1.412 +$$
   1.413 +\begin{array}{r@{\ }l@{\ }l@{\ }l@{\ }rcr@{\ }l@{\ }l@{\ }l@{\ }r}
   1.414 +&&yield&=&2000&&0&\leq&bin_1&\leq&200\\
   1.415 +-\infty&<&FE&\leq&60&&0&\leq&bin_2&\leq&2500\\
   1.416 +-\infty&<&CU&\leq&100&&400&\leq&bin_3&\leq&800\\
   1.417 +-\infty&<&MN&\leq&40&&100&\leq&bin_4&\leq&700\\
   1.418 +-\infty&<&MG&\leq&30&&0&\leq&bin_5&\leq&1500\\
   1.419 +1500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\
   1.420 +250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\
   1.421 +\end{array}
   1.422 +$$
   1.423 +
   1.424 +A complete MPS file which specifies data for this example is shown
   1.425 +below (the first two comment lines show card positions).
   1.426 +
   1.427 +\begin{verbatim}
   1.428 +*000000001111111111222222222233333333334444444444555555555566
   1.429 +*234567890123456789012345678901234567890123456789012345678901
   1.430 +NAME          PLAN
   1.431 +ROWS
   1.432 + N  VALUE
   1.433 + E  YIELD
   1.434 + L  FE
   1.435 + L  CU
   1.436 + L  MN
   1.437 + L  MG
   1.438 + G  AL
   1.439 + L  SI
   1.440 +COLUMNS
   1.441 +    BIN1      VALUE           .03000   YIELD          1.00000
   1.442 +              FE              .15000   CU              .03000
   1.443 +              MN              .02000   MG              .02000
   1.444 +              AL              .70000   SI              .02000
   1.445 +    BIN2      VALUE           .08000   YIELD          1.00000
   1.446 +              FE              .04000   CU              .05000
   1.447 +              MN              .04000   MG              .03000
   1.448 +              AL              .75000   SI              .06000
   1.449 +    BIN3      VALUE           .17000   YIELD          1.00000
   1.450 +              FE              .02000   CU              .08000
   1.451 +              MN              .01000   AL              .80000
   1.452 +              SI              .08000
   1.453 +    BIN4      VALUE           .12000   YIELD          1.00000
   1.454 +              FE              .04000   CU              .02000
   1.455 +              MN              .02000   AL              .75000
   1.456 +              SI              .12000
   1.457 +    BIN5      VALUE           .15000   YIELD          1.00000
   1.458 +              FE              .02000   CU              .06000
   1.459 +              MN              .02000   MG              .01000
   1.460 +              AL              .80000   SI              .02000
   1.461 +    ALUM      VALUE           .21000   YIELD          1.00000
   1.462 +              FE              .01000   CU              .01000
   1.463 +              AL              .97000   SI              .01000
   1.464 +    SILICON   VALUE           .38000   YIELD          1.00000
   1.465 +              FE              .03000   SI              .97000
   1.466 +RHS
   1.467 +    RHS1      YIELD       2000.00000   FE            60.00000
   1.468 +              CU           100.00000   MN            40.00000
   1.469 +              SI           300.00000
   1.470 +              MG            30.00000   AL          1500.00000
   1.471 +RANGES
   1.472 +    RNG1      SI            50.00000
   1.473 +BOUNDS
   1.474 + UP BND1      BIN1         200.00000
   1.475 + UP           BIN2        2500.00000
   1.476 + LO           BIN3         400.00000
   1.477 + UP           BIN3         800.00000
   1.478 + LO           BIN4         100.00000
   1.479 + UP           BIN4         700.00000
   1.480 + UP           BIN5        1500.00000
   1.481 +ENDATA
   1.482 +\end{verbatim}
   1.483 +
   1.484 +\section{MIP features}
   1.485 +
   1.486 +The MPS format provides two ways for introducing integer variables into
   1.487 +the problem.
   1.488 +
   1.489 +The first way is most general and based on using special marker cards
   1.490 +INTORG and INTEND. These marker cards are placed in the COLUMNS section.
   1.491 +The INTORG card indicates the start of a group of integer variables
   1.492 +(columns), and the card INTEND indicates the end of the group. The MPS
   1.493 +file may contain arbitrary number of the marker cards.
   1.494 +
   1.495 +The marker cards have the same format as the data cards (see Section
   1.496 +\ref{secmps}, page \pageref{secmps}).
   1.497 +
   1.498 +The fields 1, 2, and 6 are not used and should be empty.
   1.499 +
   1.500 +The field 2 should contain a marker name. This name may be arbitrary.
   1.501 +
   1.502 +The field 3 should contain the word \verb|'MARKER'| (including
   1.503 +apostrophes).
   1.504 +
   1.505 +The field 5 should contain either the word \verb|'INTORG'| (including
   1.506 +apostrophes) for the marker card, which begins a group of integer
   1.507 +columns, or the word \verb|'INTEND'| (including apostrophes) for the
   1.508 +marker card, which ends the group.
   1.509 +
   1.510 +The second way is less general but more convenient in some cases. It
   1.511 +allows the user declaring integer columns using three additional types
   1.512 +of bounds, which are specified in the field 1 of data cards in the
   1.513 +BOUNDS section (see Section \ref{secbounds}, page \pageref{secbounds}):
   1.514 +
   1.515 +\begin{tabular}{@{}lp{112.3mm}@{}}
   1.516 +\verb|LI| & lower integer. This bound type specifies that the
   1.517 +corresponding column (structural variable), whose name is specified in
   1.518 +field 3, is of integer kind. In this case an lower bound of the
   1.519 +column should be specified in field 4 (like in the case of \verb|LO|
   1.520 +bound type). \\
   1.521 +\verb|UI| & upper integer. This bound type specifies that the
   1.522 +corresponding column (structural variable), whose name is specified in
   1.523 +field 3, is of integer kind. In this case an upper bound of the
   1.524 +column should be specified in field 4 (like in the case of \verb|UP|
   1.525 +bound type). \\
   1.526 +\end{tabular}
   1.527 +
   1.528 +\pagebreak
   1.529 +
   1.530 +\begin{tabular}{@{}lp{112.3mm}@{}}
   1.531 +\verb|BV| & binary variable. This bound type specifies that the
   1.532 +corresponding column (structural variable), whose name is specified in
   1.533 +the field 3, is of integer kind, its lower bound is zero, and its upper
   1.534 +bound is one (thus, such variable being of integer kind can have only
   1.535 +two values zero and one). In this case a numeric value specified in the
   1.536 +field 4 is ignored and may be omitted.\\
   1.537 +\end{tabular}
   1.538 +
   1.539 +Consider the following example of MIP problem:
   1.540 +
   1.541 +\medskip
   1.542 +
   1.543 +\noindent
   1.544 +\hspace{1in} minimize
   1.545 +$$Z = 3 x_1 + 7 x_2 - x_3 + x4$$
   1.546 +\hspace{1in} subject to linear constraints
   1.547 +$$
   1.548 +\begin{array}{c}
   1.549 +\nonumber r_1 = 2   x_1 - \ \ x_2 + \ \ x_3 - \ \;x_4 \\
   1.550 +\nonumber r_2 = \ \;x_1 - \ \;x_2 - 6   x_3 + 4   x_4 \\
   1.551 +\nonumber r_3 = 5   x_1 +   3 x_2 \ \ \ \ \ \ \ \ \ + \ \ x_4 \\
   1.552 +\end{array}
   1.553 +$$
   1.554 +\hspace{1in} and bound of variables
   1.555 +$$
   1.556 +\begin{array}{cccl}
   1.557 +\nonumber 1 \leq r_1 < +\infty && 0 \leq x_1 \leq 4 &{\rm(continuous)}\\
   1.558 +\nonumber 8 \leq r_2 < +\infty && 2 \leq x_2 \leq 5 &{\rm(integer)}   \\
   1.559 +\nonumber 5 \leq r_3 < +\infty && 0 \leq x_3 \leq 1 &{\rm(integer)}   \\
   1.560 +\nonumber                      && 3 \leq x_4 \leq 8 &{\rm(continuous)}\\
   1.561 +\end{array}
   1.562 +$$
   1.563 +
   1.564 +The corresponding MPS file may look like the following:
   1.565 +
   1.566 +\begin{verbatim}
   1.567 +NAME          SAMP1
   1.568 +ROWS
   1.569 + N  Z
   1.570 + G  R1
   1.571 + G  R2
   1.572 + G  R3
   1.573 +COLUMNS
   1.574 +    X1        R1                2.0    R2                 1.0
   1.575 +    X1        R3                5.0    Z                  3.0
   1.576 +    MARK0001  'MARKER'                 'INTORG'
   1.577 +    X2        R1               -1.0    R2                -1.0
   1.578 +    X2        R3                3.0    Z                  7.0
   1.579 +    X3        R1                1.0    R2                -6.0
   1.580 +    X3        Z                -1.0
   1.581 +    MARK0002  'MARKER'                 'INTEND'
   1.582 +    X4        R1               -1.0    R2                 4.0
   1.583 +    X4        R3                1.0    Z                  1.0
   1.584 +RHS
   1.585 +    RHS1      R1                1.0
   1.586 +    RHS1      R2                8.0
   1.587 +    RHS1      R3                5.0
   1.588 +BOUNDS
   1.589 + UP BND1      X1                4.0
   1.590 + LO BND1      X2                2.0
   1.591 + UP BND1      X2                5.0
   1.592 + UP BND1      X3                1.0
   1.593 + LO BND1      X4                3.0
   1.594 + UP BND1      X4                8.0
   1.595 +ENDATA
   1.596 +\end{verbatim}
   1.597 +
   1.598 +The same example may be coded without INTORG/INTEND markers using the
   1.599 +bound type UI for the variable $x_2$ and the bound type BV for the
   1.600 +variable $x_3$:
   1.601 +
   1.602 +\begin{verbatim}
   1.603 +NAME          SAMP2
   1.604 +ROWS
   1.605 + N  Z
   1.606 + G  R1
   1.607 + G  R2
   1.608 + G  R3
   1.609 +COLUMNS
   1.610 +    X1        R1                2.0    R2                 1.0
   1.611 +    X1        R3                5.0    Z                  3.0
   1.612 +    X2        R1               -1.0    R2                -1.0
   1.613 +    X2        R3                3.0    Z                  7.0
   1.614 +    X3        R1                1.0    R2                -6.0
   1.615 +    X3        Z                -1.0
   1.616 +    X4        R1               -1.0    R2                 4.0
   1.617 +    X4        R3                1.0    Z                  1.0
   1.618 +RHS
   1.619 +    RHS1      R1                1.0
   1.620 +    RHS1      R2                8.0
   1.621 +    RHS1      R3                5.0
   1.622 +BOUNDS
   1.623 + UP BND1      X1                4.0
   1.624 + LO BND1      X2                2.0
   1.625 + UI BND1      X2                5.0
   1.626 + BV BND1      X3
   1.627 + LO BND1      X4                3.0
   1.628 + UP BND1      X4                8.0
   1.629 +ENDATA
   1.630 +\end{verbatim}
   1.631 +
   1.632 +%\section{Specifying predefined basis}
   1.633 +%\label{secbas}
   1.634 +%
   1.635 +%The MPS format can also be used to specify some predefined basis for an
   1.636 +%LP problem, i.e. to specify which rows and columns are basic and which
   1.637 +%are non-basic.
   1.638 +%
   1.639 +%The order of a basis file in the MPS format is:
   1.640 +%
   1.641 +%$\bullet$ NAME indicator card;
   1.642 +%
   1.643 +%$\bullet$ data cards (can appear in arbitrary order);
   1.644 +%
   1.645 +%$\bullet$ ENDATA indicator card.
   1.646 +%
   1.647 +%Each data card specifies either a pair "basic column---non-basic row"
   1.648 +%or a non-basic column. All the data cards have the following format.
   1.649 +%
   1.650 +%`\verb|XL|' in the field 1 means that a column, whose name is given in
   1.651 +%the field 2, is basic, and a row, whose name is given in the field 3,
   1.652 +%is non-basic and placed on its lower bound.
   1.653 +%
   1.654 +%`\verb|XU|' in the field 1 means that a column, whose name is given in
   1.655 +%the field 2, is basic, and a row, whose name is given in the field 3,
   1.656 +%is non-basic and placed on its upper bound.
   1.657 +%
   1.658 +%`\verb|LL|' in the field 1 means that a column, whose name is given in
   1.659 +%the field 3, is non-basic and placed on its lower bound.
   1.660 +%
   1.661 +%`\verb|UL|' in the field 1 means that a column, whose name is given in
   1.662 +%the field 3, is non-basic and placed on its upper bound.
   1.663 +%
   1.664 +%The field 2 contains a column name.
   1.665 +%
   1.666 +%If the indicator given in the field 1 is `\verb|XL|' or `\verb|XU|',
   1.667 +%the field 3 contains a row name. Otherwise, if the indicator is
   1.668 +%`\verb|LL|' or `\verb|UL|', the field 3 is not used and should be
   1.669 +%empty.
   1.670 +%
   1.671 +%The field 4, 5, and 6 are not used and should be empty.
   1.672 +%
   1.673 +%A basis file in the MPS format acts like a patch: it doesn't specify
   1.674 +%a basis completely, instead that it is just shows in what a given basis
   1.675 +%differs from the "standard" basis, where all rows (auxiliary variables)
   1.676 +%are assumed to be basic and all columns (structural variables) are
   1.677 +%assumed to be non-basic.
   1.678 +%
   1.679 +%As an example here is a basis file that specifies an optimal basis
   1.680 +%for the example LP problem given in Section \ref{secmpsex},
   1.681 +%Page \pageref{secmpsex}:
   1.682 +%
   1.683 +%\pagebreak
   1.684 +%
   1.685 +%\begin{verbatim}
   1.686 +%*000000001111111111222222222233333333334444444444555555555566
   1.687 +%*234567890123456789012345678901234567890123456789012345678901
   1.688 +%NAME          PLAN
   1.689 +% XL BIN2      YIELD
   1.690 +% XL BIN3      FE
   1.691 +% XL BIN4      MN
   1.692 +% XL ALUM      AL
   1.693 +% XL SILICON   SI
   1.694 +% LL BIN1
   1.695 +% LL BIN5
   1.696 +%ENDATA
   1.697 +%\end{verbatim}
   1.698 +
   1.699 +%* eof *%