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 *% |
---|