lemon-project-template-glpk

annotate deps/glpk/doc/glpk08.tex @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 %* glpk08.tex *%
alpar@9 2
alpar@9 3 \chapter{MPS Format}
alpar@9 4 \label{champs}
alpar@9 5
alpar@9 6 \section{Fixed MPS Format}
alpar@9 7 \label{secmps}
alpar@9 8
alpar@9 9 The MPS format\footnote{The MPS format was developed in 1960's by IBM
alpar@9 10 as input format for their mathematical programming system MPS/360.
alpar@9 11 Today the MPS format is a most widely used format understood by most
alpar@9 12 mathematical programming packages. This appendix describes only the
alpar@9 13 features of the MPS format, which are implemented in the GLPK package.}
alpar@9 14 is intended for coding LP/MIP problem data. This format assumes the
alpar@9 15 formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp},
alpar@9 16 page \pageref{seclp}).
alpar@9 17
alpar@9 18 {\it MPS file} is a text file, which contains two types of
alpar@9 19 cards\footnote{In 1960's MPS file was a deck of 80-column punched cards,
alpar@9 20 so the author decided to keep the word ``card'', which may be understood
alpar@9 21 as ``line of text file''.}: indicator cards and data cards.
alpar@9 22
alpar@9 23 Indicator cards determine a kind of succeeding data. Each indicator card
alpar@9 24 has one word in uppercase letters beginning in column 1.
alpar@9 25
alpar@9 26 Data cards contain problem data. Each data card is divided into six
alpar@9 27 fixed fields:
alpar@9 28
alpar@9 29 \begin{center}
alpar@9 30 \begin{tabular}{lcccccc}
alpar@9 31 & Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\
alpar@9 32 \hline
alpar@9 33 Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\
alpar@9 34 Contents & Code & Name & Name & Number & Name & Number \\
alpar@9 35 \end{tabular}
alpar@9 36 \end{center}
alpar@9 37
alpar@9 38 On a particular data card some fields may be optional.
alpar@9 39
alpar@9 40 Names are used to identify rows, columns, and some vectors (see below).
alpar@9 41
alpar@9 42 Aligning the indicator code in the field 1 to the left margin is
alpar@9 43 optional.
alpar@9 44
alpar@9 45 All names specified in the fields 2, 3, and 5 should contain from 1 up
alpar@9 46 to 8 arbitrary characters (except control characters). If a name is
alpar@9 47 placed in the field 3 or 5, its first character should not be the dollar
alpar@9 48 sign `\verb|$|'. If a name contains spaces, the spaces are ignored.
alpar@9 49
alpar@9 50 All numerical values in the fields 4 and 6 should be coded in the form
alpar@9 51 $sxx$\verb|E|$syy$, where $s$ is the plus `\verb|+|' or the minus
alpar@9 52 `\verb|-|' sign, $xx$ is a real number with optional decimal point,
alpar@9 53 $yy$ is an integer decimal exponent. Any number should contain up to 12
alpar@9 54 characters. If the sign $s$ is omitted, the plus sign is assumed. The
alpar@9 55 exponent part is optional. If a number contains spaces, the spaces are
alpar@9 56 ignored.
alpar@9 57
alpar@9 58 If a card has the asterisk `\verb|*|' in the column 1, this card is
alpar@9 59 considered as a comment and ignored. Besides, if the first character in
alpar@9 60 the field 3 or 5 is the dollar sign `\verb|$|', all characters from the
alpar@9 61 dollar sign to the end of card are considered as a comment and ignored.
alpar@9 62
alpar@9 63 MPS file should contain cards in the following order:
alpar@9 64
alpar@9 65 $\bullet$ NAME indicator card;
alpar@9 66
alpar@9 67 $\bullet$ ROWS indicator card;
alpar@9 68
alpar@9 69 $\bullet$ data cards specifying rows (constraints);
alpar@9 70
alpar@9 71 $\bullet$ COLUMNS indicator card;
alpar@9 72
alpar@9 73 $\bullet$ data cards specifying columns (structural variables) and
alpar@9 74 constraint coefficients;
alpar@9 75
alpar@9 76 $\bullet$ RHS indicator card;
alpar@9 77
alpar@9 78 $\bullet$ data cards specifying right-hand sides of constraints;
alpar@9 79
alpar@9 80 $\bullet$ RANGES indicator card;
alpar@9 81
alpar@9 82 $\bullet$ data cards specifying ranges for double-bounded constraints;
alpar@9 83
alpar@9 84 $\bullet$ BOUNDS indicator card;
alpar@9 85
alpar@9 86 $\bullet$ data cards specifying types and bounds of structural
alpar@9 87 variables;
alpar@9 88
alpar@9 89 $\bullet$ ENDATA indicator card.
alpar@9 90
alpar@9 91 {\it Section} is a group of cards consisting of an indicator card and
alpar@9 92 data cards succeeding this indicator card. For example, the ROWS section
alpar@9 93 consists of the ROWS indicator card and data cards specifying rows.
alpar@9 94
alpar@9 95 The sections RHS, RANGES, and BOUNDS are optional and may be omitted.
alpar@9 96
alpar@9 97 \section{Free MPS Format}
alpar@9 98
alpar@9 99 {\it Free MPS format} is an improved version of the standard (fixed)
alpar@9 100 MPS format described above.\footnote{This format was developed in the
alpar@9 101 beginning of 1990's by IBM as an alternative to the standard fixed MPS
alpar@9 102 format for Optimization Subroutine Library (OSL).} Note that all
alpar@9 103 changes in free MPS format concern only the coding of data while the
alpar@9 104 structure of data is the same for both fixed and free versions of the
alpar@9 105 MPS format.
alpar@9 106
alpar@9 107 In free MPS format indicator and data records\footnote{{\it Record} in
alpar@9 108 free MPS format has the same meaning as {\it card} in fixed MPS format.}
alpar@9 109 may have arbitrary length not limited to 80 characters. Fields of data
alpar@9 110 records have no predefined positions, i.e. the fields may begin in any
alpar@9 111 position, except position 1, which must be blank, and must be separated
alpar@9 112 from each other by one or more blanks. However, the fields must appear
alpar@9 113 in the same order as in fixed MPS format.
alpar@9 114
alpar@9 115 Symbolic names in fields 2, 3, and 5 may be longer than 8
alpar@9 116 characters\footnote{GLPK allows symbolic names having up to 255
alpar@9 117 characters.}
alpar@9 118 and must not contain embedded blanks.
alpar@9 119
alpar@9 120 Numeric values in fields 4 and 6 are limited to 12 characters and must
alpar@9 121 not contain embedded blanks.
alpar@9 122
alpar@9 123 Only six fields on each data record are used. Any other fields are
alpar@9 124 ignored.
alpar@9 125
alpar@9 126 If the first character of any field (not necessarily fields 3 and 5)
alpar@9 127 is the dollar sign (\$), all characters from the dollar sign to the end
alpar@9 128 of record are considered as a comment and ignored.
alpar@9 129
alpar@9 130 \section{NAME indicator card}
alpar@9 131
alpar@9 132 The NAME indicator card should be the first card in the MPS file (except
alpar@9 133 optional comment cards, which may precede the NAME card). This card
alpar@9 134 should contain the word \verb|NAME| in the columns 1---4 and the problem
alpar@9 135 name in the field 3. The problem name is optional and may be omitted.
alpar@9 136
alpar@9 137 \section{ROWS section}
alpar@9 138 \label{secrows}
alpar@9 139
alpar@9 140 The ROWS section should start with the indicator card, which contains
alpar@9 141 the word \verb|ROWS| in the columns 1---4.
alpar@9 142
alpar@9 143 Each data card in the ROWS section specifies one row (constraint) of the
alpar@9 144 problem. All these data cards have the following format.
alpar@9 145
alpar@9 146 `\verb|N|' in the field 1 means that the row is free (unbounded):
alpar@9 147 $$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
alpar@9 148 < +\infty;$$
alpar@9 149
alpar@9 150 `\verb|L|' in the field 1 means that the row is of ``less than or equal
alpar@9 151 to'' type:
alpar@9 152 $$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
alpar@9 153 \leq b_i;$$
alpar@9 154
alpar@9 155 `\verb|G|' in the field 1 means that the row is of ``greater than or
alpar@9 156 equal to'' type:
alpar@9 157 $$b_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
alpar@9 158 < +\infty;$$
alpar@9 159
alpar@9 160 `\verb|E|' in the field 1 means that the row is of ``equal to'' type:
alpar@9 161 $$x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} \leq
alpar@9 162 b_i,$$
alpar@9 163 where $b_i$ is a right-hand side. Note that each constraint has a
alpar@9 164 corresponding implictly defined auxiliary variable ($x_i$ above), whose
alpar@9 165 value is a value of the corresponding linear form, therefore row bounds
alpar@9 166 can be considered as bounds of such auxiliary variable.
alpar@9 167
alpar@9 168 The filed 2 specifies a row name (which is considered as the name of
alpar@9 169 the corresponding auxiliary variable).
alpar@9 170
alpar@9 171 The fields 3, 4, 5, and 6 are not used and should be empty.
alpar@9 172
alpar@9 173 Numerical values of all non-zero right-hand sides $b_i$ should be
alpar@9 174 specified in the RHS section (see below). All double-bounded (ranged)
alpar@9 175 constraints should be specified in the RANGES section (see below).
alpar@9 176
alpar@9 177 \section{COLUMNS section}
alpar@9 178
alpar@9 179 The COLUMNS section should start with the indicator card, which contains
alpar@9 180 the word \verb|COLUMNS| in the columns 1---7.
alpar@9 181
alpar@9 182 Each data card in the COLUMNS section specifies one or two constraint
alpar@9 183 coefficients $a_{ij}$ and also introduces names of columns, i.e. names
alpar@9 184 of structural variables. All these data cards have the following format.
alpar@9 185
alpar@9 186 The field 1 is not used and should be empty.
alpar@9 187
alpar@9 188 The field 2 specifies a column name. If this field is empty, the column
alpar@9 189 name from the immediately preceeding data card is assumed.
alpar@9 190
alpar@9 191 The field 3 specifies a row name defined in the ROWS section.
alpar@9 192
alpar@9 193 The field 4 specifies a numerical value of the constraint coefficient
alpar@9 194 $a_{ij}$, which is placed in the corresponding row and column.
alpar@9 195
alpar@9 196 The fields 5 and 6 are optional. If they are used, they should contain
alpar@9 197 a second pair ``row name---constraint coefficient'' for the same column.
alpar@9 198
alpar@9 199 Elements of the constraint matrix (i.e. constraint coefficients) should
alpar@9 200 be enumerated in the column wise manner: all elements for the current
alpar@9 201 column should be specified before elements for the next column. However,
alpar@9 202 the order of rows in the COLUMNS section may differ from the order of
alpar@9 203 rows in the ROWS section.
alpar@9 204
alpar@9 205 Constraint coefficients not specified in the COLUMNS section are
alpar@9 206 considered as zeros. Therefore zero coefficients may be omitted,
alpar@9 207 although it is allowed to explicitly specify them.
alpar@9 208
alpar@9 209 \section{RHS section}
alpar@9 210
alpar@9 211 The RHS section should start with the indicator card, which contains the
alpar@9 212 word \verb|RHS| in the columns 1---3.
alpar@9 213
alpar@9 214 Each data card in the RHS section specifies one or two right-hand sides
alpar@9 215 $b_i$ (see Section \ref{secrows}, page \pageref{secrows}). All these
alpar@9 216 data cards have the following format.
alpar@9 217
alpar@9 218 The field 1 is not used and should be empty.
alpar@9 219
alpar@9 220 The field 2 specifies a name of the right-hand side (RHS)
alpar@9 221 vector\footnote{This feature allows the user to specify several RHS
alpar@9 222 vectors in the same MPS file. However, before solving the problem a
alpar@9 223 particular RHS vector should be chosen.}. If this field is empty, the
alpar@9 224 RHS vector name from the immediately preceeding data card is assumed.
alpar@9 225
alpar@9 226 The field 3 specifies a row name defined in the ROWS section.
alpar@9 227
alpar@9 228 The field 4 specifies a right-hand side $b_i$ for the row, whose name is
alpar@9 229 specified in the field 3. Depending on the row type $b_i$ is a lower
alpar@9 230 bound (for the row of \verb|G| type), an upper bound (for the row of
alpar@9 231 \verb|L| type), or a fixed value (for the row of \verb|E|
alpar@9 232 type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as
alpar@9 233 a constant term of the corresponding linear form. Should note, however,
alpar@9 234 this convention is non-standard.}
alpar@9 235
alpar@9 236 The fields 5 and 6 are optional. If they are used, they should contain
alpar@9 237 a second pair ``row name---right-hand side'' for the same RHS vector.
alpar@9 238
alpar@9 239 All right-hand sides for the current RHS vector should be specified
alpar@9 240 before right-hand sides for the next RHS vector. However, the order of
alpar@9 241 rows in the RHS section may differ from the order of rows in the ROWS
alpar@9 242 section.
alpar@9 243
alpar@9 244 Right-hand sides not specified in the RHS section are considered as
alpar@9 245 zeros. Therefore zero right-hand sides may be omitted, although it is
alpar@9 246 allowed to explicitly specify them.
alpar@9 247
alpar@9 248 \section{RANGES section}
alpar@9 249
alpar@9 250 The RANGES section should start with the indicator card, which contains
alpar@9 251 the word \verb|RANGES| in the columns 1---6.
alpar@9 252
alpar@9 253 Each data card in the RANGES section specifies one or two ranges for
alpar@9 254 double-side constraints, i.e. for constraints that are of the types
alpar@9 255 \verb|L| and \verb|G| at the same time:
alpar@9 256 $$l_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
alpar@9 257 \leq u_i,$$
alpar@9 258 where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data
alpar@9 259 cards have the following format.
alpar@9 260
alpar@9 261 The field 1 is not used and should be empty.
alpar@9 262
alpar@9 263 The field 2 specifies a name of the range vector\footnote{This feature
alpar@9 264 allows the user to specify several range vectors in the same MPS file.
alpar@9 265 However, before solving the problem a particular range vector should be
alpar@9 266 chosen.}. If this field is empty, the range vector name from the
alpar@9 267 immediately preceeding data card is assumed.
alpar@9 268
alpar@9 269 The field 3 specifies a row name defined in the ROWS section.
alpar@9 270
alpar@9 271 The field 4 specifies a range value $r_i$ (see the table below) for the
alpar@9 272 row, whose name is specified in the field 3.
alpar@9 273
alpar@9 274 The fields 5 and 6 are optional. If they are used, they should contain
alpar@9 275 a second pair ``row name---range value'' for the same range vector.
alpar@9 276
alpar@9 277 All range values for the current range vector should be specified before
alpar@9 278 range values for the next range vector. However, the order of rows in
alpar@9 279 the RANGES section may differ from the order of rows in the ROWS
alpar@9 280 section.
alpar@9 281
alpar@9 282 For each double-side constraint specified in the RANGES section its
alpar@9 283 lower and upper bounds are determined as follows:
alpar@9 284
alpar@9 285 \begin{center}
alpar@9 286 \begin{tabular}{cccc}
alpar@9 287 Row type & Sign of $r_i$ & Lower bound & Upper bound \\
alpar@9 288 \hline
alpar@9 289 {\tt G} & $+$ or $-$ & $b_i$ & $b_i + |r_i|$ \\
alpar@9 290 {\tt L} & $+$ or $-$ & $b_i - |r_i|$ & $b_i$ \\
alpar@9 291 {\tt E} & $+$ & $b_i$ & $b_i + |r_i|$ \\
alpar@9 292 {\tt E} & $-$ & $b_i - |r_i|$ & $b_i$ \\
alpar@9 293 \end{tabular}
alpar@9 294 \end{center}
alpar@9 295
alpar@9 296 \noindent
alpar@9 297 where $b_i$ is a right-hand side specified in the RHS section (if $b_i$
alpar@9 298 is not specified, it is considered as zero), $r_i$ is a range value
alpar@9 299 specified in the RANGES section.
alpar@9 300
alpar@9 301 \section{BOUNDS section}
alpar@9 302 \label{secbounds}
alpar@9 303
alpar@9 304 The BOUNDS section should start with the indicator card, which contains
alpar@9 305 the word \verb|BOUNDS| in the columns 1---6.
alpar@9 306
alpar@9 307 Each data card in the BOUNDS section specifies one (lower or upper)
alpar@9 308 bound for one structural variable (column). All these data cards have
alpar@9 309 the following format.
alpar@9 310
alpar@9 311 The indicator in the field 1 specifies the bound type:
alpar@9 312
alpar@9 313 \begin{tabular}{@{}ll}
alpar@9 314 \verb|LO| & lower bound; \\
alpar@9 315 \verb|UP| & upper bound; \\
alpar@9 316 \verb|FX| & fixed variable (lower and upper bounds are equal); \\
alpar@9 317 \verb|FR| & free variable (no bounds); \\
alpar@9 318 \verb|MI| & no lower bound (lower bound is ``minus infinity''); \\
alpar@9 319 \verb|PL| & no upper bound (upper bound is ``plus infinity''); \\
alpar@9 320 \end{tabular}
alpar@9 321
alpar@9 322 The field 2 specifies a name of the bound vector\footnote{This feature
alpar@9 323 allows the user to specify several bound vectors in the same MPS file.
alpar@9 324 However, before solving the problem a particular bound vector should be
alpar@9 325 chosen.}. If this field is empty, the bound vector name from the
alpar@9 326 immediately preceeding data card is assumed.
alpar@9 327
alpar@9 328 The field 3 specifies a column name defined in the COLUMNS section.
alpar@9 329
alpar@9 330 The field 4 specifies a bound value. If the bound type in the field 1
alpar@9 331 differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field
alpar@9 332 4 is ignored and may be omitted.
alpar@9 333
alpar@9 334 The fields 5 and 6 are not used and should be empty.
alpar@9 335
alpar@9 336 All bound values for the current bound vector should be specified before
alpar@9 337 bound values for the next bound vector. However, the order of columns in
alpar@9 338 the BOUNDS section may differ from the order of columns in the COLUMNS
alpar@9 339 section. Specification of a lower bound should precede specification of
alpar@9 340 an upper bound for the same column (if both the lower and upper bounds
alpar@9 341 are explicitly specified).
alpar@9 342
alpar@9 343 By default, all columns (structural variables) are non-negative, i.e.
alpar@9 344 have zero lower bound and no upper bound. Lower ($l_j$) and upper
alpar@9 345 ($u_j$) bounds of some column (structural variable $x_j$) are set in the
alpar@9 346 following way, where $s_j$ is a corresponding bound value explicitly
alpar@9 347 specified in the BOUNDS section:
alpar@9 348
alpar@9 349 \begin{tabular}{@{}ll}
alpar@9 350 \verb|LO| & sets $l_j$ to $s_j$; \\
alpar@9 351 \verb|UP| & sets $u_j$ to $s_j$; \\
alpar@9 352 \verb|FX| & sets both $l_j$ and $u_j$ to $s_j$; \\
alpar@9 353 \verb|FR| & sets $l_j$ to $-\infty$ and $u_j$ to $+\infty$; \\
alpar@9 354 \verb|MI| & sets $l_j$ to $-\infty$; \\
alpar@9 355 \verb|PL| & sets $u_j$ to $+\infty$. \\
alpar@9 356 \end{tabular}
alpar@9 357
alpar@9 358 \section{ENDATA indicator card}
alpar@9 359
alpar@9 360 The ENDATA indicator card should be the last card of MPS file (except
alpar@9 361 optional comment cards, which may follow the ENDATA card). This card
alpar@9 362 should contain the word \verb|ENDATA| in the columns 1---6.
alpar@9 363
alpar@9 364 \section{Specifying objective function}
alpar@9 365
alpar@9 366 It is impossible to explicitly specify the objective function and
alpar@9 367 optimization direction in the MPS file. However, the following implicit
alpar@9 368 rule is used by default: the first row of \verb|N| type is considered
alpar@9 369 as a row of the objective function (i.e. the objective function is the
alpar@9 370 corresponding auxiliary variable), which should be {\it minimized}.
alpar@9 371
alpar@9 372 GLPK also allows specifying a constant term of the objective function
alpar@9 373 as a right-hand side of the corresponding row in the RHS section.
alpar@9 374
alpar@9 375 \section{Example of MPS file}
alpar@9 376 \label{secmpsex}
alpar@9 377
alpar@9 378 In order to illustrate what the MPS format is, consider the following
alpar@9 379 example of LP problem:
alpar@9 380
alpar@9 381 \medskip
alpar@9 382 \noindent minimize
alpar@9 383 $$
alpar@9 384 value = .03\ bin_1 + .08\ bin_2 + .17\ bin_3 + .12\ bin_4 + .15\ bin_5
alpar@9 385 + .21\ al + .38\ si
alpar@9 386 $$
alpar@9 387
alpar@9 388 \noindent subject to linear constraints
alpar@9 389 $$
alpar@9 390 \begin{array}{@{}l@{\:}l@{}}
alpar@9 391 yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 +
alpar@9 392 \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al +
alpar@9 393 \ \ \ \ \;si \\
alpar@9 394 FE &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5
alpar@9 395 + .01\ al + .03\ si \\
alpar@9 396 CU &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5
alpar@9 397 + .01\ al \\
alpar@9 398 MN &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5
alpar@9 399 \\
alpar@9 400 MG &= .02\ bin_1 + .03\ bin_2
alpar@9 401 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\
alpar@9 402 AL &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5
alpar@9 403 + .97\ al \\
alpar@9 404 SI &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5
alpar@9 405 + .01\ al + .97\ si \\
alpar@9 406 \end{array}
alpar@9 407 $$
alpar@9 408 and bounds of (auxiliary and structural) variables
alpar@9 409 $$
alpar@9 410 \begin{array}{r@{\ }l@{\ }l@{\ }l@{\ }rcr@{\ }l@{\ }l@{\ }l@{\ }r}
alpar@9 411 &&yield&=&2000&&0&\leq&bin_1&\leq&200\\
alpar@9 412 -\infty&<&FE&\leq&60&&0&\leq&bin_2&\leq&2500\\
alpar@9 413 -\infty&<&CU&\leq&100&&400&\leq&bin_3&\leq&800\\
alpar@9 414 -\infty&<&MN&\leq&40&&100&\leq&bin_4&\leq&700\\
alpar@9 415 -\infty&<&MG&\leq&30&&0&\leq&bin_5&\leq&1500\\
alpar@9 416 1500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\
alpar@9 417 250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\
alpar@9 418 \end{array}
alpar@9 419 $$
alpar@9 420
alpar@9 421 A complete MPS file which specifies data for this example is shown
alpar@9 422 below (the first two comment lines show card positions).
alpar@9 423
alpar@9 424 \begin{verbatim}
alpar@9 425 *000000001111111111222222222233333333334444444444555555555566
alpar@9 426 *234567890123456789012345678901234567890123456789012345678901
alpar@9 427 NAME PLAN
alpar@9 428 ROWS
alpar@9 429 N VALUE
alpar@9 430 E YIELD
alpar@9 431 L FE
alpar@9 432 L CU
alpar@9 433 L MN
alpar@9 434 L MG
alpar@9 435 G AL
alpar@9 436 L SI
alpar@9 437 COLUMNS
alpar@9 438 BIN1 VALUE .03000 YIELD 1.00000
alpar@9 439 FE .15000 CU .03000
alpar@9 440 MN .02000 MG .02000
alpar@9 441 AL .70000 SI .02000
alpar@9 442 BIN2 VALUE .08000 YIELD 1.00000
alpar@9 443 FE .04000 CU .05000
alpar@9 444 MN .04000 MG .03000
alpar@9 445 AL .75000 SI .06000
alpar@9 446 BIN3 VALUE .17000 YIELD 1.00000
alpar@9 447 FE .02000 CU .08000
alpar@9 448 MN .01000 AL .80000
alpar@9 449 SI .08000
alpar@9 450 BIN4 VALUE .12000 YIELD 1.00000
alpar@9 451 FE .04000 CU .02000
alpar@9 452 MN .02000 AL .75000
alpar@9 453 SI .12000
alpar@9 454 BIN5 VALUE .15000 YIELD 1.00000
alpar@9 455 FE .02000 CU .06000
alpar@9 456 MN .02000 MG .01000
alpar@9 457 AL .80000 SI .02000
alpar@9 458 ALUM VALUE .21000 YIELD 1.00000
alpar@9 459 FE .01000 CU .01000
alpar@9 460 AL .97000 SI .01000
alpar@9 461 SILICON VALUE .38000 YIELD 1.00000
alpar@9 462 FE .03000 SI .97000
alpar@9 463 RHS
alpar@9 464 RHS1 YIELD 2000.00000 FE 60.00000
alpar@9 465 CU 100.00000 MN 40.00000
alpar@9 466 SI 300.00000
alpar@9 467 MG 30.00000 AL 1500.00000
alpar@9 468 RANGES
alpar@9 469 RNG1 SI 50.00000
alpar@9 470 BOUNDS
alpar@9 471 UP BND1 BIN1 200.00000
alpar@9 472 UP BIN2 2500.00000
alpar@9 473 LO BIN3 400.00000
alpar@9 474 UP BIN3 800.00000
alpar@9 475 LO BIN4 100.00000
alpar@9 476 UP BIN4 700.00000
alpar@9 477 UP BIN5 1500.00000
alpar@9 478 ENDATA
alpar@9 479 \end{verbatim}
alpar@9 480
alpar@9 481 \section{MIP features}
alpar@9 482
alpar@9 483 The MPS format provides two ways for introducing integer variables into
alpar@9 484 the problem.
alpar@9 485
alpar@9 486 The first way is most general and based on using special marker cards
alpar@9 487 INTORG and INTEND. These marker cards are placed in the COLUMNS section.
alpar@9 488 The INTORG card indicates the start of a group of integer variables
alpar@9 489 (columns), and the card INTEND indicates the end of the group. The MPS
alpar@9 490 file may contain arbitrary number of the marker cards.
alpar@9 491
alpar@9 492 The marker cards have the same format as the data cards (see Section
alpar@9 493 \ref{secmps}, page \pageref{secmps}).
alpar@9 494
alpar@9 495 The fields 1, 2, and 6 are not used and should be empty.
alpar@9 496
alpar@9 497 The field 2 should contain a marker name. This name may be arbitrary.
alpar@9 498
alpar@9 499 The field 3 should contain the word \verb|'MARKER'| (including
alpar@9 500 apostrophes).
alpar@9 501
alpar@9 502 The field 5 should contain either the word \verb|'INTORG'| (including
alpar@9 503 apostrophes) for the marker card, which begins a group of integer
alpar@9 504 columns, or the word \verb|'INTEND'| (including apostrophes) for the
alpar@9 505 marker card, which ends the group.
alpar@9 506
alpar@9 507 The second way is less general but more convenient in some cases. It
alpar@9 508 allows the user declaring integer columns using three additional types
alpar@9 509 of bounds, which are specified in the field 1 of data cards in the
alpar@9 510 BOUNDS section (see Section \ref{secbounds}, page \pageref{secbounds}):
alpar@9 511
alpar@9 512 \begin{tabular}{@{}lp{112.3mm}@{}}
alpar@9 513 \verb|LI| & lower integer. This bound type specifies that the
alpar@9 514 corresponding column (structural variable), whose name is specified in
alpar@9 515 field 3, is of integer kind. In this case an lower bound of the
alpar@9 516 column should be specified in field 4 (like in the case of \verb|LO|
alpar@9 517 bound type). \\
alpar@9 518 \verb|UI| & upper integer. This bound type specifies that the
alpar@9 519 corresponding column (structural variable), whose name is specified in
alpar@9 520 field 3, is of integer kind. In this case an upper bound of the
alpar@9 521 column should be specified in field 4 (like in the case of \verb|UP|
alpar@9 522 bound type). \\
alpar@9 523 \end{tabular}
alpar@9 524
alpar@9 525 \pagebreak
alpar@9 526
alpar@9 527 \begin{tabular}{@{}lp{112.3mm}@{}}
alpar@9 528 \verb|BV| & binary variable. This bound type specifies that the
alpar@9 529 corresponding column (structural variable), whose name is specified in
alpar@9 530 the field 3, is of integer kind, its lower bound is zero, and its upper
alpar@9 531 bound is one (thus, such variable being of integer kind can have only
alpar@9 532 two values zero and one). In this case a numeric value specified in the
alpar@9 533 field 4 is ignored and may be omitted.\\
alpar@9 534 \end{tabular}
alpar@9 535
alpar@9 536 Consider the following example of MIP problem:
alpar@9 537
alpar@9 538 \medskip
alpar@9 539
alpar@9 540 \noindent
alpar@9 541 \hspace{1in} minimize
alpar@9 542 $$Z = 3 x_1 + 7 x_2 - x_3 + x4$$
alpar@9 543 \hspace{1in} subject to linear constraints
alpar@9 544 $$
alpar@9 545 \begin{array}{c}
alpar@9 546 \nonumber r_1 = 2 x_1 - \ \ x_2 + \ \ x_3 - \ \;x_4 \\
alpar@9 547 \nonumber r_2 = \ \;x_1 - \ \;x_2 - 6 x_3 + 4 x_4 \\
alpar@9 548 \nonumber r_3 = 5 x_1 + 3 x_2 \ \ \ \ \ \ \ \ \ + \ \ x_4 \\
alpar@9 549 \end{array}
alpar@9 550 $$
alpar@9 551 \hspace{1in} and bound of variables
alpar@9 552 $$
alpar@9 553 \begin{array}{cccl}
alpar@9 554 \nonumber 1 \leq r_1 < +\infty && 0 \leq x_1 \leq 4 &{\rm(continuous)}\\
alpar@9 555 \nonumber 8 \leq r_2 < +\infty && 2 \leq x_2 \leq 5 &{\rm(integer)} \\
alpar@9 556 \nonumber 5 \leq r_3 < +\infty && 0 \leq x_3 \leq 1 &{\rm(integer)} \\
alpar@9 557 \nonumber && 3 \leq x_4 \leq 8 &{\rm(continuous)}\\
alpar@9 558 \end{array}
alpar@9 559 $$
alpar@9 560
alpar@9 561 The corresponding MPS file may look like the following:
alpar@9 562
alpar@9 563 \begin{verbatim}
alpar@9 564 NAME SAMP1
alpar@9 565 ROWS
alpar@9 566 N Z
alpar@9 567 G R1
alpar@9 568 G R2
alpar@9 569 G R3
alpar@9 570 COLUMNS
alpar@9 571 X1 R1 2.0 R2 1.0
alpar@9 572 X1 R3 5.0 Z 3.0
alpar@9 573 MARK0001 'MARKER' 'INTORG'
alpar@9 574 X2 R1 -1.0 R2 -1.0
alpar@9 575 X2 R3 3.0 Z 7.0
alpar@9 576 X3 R1 1.0 R2 -6.0
alpar@9 577 X3 Z -1.0
alpar@9 578 MARK0002 'MARKER' 'INTEND'
alpar@9 579 X4 R1 -1.0 R2 4.0
alpar@9 580 X4 R3 1.0 Z 1.0
alpar@9 581 RHS
alpar@9 582 RHS1 R1 1.0
alpar@9 583 RHS1 R2 8.0
alpar@9 584 RHS1 R3 5.0
alpar@9 585 BOUNDS
alpar@9 586 UP BND1 X1 4.0
alpar@9 587 LO BND1 X2 2.0
alpar@9 588 UP BND1 X2 5.0
alpar@9 589 UP BND1 X3 1.0
alpar@9 590 LO BND1 X4 3.0
alpar@9 591 UP BND1 X4 8.0
alpar@9 592 ENDATA
alpar@9 593 \end{verbatim}
alpar@9 594
alpar@9 595 The same example may be coded without INTORG/INTEND markers using the
alpar@9 596 bound type UI for the variable $x_2$ and the bound type BV for the
alpar@9 597 variable $x_3$:
alpar@9 598
alpar@9 599 \begin{verbatim}
alpar@9 600 NAME SAMP2
alpar@9 601 ROWS
alpar@9 602 N Z
alpar@9 603 G R1
alpar@9 604 G R2
alpar@9 605 G R3
alpar@9 606 COLUMNS
alpar@9 607 X1 R1 2.0 R2 1.0
alpar@9 608 X1 R3 5.0 Z 3.0
alpar@9 609 X2 R1 -1.0 R2 -1.0
alpar@9 610 X2 R3 3.0 Z 7.0
alpar@9 611 X3 R1 1.0 R2 -6.0
alpar@9 612 X3 Z -1.0
alpar@9 613 X4 R1 -1.0 R2 4.0
alpar@9 614 X4 R3 1.0 Z 1.0
alpar@9 615 RHS
alpar@9 616 RHS1 R1 1.0
alpar@9 617 RHS1 R2 8.0
alpar@9 618 RHS1 R3 5.0
alpar@9 619 BOUNDS
alpar@9 620 UP BND1 X1 4.0
alpar@9 621 LO BND1 X2 2.0
alpar@9 622 UI BND1 X2 5.0
alpar@9 623 BV BND1 X3
alpar@9 624 LO BND1 X4 3.0
alpar@9 625 UP BND1 X4 8.0
alpar@9 626 ENDATA
alpar@9 627 \end{verbatim}
alpar@9 628
alpar@9 629 %\section{Specifying predefined basis}
alpar@9 630 %\label{secbas}
alpar@9 631 %
alpar@9 632 %The MPS format can also be used to specify some predefined basis for an
alpar@9 633 %LP problem, i.e. to specify which rows and columns are basic and which
alpar@9 634 %are non-basic.
alpar@9 635 %
alpar@9 636 %The order of a basis file in the MPS format is:
alpar@9 637 %
alpar@9 638 %$\bullet$ NAME indicator card;
alpar@9 639 %
alpar@9 640 %$\bullet$ data cards (can appear in arbitrary order);
alpar@9 641 %
alpar@9 642 %$\bullet$ ENDATA indicator card.
alpar@9 643 %
alpar@9 644 %Each data card specifies either a pair "basic column---non-basic row"
alpar@9 645 %or a non-basic column. All the data cards have the following format.
alpar@9 646 %
alpar@9 647 %`\verb|XL|' in the field 1 means that a column, whose name is given in
alpar@9 648 %the field 2, is basic, and a row, whose name is given in the field 3,
alpar@9 649 %is non-basic and placed on its lower bound.
alpar@9 650 %
alpar@9 651 %`\verb|XU|' in the field 1 means that a column, whose name is given in
alpar@9 652 %the field 2, is basic, and a row, whose name is given in the field 3,
alpar@9 653 %is non-basic and placed on its upper bound.
alpar@9 654 %
alpar@9 655 %`\verb|LL|' in the field 1 means that a column, whose name is given in
alpar@9 656 %the field 3, is non-basic and placed on its lower bound.
alpar@9 657 %
alpar@9 658 %`\verb|UL|' in the field 1 means that a column, whose name is given in
alpar@9 659 %the field 3, is non-basic and placed on its upper bound.
alpar@9 660 %
alpar@9 661 %The field 2 contains a column name.
alpar@9 662 %
alpar@9 663 %If the indicator given in the field 1 is `\verb|XL|' or `\verb|XU|',
alpar@9 664 %the field 3 contains a row name. Otherwise, if the indicator is
alpar@9 665 %`\verb|LL|' or `\verb|UL|', the field 3 is not used and should be
alpar@9 666 %empty.
alpar@9 667 %
alpar@9 668 %The field 4, 5, and 6 are not used and should be empty.
alpar@9 669 %
alpar@9 670 %A basis file in the MPS format acts like a patch: it doesn't specify
alpar@9 671 %a basis completely, instead that it is just shows in what a given basis
alpar@9 672 %differs from the "standard" basis, where all rows (auxiliary variables)
alpar@9 673 %are assumed to be basic and all columns (structural variables) are
alpar@9 674 %assumed to be non-basic.
alpar@9 675 %
alpar@9 676 %As an example here is a basis file that specifies an optimal basis
alpar@9 677 %for the example LP problem given in Section \ref{secmpsex},
alpar@9 678 %Page \pageref{secmpsex}:
alpar@9 679 %
alpar@9 680 %\pagebreak
alpar@9 681 %
alpar@9 682 %\begin{verbatim}
alpar@9 683 %*000000001111111111222222222233333333334444444444555555555566
alpar@9 684 %*234567890123456789012345678901234567890123456789012345678901
alpar@9 685 %NAME PLAN
alpar@9 686 % XL BIN2 YIELD
alpar@9 687 % XL BIN3 FE
alpar@9 688 % XL BIN4 MN
alpar@9 689 % XL ALUM AL
alpar@9 690 % XL SILICON SI
alpar@9 691 % LL BIN1
alpar@9 692 % LL BIN5
alpar@9 693 %ENDATA
alpar@9 694 %\end{verbatim}
alpar@9 695
alpar@9 696 %* eof *%