lemon-project-template-glpk
comparison deps/glpk/doc/glpk08.tex @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:f07ae970d248 |
---|---|
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 *% |