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