COIN-OR::LEMON - Graph Library

source: glpk-cmake/doc/glpk08.tex @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 25.9 KB
Line 
1%* glpk08.tex *%
2
3\chapter{MPS Format}
4\label{champs}
5
6\section{Fixed MPS Format}
7\label{secmps}
8
9The MPS format\footnote{The MPS format was developed in 1960's by IBM
10as input format for their mathematical programming system MPS/360.
11Today the MPS format is a most widely used format understood by most
12mathematical programming packages. This appendix describes only the
13features of the MPS format, which are implemented in the GLPK package.}
14is intended for coding LP/MIP problem data. This format assumes the
15formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp},
16page \pageref{seclp}).
17
18{\it MPS file} is a text file, which contains two types of
19cards\footnote{In 1960's MPS file was a deck of 80-column punched cards,
20so the author decided to keep the word ``card'', which may be understood
21as ``line of text file''.}: indicator cards and data cards.
22
23Indicator cards determine a kind of succeeding data. Each indicator card
24has one word in uppercase letters beginning in column 1.
25
26Data cards contain problem data. Each data card is divided into six
27fixed fields:
28
29\begin{center}
30\begin{tabular}{lcccccc}
31& Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\
32\hline
33Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\
34Contents & Code & Name & Name & Number & Name & Number \\
35\end{tabular}
36\end{center}
37
38On a particular data card some fields may be optional.
39
40Names are used to identify rows, columns, and some vectors (see below).
41
42Aligning the indicator code in the field 1 to the left margin is
43optional.
44
45All names specified in the fields 2, 3, and 5 should contain from 1 up
46to 8 arbitrary characters (except control characters). If a name is
47placed in the field 3 or 5, its first character should not be the dollar
48sign `\verb|$|'. If a name contains spaces, the spaces are ignored.
49
50All 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
54characters. If the sign $s$ is omitted, the plus sign is assumed. The
55exponent part is optional. If a number contains spaces, the spaces are
56ignored.
57
58If a card has the asterisk `\verb|*|' in the column 1, this card is
59considered as a comment and ignored. Besides, if the first character in
60the field 3 or 5 is the dollar sign `\verb|$|', all characters from the
61dollar sign to the end of card are considered as a comment and ignored.
62
63MPS 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
74constraint 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
87variables;
88
89$\bullet$ ENDATA indicator card.
90
91{\it Section} is a group of cards consisting of an indicator card and
92data cards succeeding this indicator card. For example, the ROWS section
93consists of the ROWS indicator card and data cards specifying rows.
94
95The 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)
100MPS format described above.\footnote{This format was developed in the
101beginning of 1990's by IBM as an alternative to the standard fixed MPS
102format for Optimization Subroutine Library (OSL).} Note that all
103changes in free MPS format concern only the coding of data while the
104structure of data is the same for both fixed and free versions of the
105MPS format.
106
107In free MPS format indicator and data records\footnote{{\it Record} in
108free MPS format has the same meaning as {\it card} in fixed MPS format.}
109may have arbitrary length not limited to 80 characters. Fields of data
110records have no predefined positions, i.e. the fields may begin in any
111position, except position 1, which must be blank, and must be separated
112from each other by one or more blanks. However, the fields must appear
113in the same order as in fixed MPS format.
114
115Symbolic names in fields 2, 3, and 5 may be longer than 8
116characters\footnote{GLPK allows symbolic names having up to 255
117characters.}
118and must not contain embedded blanks.
119
120Numeric values in fields 4 and 6 are limited to 12 characters and must
121not contain embedded blanks.
122
123Only six fields on each data record are used. Any other fields are
124ignored.
125
126If the first character of any field (not necessarily fields 3 and 5)
127is the dollar sign (\$), all characters from the dollar sign to the end
128of record are considered as a comment and ignored.
129
130\section{NAME indicator card}
131
132The NAME indicator card should be the first card in the MPS file (except
133optional comment cards, which may precede the NAME card). This card
134should contain the word \verb|NAME| in the columns 1---4 and the problem
135name in the field 3. The problem name is optional and may be omitted.
136
137\section{ROWS section}
138\label{secrows}
139
140The ROWS section should start with the indicator card, which contains
141the word \verb|ROWS| in the columns 1---4.
142
143Each data card in the ROWS section specifies one row (constraint) of the
144problem. 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
151to'' 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
156equal 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
162b_i,$$
163where $b_i$ is a right-hand side. Note that each constraint has a
164corresponding implictly defined auxiliary variable ($x_i$ above), whose
165value is a value of the corresponding linear form, therefore row bounds
166can be considered as bounds of such auxiliary variable.
167
168The filed 2 specifies a row name (which is considered as the name of
169the corresponding auxiliary variable).
170
171The fields 3, 4, 5, and 6 are not used and should be empty.
172
173Numerical values of all non-zero right-hand sides $b_i$ should be
174specified in the RHS section (see below). All double-bounded (ranged)
175constraints should be specified in the RANGES section (see below).
176
177\section{COLUMNS section}
178
179The COLUMNS section should start with the indicator card, which contains
180the word \verb|COLUMNS| in the columns 1---7.
181
182Each data card in the COLUMNS section specifies one or two constraint
183coefficients $a_{ij}$ and also introduces names of columns, i.e. names
184of structural variables. All these data cards have the following format.
185
186The field 1 is not used and should be empty.
187
188The field 2 specifies a column name. If this field is empty, the column
189name from the immediately preceeding data card is assumed.
190
191The field 3 specifies a row name defined in the ROWS section.
192
193The field 4 specifies a numerical value of the constraint coefficient
194$a_{ij}$, which is placed in the corresponding row and column.
195
196The fields 5 and 6 are optional. If they are used, they should contain
197a second pair ``row name---constraint coefficient'' for the same column.
198
199Elements of the constraint matrix (i.e. constraint coefficients) should
200be enumerated in the column wise manner: all elements for the current
201column should be specified before elements for the next column. However,
202the order of rows in the COLUMNS section may differ from the order of
203rows in the ROWS section.
204
205Constraint coefficients not specified in the COLUMNS section are
206considered as zeros. Therefore zero coefficients may be omitted,
207although it is allowed to explicitly specify them.
208
209\section{RHS section}
210
211The RHS section should start with the indicator card, which contains the
212word \verb|RHS| in the columns 1---3.
213
214Each 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
216data cards have the following format.
217
218The field 1 is not used and should be empty.
219
220The field 2 specifies a name of the right-hand side (RHS)
221vector\footnote{This feature allows the user to specify several RHS
222vectors in the same MPS file. However, before solving the problem a
223particular RHS vector should be chosen.}. If this field is empty, the
224RHS vector name from the immediately preceeding data card is assumed.
225
226The field 3 specifies a row name defined in the ROWS section.
227
228The field 4 specifies a right-hand side $b_i$ for the row, whose name is
229specified in the field 3. Depending on the row type $b_i$ is a lower
230bound (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|
232type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as
233a constant term of the corresponding linear form. Should note, however,
234this convention is non-standard.}
235
236The fields 5 and 6 are optional. If they are used, they should contain
237a second pair ``row name---right-hand side'' for the same RHS vector.
238
239All right-hand sides for the current RHS vector should be specified
240before right-hand sides for the next RHS vector. However, the order of
241rows in the RHS section may differ from the order of rows in the ROWS
242section.
243
244Right-hand sides not specified in the RHS section are considered as
245zeros. Therefore zero right-hand sides may be omitted, although it is
246allowed to explicitly specify them.
247
248\section{RANGES section}
249
250The RANGES section should start with the indicator card, which contains
251the word \verb|RANGES| in the columns 1---6.
252
253Each data card in the RANGES section specifies one or two ranges for
254double-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,$$
258where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data
259cards have the following format.
260
261The field 1 is not used and should be empty.
262
263The field 2 specifies a name of the range vector\footnote{This feature
264allows the user to specify several range vectors in the same MPS file.
265However, before solving the problem a particular range vector should be
266chosen.}. If this field is empty, the range vector name from the
267immediately preceeding data card is assumed.
268
269The field 3 specifies a row name defined in the ROWS section.
270
271The field 4 specifies a range value $r_i$ (see the table below) for the
272row, whose name is specified in the field 3.
273
274The fields 5 and 6 are optional. If they are used, they should contain
275a second pair ``row name---range value'' for the same range vector.
276
277All range values for the current range vector should be specified before
278range values for the next range vector. However, the order of rows in
279the RANGES section may differ from the order of rows in the ROWS
280section.
281
282For each double-side constraint specified in the RANGES section its
283lower and upper bounds are determined as follows:
284
285\begin{center}
286\begin{tabular}{cccc}
287Row 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
297where $b_i$ is a right-hand side specified in the RHS section (if $b_i$
298is not specified, it is considered as zero), $r_i$ is a range value
299specified in the RANGES section.
300
301\section{BOUNDS section}
302\label{secbounds}
303
304The BOUNDS section should start with the indicator card, which contains
305the word \verb|BOUNDS| in the columns 1---6.
306
307Each data card in the BOUNDS section specifies one (lower or upper)
308bound for one structural variable (column). All these data cards have
309the following format.
310
311The 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
322The field 2 specifies a name of the bound vector\footnote{This feature
323allows the user to specify several bound vectors in the same MPS file.
324However, before solving the problem a particular bound vector should be
325chosen.}. If this field is empty, the bound vector name from the
326immediately preceeding data card is assumed.
327
328The field 3 specifies a column name defined in the COLUMNS section.
329
330The field 4 specifies a bound value. If the bound type in the field 1
331differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field
3324 is ignored and may be omitted.
333
334The fields 5 and 6 are not used and should be empty.
335
336All bound values for the current bound vector should be specified before
337bound values for the next bound vector. However, the order of columns in
338the BOUNDS section may differ from the order of columns in the COLUMNS
339section. Specification of a lower bound should precede specification of
340an upper bound for the same column (if both the lower and upper bounds
341are explicitly specified).
342
343By default, all columns (structural variables) are non-negative, i.e.
344have 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
346following way, where $s_j$ is a corresponding bound value explicitly
347specified 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
360The ENDATA indicator card should be the last card of MPS file (except
361optional comment cards, which may follow the ENDATA card). This card
362should contain the word \verb|ENDATA| in the columns 1---6.
363
364\section{Specifying objective function}
365
366It is impossible to explicitly specify the objective function and
367optimization direction in the MPS file. However, the following implicit
368rule is used by default: the first row of \verb|N| type is considered
369as a row of the objective function (i.e. the objective function is the
370corresponding auxiliary variable), which should be {\it minimized}.
371
372GLPK also allows specifying a constant term of the objective function
373as a right-hand side of the corresponding row in the RHS section.
374
375\section{Example of MPS file}
376\label{secmpsex}
377
378In order to illustrate what the MPS format is, consider the following
379example of LP problem:
380
381\medskip
382\noindent minimize
383$$
384value = .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@{}}
391yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 +
392         \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al +
393         \ \ \ \ \;si \\
394FE    &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5
395         + .01\ al + .03\ si \\
396CU    &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5
397         + .01\ al \\
398MN    &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5
399         \\
400MG    &= .02\ bin_1 + .03\ bin_2
401\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\
402AL    &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5
403         + .97\ al \\
404SI    &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5
405         + .01\ al + .97\ si \\
406\end{array}
407$$
408and 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\\
4161500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\
417250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\
418\end{array}
419$$
420
421A complete MPS file which specifies data for this example is shown
422below (the first two comment lines show card positions).
423
424\begin{verbatim}
425*000000001111111111222222222233333333334444444444555555555566
426*234567890123456789012345678901234567890123456789012345678901
427NAME          PLAN
428ROWS
429 N  VALUE
430 E  YIELD
431 L  FE
432 L  CU
433 L  MN
434 L  MG
435 G  AL
436 L  SI
437COLUMNS
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
463RHS
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
468RANGES
469    RNG1      SI            50.00000
470BOUNDS
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
478ENDATA
479\end{verbatim}
480
481\section{MIP features}
482
483The MPS format provides two ways for introducing integer variables into
484the problem.
485
486The first way is most general and based on using special marker cards
487INTORG and INTEND. These marker cards are placed in the COLUMNS section.
488The 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
490file may contain arbitrary number of the marker cards.
491
492The marker cards have the same format as the data cards (see Section
493\ref{secmps}, page \pageref{secmps}).
494
495The fields 1, 2, and 6 are not used and should be empty.
496
497The field 2 should contain a marker name. This name may be arbitrary.
498
499The field 3 should contain the word \verb|'MARKER'| (including
500apostrophes).
501
502The field 5 should contain either the word \verb|'INTORG'| (including
503apostrophes) for the marker card, which begins a group of integer
504columns, or the word \verb|'INTEND'| (including apostrophes) for the
505marker card, which ends the group.
506
507The second way is less general but more convenient in some cases. It
508allows the user declaring integer columns using three additional types
509of bounds, which are specified in the field 1 of data cards in the
510BOUNDS 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
514corresponding column (structural variable), whose name is specified in
515field 3, is of integer kind. In this case an lower bound of the
516column should be specified in field 4 (like in the case of \verb|LO|
517bound type). \\
518\verb|UI| & upper integer. This bound type specifies that the
519corresponding column (structural variable), whose name is specified in
520field 3, is of integer kind. In this case an upper bound of the
521column should be specified in field 4 (like in the case of \verb|UP|
522bound 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
529corresponding column (structural variable), whose name is specified in
530the field 3, is of integer kind, its lower bound is zero, and its upper
531bound is one (thus, such variable being of integer kind can have only
532two values zero and one). In this case a numeric value specified in the
533field 4 is ignored and may be omitted.\\
534\end{tabular}
535
536Consider 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
561The corresponding MPS file may look like the following:
562
563\begin{verbatim}
564NAME          SAMP1
565ROWS
566 N  Z
567 G  R1
568 G  R2
569 G  R3
570COLUMNS
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
581RHS
582    RHS1      R1                1.0
583    RHS1      R2                8.0
584    RHS1      R3                5.0
585BOUNDS
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
592ENDATA
593\end{verbatim}
594
595The same example may be coded without INTORG/INTEND markers using the
596bound type UI for the variable $x_2$ and the bound type BV for the
597variable $x_3$:
598
599\begin{verbatim}
600NAME          SAMP2
601ROWS
602 N  Z
603 G  R1
604 G  R2
605 G  R3
606COLUMNS
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
615RHS
616    RHS1      R1                1.0
617    RHS1      R2                8.0
618    RHS1      R3                5.0
619BOUNDS
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
626ENDATA
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 *%
Note: See TracBrowser for help on using the repository browser.