lemon-project-template-glpk
view deps/glpk/doc/glpk08.tex @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 21:43:29 +0100 |
| parents | |
| children |
line source
1 %* glpk08.tex *%
3 \chapter{MPS Format}
4 \label{champs}
6 \section{Fixed MPS Format}
7 \label{secmps}
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}).
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.
23 Indicator cards determine a kind of succeeding data. Each indicator card
24 has one word in uppercase letters beginning in column 1.
26 Data cards contain problem data. Each data card is divided into six
27 fixed fields:
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}
38 On a particular data card some fields may be optional.
40 Names are used to identify rows, columns, and some vectors (see below).
42 Aligning the indicator code in the field 1 to the left margin is
43 optional.
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.
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.
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.
63 MPS file should contain cards in the following order:
65 $\bullet$ NAME indicator card;
67 $\bullet$ ROWS indicator card;
69 $\bullet$ data cards specifying rows (constraints);
71 $\bullet$ COLUMNS indicator card;
73 $\bullet$ data cards specifying columns (structural variables) and
74 constraint coefficients;
76 $\bullet$ RHS indicator card;
78 $\bullet$ data cards specifying right-hand sides of constraints;
80 $\bullet$ RANGES indicator card;
82 $\bullet$ data cards specifying ranges for double-bounded constraints;
84 $\bullet$ BOUNDS indicator card;
86 $\bullet$ data cards specifying types and bounds of structural
87 variables;
89 $\bullet$ ENDATA indicator card.
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.
95 The sections RHS, RANGES, and BOUNDS are optional and may be omitted.
97 \section{Free MPS Format}
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.
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.
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.
120 Numeric values in fields 4 and 6 are limited to 12 characters and must
121 not contain embedded blanks.
123 Only six fields on each data record are used. Any other fields are
124 ignored.
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.
130 \section{NAME indicator card}
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.
137 \section{ROWS section}
138 \label{secrows}
140 The ROWS section should start with the indicator card, which contains
141 the word \verb|ROWS| in the columns 1---4.
143 Each data card in the ROWS section specifies one row (constraint) of the
144 problem. All these data cards have the following format.
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;$$
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;$$
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;$$
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.
168 The filed 2 specifies a row name (which is considered as the name of
169 the corresponding auxiliary variable).
171 The fields 3, 4, 5, and 6 are not used and should be empty.
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).
177 \section{COLUMNS section}
179 The COLUMNS section should start with the indicator card, which contains
180 the word \verb|COLUMNS| in the columns 1---7.
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.
186 The field 1 is not used and should be empty.
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.
191 The field 3 specifies a row name defined in the ROWS section.
193 The field 4 specifies a numerical value of the constraint coefficient
194 $a_{ij}$, which is placed in the corresponding row and column.
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.
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.
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.
209 \section{RHS section}
211 The RHS section should start with the indicator card, which contains the
212 word \verb|RHS| in the columns 1---3.
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.
218 The field 1 is not used and should be empty.
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.
226 The field 3 specifies a row name defined in the ROWS section.
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.}
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.
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.
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.
248 \section{RANGES section}
250 The RANGES section should start with the indicator card, which contains
251 the word \verb|RANGES| in the columns 1---6.
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.
261 The field 1 is not used and should be empty.
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.
269 The field 3 specifies a row name defined in the ROWS section.
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.
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.
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.
282 For each double-side constraint specified in the RANGES section its
283 lower and upper bounds are determined as follows:
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}
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.
301 \section{BOUNDS section}
302 \label{secbounds}
304 The BOUNDS section should start with the indicator card, which contains
305 the word \verb|BOUNDS| in the columns 1---6.
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.
311 The indicator in the field 1 specifies the bound type:
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}
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.
328 The field 3 specifies a column name defined in the COLUMNS section.
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.
334 The fields 5 and 6 are not used and should be empty.
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).
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:
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}
358 \section{ENDATA indicator card}
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.
364 \section{Specifying objective function}
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}.
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.
375 \section{Example of MPS file}
376 \label{secmpsex}
378 In order to illustrate what the MPS format is, consider the following
379 example of LP problem:
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 $$
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 $$
421 A complete MPS file which specifies data for this example is shown
422 below (the first two comment lines show card positions).
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}
481 \section{MIP features}
483 The MPS format provides two ways for introducing integer variables into
484 the problem.
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.
492 The marker cards have the same format as the data cards (see Section
493 \ref{secmps}, page \pageref{secmps}).
495 The fields 1, 2, and 6 are not used and should be empty.
497 The field 2 should contain a marker name. This name may be arbitrary.
499 The field 3 should contain the word \verb|'MARKER'| (including
500 apostrophes).
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.
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}):
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}
525 \pagebreak
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}
536 Consider the following example of MIP problem:
538 \medskip
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 $$
561 The corresponding MPS file may look like the following:
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}
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$:
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}
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}
696 %* eof *%