alpar@1: %* glpk08.tex *% alpar@1: alpar@1: \chapter{MPS Format} alpar@1: \label{champs} alpar@1: alpar@1: \section{Fixed MPS Format} alpar@1: \label{secmps} alpar@1: alpar@1: The MPS format\footnote{The MPS format was developed in 1960's by IBM alpar@1: as input format for their mathematical programming system MPS/360. alpar@1: Today the MPS format is a most widely used format understood by most alpar@1: mathematical programming packages. This appendix describes only the alpar@1: features of the MPS format, which are implemented in the GLPK package.} alpar@1: is intended for coding LP/MIP problem data. This format assumes the alpar@1: formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp}, alpar@1: page \pageref{seclp}). alpar@1: alpar@1: {\it MPS file} is a text file, which contains two types of alpar@1: cards\footnote{In 1960's MPS file was a deck of 80-column punched cards, alpar@1: so the author decided to keep the word ``card'', which may be understood alpar@1: as ``line of text file''.}: indicator cards and data cards. alpar@1: alpar@1: Indicator cards determine a kind of succeeding data. Each indicator card alpar@1: has one word in uppercase letters beginning in column 1. alpar@1: alpar@1: Data cards contain problem data. Each data card is divided into six alpar@1: fixed fields: alpar@1: alpar@1: \begin{center} alpar@1: \begin{tabular}{lcccccc} alpar@1: & Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\ alpar@1: \hline alpar@1: Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\ alpar@1: Contents & Code & Name & Name & Number & Name & Number \\ alpar@1: \end{tabular} alpar@1: \end{center} alpar@1: alpar@1: On a particular data card some fields may be optional. alpar@1: alpar@1: Names are used to identify rows, columns, and some vectors (see below). alpar@1: alpar@1: Aligning the indicator code in the field 1 to the left margin is alpar@1: optional. alpar@1: alpar@1: All names specified in the fields 2, 3, and 5 should contain from 1 up alpar@1: to 8 arbitrary characters (except control characters). If a name is alpar@1: placed in the field 3 or 5, its first character should not be the dollar alpar@1: sign `\verb|$|'. If a name contains spaces, the spaces are ignored. alpar@1: alpar@1: All numerical values in the fields 4 and 6 should be coded in the form alpar@1: $sxx$\verb|E|$syy$, where $s$ is the plus `\verb|+|' or the minus alpar@1: `\verb|-|' sign, $xx$ is a real number with optional decimal point, alpar@1: $yy$ is an integer decimal exponent. Any number should contain up to 12 alpar@1: characters. If the sign $s$ is omitted, the plus sign is assumed. The alpar@1: exponent part is optional. If a number contains spaces, the spaces are alpar@1: ignored. alpar@1: alpar@1: If a card has the asterisk `\verb|*|' in the column 1, this card is alpar@1: considered as a comment and ignored. Besides, if the first character in alpar@1: the field 3 or 5 is the dollar sign `\verb|$|', all characters from the alpar@1: dollar sign to the end of card are considered as a comment and ignored. alpar@1: alpar@1: MPS file should contain cards in the following order: alpar@1: alpar@1: $\bullet$ NAME indicator card; alpar@1: alpar@1: $\bullet$ ROWS indicator card; alpar@1: alpar@1: $\bullet$ data cards specifying rows (constraints); alpar@1: alpar@1: $\bullet$ COLUMNS indicator card; alpar@1: alpar@1: $\bullet$ data cards specifying columns (structural variables) and alpar@1: constraint coefficients; alpar@1: alpar@1: $\bullet$ RHS indicator card; alpar@1: alpar@1: $\bullet$ data cards specifying right-hand sides of constraints; alpar@1: alpar@1: $\bullet$ RANGES indicator card; alpar@1: alpar@1: $\bullet$ data cards specifying ranges for double-bounded constraints; alpar@1: alpar@1: $\bullet$ BOUNDS indicator card; alpar@1: alpar@1: $\bullet$ data cards specifying types and bounds of structural alpar@1: variables; alpar@1: alpar@1: $\bullet$ ENDATA indicator card. alpar@1: alpar@1: {\it Section} is a group of cards consisting of an indicator card and alpar@1: data cards succeeding this indicator card. For example, the ROWS section alpar@1: consists of the ROWS indicator card and data cards specifying rows. alpar@1: alpar@1: The sections RHS, RANGES, and BOUNDS are optional and may be omitted. alpar@1: alpar@1: \section{Free MPS Format} alpar@1: alpar@1: {\it Free MPS format} is an improved version of the standard (fixed) alpar@1: MPS format described above.\footnote{This format was developed in the alpar@1: beginning of 1990's by IBM as an alternative to the standard fixed MPS alpar@1: format for Optimization Subroutine Library (OSL).} Note that all alpar@1: changes in free MPS format concern only the coding of data while the alpar@1: structure of data is the same for both fixed and free versions of the alpar@1: MPS format. alpar@1: alpar@1: In free MPS format indicator and data records\footnote{{\it Record} in alpar@1: free MPS format has the same meaning as {\it card} in fixed MPS format.} alpar@1: may have arbitrary length not limited to 80 characters. Fields of data alpar@1: records have no predefined positions, i.e. the fields may begin in any alpar@1: position, except position 1, which must be blank, and must be separated alpar@1: from each other by one or more blanks. However, the fields must appear alpar@1: in the same order as in fixed MPS format. alpar@1: alpar@1: Symbolic names in fields 2, 3, and 5 may be longer than 8 alpar@1: characters\footnote{GLPK allows symbolic names having up to 255 alpar@1: characters.} alpar@1: and must not contain embedded blanks. alpar@1: alpar@1: Numeric values in fields 4 and 6 are limited to 12 characters and must alpar@1: not contain embedded blanks. alpar@1: alpar@1: Only six fields on each data record are used. Any other fields are alpar@1: ignored. alpar@1: alpar@1: If the first character of any field (not necessarily fields 3 and 5) alpar@1: is the dollar sign (\$), all characters from the dollar sign to the end alpar@1: of record are considered as a comment and ignored. alpar@1: alpar@1: \section{NAME indicator card} alpar@1: alpar@1: The NAME indicator card should be the first card in the MPS file (except alpar@1: optional comment cards, which may precede the NAME card). This card alpar@1: should contain the word \verb|NAME| in the columns 1---4 and the problem alpar@1: name in the field 3. The problem name is optional and may be omitted. alpar@1: alpar@1: \section{ROWS section} alpar@1: \label{secrows} alpar@1: alpar@1: The ROWS section should start with the indicator card, which contains alpar@1: the word \verb|ROWS| in the columns 1---4. alpar@1: alpar@1: Each data card in the ROWS section specifies one row (constraint) of the alpar@1: problem. All these data cards have the following format. alpar@1: alpar@1: `\verb|N|' in the field 1 means that the row is free (unbounded): alpar@1: $$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} alpar@1: < +\infty;$$ alpar@1: alpar@1: `\verb|L|' in the field 1 means that the row is of ``less than or equal alpar@1: to'' type: alpar@1: $$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} alpar@1: \leq b_i;$$ alpar@1: alpar@1: `\verb|G|' in the field 1 means that the row is of ``greater than or alpar@1: equal to'' type: alpar@1: $$b_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} alpar@1: < +\infty;$$ alpar@1: alpar@1: `\verb|E|' in the field 1 means that the row is of ``equal to'' type: alpar@1: $$x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} \leq alpar@1: b_i,$$ alpar@1: where $b_i$ is a right-hand side. Note that each constraint has a alpar@1: corresponding implictly defined auxiliary variable ($x_i$ above), whose alpar@1: value is a value of the corresponding linear form, therefore row bounds alpar@1: can be considered as bounds of such auxiliary variable. alpar@1: alpar@1: The filed 2 specifies a row name (which is considered as the name of alpar@1: the corresponding auxiliary variable). alpar@1: alpar@1: The fields 3, 4, 5, and 6 are not used and should be empty. alpar@1: alpar@1: Numerical values of all non-zero right-hand sides $b_i$ should be alpar@1: specified in the RHS section (see below). All double-bounded (ranged) alpar@1: constraints should be specified in the RANGES section (see below). alpar@1: alpar@1: \section{COLUMNS section} alpar@1: alpar@1: The COLUMNS section should start with the indicator card, which contains alpar@1: the word \verb|COLUMNS| in the columns 1---7. alpar@1: alpar@1: Each data card in the COLUMNS section specifies one or two constraint alpar@1: coefficients $a_{ij}$ and also introduces names of columns, i.e. names alpar@1: of structural variables. All these data cards have the following format. alpar@1: alpar@1: The field 1 is not used and should be empty. alpar@1: alpar@1: The field 2 specifies a column name. If this field is empty, the column alpar@1: name from the immediately preceeding data card is assumed. alpar@1: alpar@1: The field 3 specifies a row name defined in the ROWS section. alpar@1: alpar@1: The field 4 specifies a numerical value of the constraint coefficient alpar@1: $a_{ij}$, which is placed in the corresponding row and column. alpar@1: alpar@1: The fields 5 and 6 are optional. If they are used, they should contain alpar@1: a second pair ``row name---constraint coefficient'' for the same column. alpar@1: alpar@1: Elements of the constraint matrix (i.e. constraint coefficients) should alpar@1: be enumerated in the column wise manner: all elements for the current alpar@1: column should be specified before elements for the next column. However, alpar@1: the order of rows in the COLUMNS section may differ from the order of alpar@1: rows in the ROWS section. alpar@1: alpar@1: Constraint coefficients not specified in the COLUMNS section are alpar@1: considered as zeros. Therefore zero coefficients may be omitted, alpar@1: although it is allowed to explicitly specify them. alpar@1: alpar@1: \section{RHS section} alpar@1: alpar@1: The RHS section should start with the indicator card, which contains the alpar@1: word \verb|RHS| in the columns 1---3. alpar@1: alpar@1: Each data card in the RHS section specifies one or two right-hand sides alpar@1: $b_i$ (see Section \ref{secrows}, page \pageref{secrows}). All these alpar@1: data cards have the following format. alpar@1: alpar@1: The field 1 is not used and should be empty. alpar@1: alpar@1: The field 2 specifies a name of the right-hand side (RHS) alpar@1: vector\footnote{This feature allows the user to specify several RHS alpar@1: vectors in the same MPS file. However, before solving the problem a alpar@1: particular RHS vector should be chosen.}. If this field is empty, the alpar@1: RHS vector name from the immediately preceeding data card is assumed. alpar@1: alpar@1: The field 3 specifies a row name defined in the ROWS section. alpar@1: alpar@1: The field 4 specifies a right-hand side $b_i$ for the row, whose name is alpar@1: specified in the field 3. Depending on the row type $b_i$ is a lower alpar@1: bound (for the row of \verb|G| type), an upper bound (for the row of alpar@1: \verb|L| type), or a fixed value (for the row of \verb|E| alpar@1: type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as alpar@1: a constant term of the corresponding linear form. Should note, however, alpar@1: this convention is non-standard.} alpar@1: alpar@1: The fields 5 and 6 are optional. If they are used, they should contain alpar@1: a second pair ``row name---right-hand side'' for the same RHS vector. alpar@1: alpar@1: All right-hand sides for the current RHS vector should be specified alpar@1: before right-hand sides for the next RHS vector. However, the order of alpar@1: rows in the RHS section may differ from the order of rows in the ROWS alpar@1: section. alpar@1: alpar@1: Right-hand sides not specified in the RHS section are considered as alpar@1: zeros. Therefore zero right-hand sides may be omitted, although it is alpar@1: allowed to explicitly specify them. alpar@1: alpar@1: \section{RANGES section} alpar@1: alpar@1: The RANGES section should start with the indicator card, which contains alpar@1: the word \verb|RANGES| in the columns 1---6. alpar@1: alpar@1: Each data card in the RANGES section specifies one or two ranges for alpar@1: double-side constraints, i.e. for constraints that are of the types alpar@1: \verb|L| and \verb|G| at the same time: alpar@1: $$l_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} alpar@1: \leq u_i,$$ alpar@1: where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data alpar@1: cards have the following format. alpar@1: alpar@1: The field 1 is not used and should be empty. alpar@1: alpar@1: The field 2 specifies a name of the range vector\footnote{This feature alpar@1: allows the user to specify several range vectors in the same MPS file. alpar@1: However, before solving the problem a particular range vector should be alpar@1: chosen.}. If this field is empty, the range vector name from the alpar@1: immediately preceeding data card is assumed. alpar@1: alpar@1: The field 3 specifies a row name defined in the ROWS section. alpar@1: alpar@1: The field 4 specifies a range value $r_i$ (see the table below) for the alpar@1: row, whose name is specified in the field 3. alpar@1: alpar@1: The fields 5 and 6 are optional. If they are used, they should contain alpar@1: a second pair ``row name---range value'' for the same range vector. alpar@1: alpar@1: All range values for the current range vector should be specified before alpar@1: range values for the next range vector. However, the order of rows in alpar@1: the RANGES section may differ from the order of rows in the ROWS alpar@1: section. alpar@1: alpar@1: For each double-side constraint specified in the RANGES section its alpar@1: lower and upper bounds are determined as follows: alpar@1: alpar@1: \begin{center} alpar@1: \begin{tabular}{cccc} alpar@1: Row type & Sign of $r_i$ & Lower bound & Upper bound \\ alpar@1: \hline alpar@1: {\tt G} & $+$ or $-$ & $b_i$ & $b_i + |r_i|$ \\ alpar@1: {\tt L} & $+$ or $-$ & $b_i - |r_i|$ & $b_i$ \\ alpar@1: {\tt E} & $+$ & $b_i$ & $b_i + |r_i|$ \\ alpar@1: {\tt E} & $-$ & $b_i - |r_i|$ & $b_i$ \\ alpar@1: \end{tabular} alpar@1: \end{center} alpar@1: alpar@1: \noindent alpar@1: where $b_i$ is a right-hand side specified in the RHS section (if $b_i$ alpar@1: is not specified, it is considered as zero), $r_i$ is a range value alpar@1: specified in the RANGES section. alpar@1: alpar@1: \section{BOUNDS section} alpar@1: \label{secbounds} alpar@1: alpar@1: The BOUNDS section should start with the indicator card, which contains alpar@1: the word \verb|BOUNDS| in the columns 1---6. alpar@1: alpar@1: Each data card in the BOUNDS section specifies one (lower or upper) alpar@1: bound for one structural variable (column). All these data cards have alpar@1: the following format. alpar@1: alpar@1: The indicator in the field 1 specifies the bound type: alpar@1: alpar@1: \begin{tabular}{@{}ll} alpar@1: \verb|LO| & lower bound; \\ alpar@1: \verb|UP| & upper bound; \\ alpar@1: \verb|FX| & fixed variable (lower and upper bounds are equal); \\ alpar@1: \verb|FR| & free variable (no bounds); \\ alpar@1: \verb|MI| & no lower bound (lower bound is ``minus infinity''); \\ alpar@1: \verb|PL| & no upper bound (upper bound is ``plus infinity''); \\ alpar@1: \end{tabular} alpar@1: alpar@1: The field 2 specifies a name of the bound vector\footnote{This feature alpar@1: allows the user to specify several bound vectors in the same MPS file. alpar@1: However, before solving the problem a particular bound vector should be alpar@1: chosen.}. If this field is empty, the bound vector name from the alpar@1: immediately preceeding data card is assumed. alpar@1: alpar@1: The field 3 specifies a column name defined in the COLUMNS section. alpar@1: alpar@1: The field 4 specifies a bound value. If the bound type in the field 1 alpar@1: differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field alpar@1: 4 is ignored and may be omitted. alpar@1: alpar@1: The fields 5 and 6 are not used and should be empty. alpar@1: alpar@1: All bound values for the current bound vector should be specified before alpar@1: bound values for the next bound vector. However, the order of columns in alpar@1: the BOUNDS section may differ from the order of columns in the COLUMNS alpar@1: section. Specification of a lower bound should precede specification of alpar@1: an upper bound for the same column (if both the lower and upper bounds alpar@1: are explicitly specified). alpar@1: alpar@1: By default, all columns (structural variables) are non-negative, i.e. alpar@1: have zero lower bound and no upper bound. Lower ($l_j$) and upper alpar@1: ($u_j$) bounds of some column (structural variable $x_j$) are set in the alpar@1: following way, where $s_j$ is a corresponding bound value explicitly alpar@1: specified in the BOUNDS section: alpar@1: alpar@1: \begin{tabular}{@{}ll} alpar@1: \verb|LO| & sets $l_j$ to $s_j$; \\ alpar@1: \verb|UP| & sets $u_j$ to $s_j$; \\ alpar@1: \verb|FX| & sets both $l_j$ and $u_j$ to $s_j$; \\ alpar@1: \verb|FR| & sets $l_j$ to $-\infty$ and $u_j$ to $+\infty$; \\ alpar@1: \verb|MI| & sets $l_j$ to $-\infty$; \\ alpar@1: \verb|PL| & sets $u_j$ to $+\infty$. \\ alpar@1: \end{tabular} alpar@1: alpar@1: \section{ENDATA indicator card} alpar@1: alpar@1: The ENDATA indicator card should be the last card of MPS file (except alpar@1: optional comment cards, which may follow the ENDATA card). This card alpar@1: should contain the word \verb|ENDATA| in the columns 1---6. alpar@1: alpar@1: \section{Specifying objective function} alpar@1: alpar@1: It is impossible to explicitly specify the objective function and alpar@1: optimization direction in the MPS file. However, the following implicit alpar@1: rule is used by default: the first row of \verb|N| type is considered alpar@1: as a row of the objective function (i.e. the objective function is the alpar@1: corresponding auxiliary variable), which should be {\it minimized}. alpar@1: alpar@1: GLPK also allows specifying a constant term of the objective function alpar@1: as a right-hand side of the corresponding row in the RHS section. alpar@1: alpar@1: \section{Example of MPS file} alpar@1: \label{secmpsex} alpar@1: alpar@1: In order to illustrate what the MPS format is, consider the following alpar@1: example of LP problem: alpar@1: alpar@1: \medskip alpar@1: \noindent minimize alpar@1: $$ alpar@1: value = .03\ bin_1 + .08\ bin_2 + .17\ bin_3 + .12\ bin_4 + .15\ bin_5 alpar@1: + .21\ al + .38\ si alpar@1: $$ alpar@1: alpar@1: \noindent subject to linear constraints alpar@1: $$ alpar@1: \begin{array}{@{}l@{\:}l@{}} alpar@1: yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 + alpar@1: \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al + alpar@1: \ \ \ \ \;si \\ alpar@1: FE &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5 alpar@1: + .01\ al + .03\ si \\ alpar@1: CU &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5 alpar@1: + .01\ al \\ alpar@1: MN &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5 alpar@1: \\ alpar@1: MG &= .02\ bin_1 + .03\ bin_2 alpar@1: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\ alpar@1: AL &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5 alpar@1: + .97\ al \\ alpar@1: SI &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5 alpar@1: + .01\ al + .97\ si \\ alpar@1: \end{array} alpar@1: $$ alpar@1: and bounds of (auxiliary and structural) variables alpar@1: $$ alpar@1: \begin{array}{r@{\ }l@{\ }l@{\ }l@{\ }rcr@{\ }l@{\ }l@{\ }l@{\ }r} alpar@1: &&yield&=&2000&&0&\leq&bin_1&\leq&200\\ alpar@1: -\infty&<&FE&\leq&60&&0&\leq&bin_2&\leq&2500\\ alpar@1: -\infty&<&CU&\leq&100&&400&\leq&bin_3&\leq&800\\ alpar@1: -\infty&<&MN&\leq&40&&100&\leq&bin_4&\leq&700\\ alpar@1: -\infty&<&MG&\leq&30&&0&\leq&bin_5&\leq&1500\\ alpar@1: 1500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\ alpar@1: 250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\ alpar@1: \end{array} alpar@1: $$ alpar@1: alpar@1: A complete MPS file which specifies data for this example is shown alpar@1: below (the first two comment lines show card positions). alpar@1: alpar@1: \begin{verbatim} alpar@1: *000000001111111111222222222233333333334444444444555555555566 alpar@1: *234567890123456789012345678901234567890123456789012345678901 alpar@1: NAME PLAN alpar@1: ROWS alpar@1: N VALUE alpar@1: E YIELD alpar@1: L FE alpar@1: L CU alpar@1: L MN alpar@1: L MG alpar@1: G AL alpar@1: L SI alpar@1: COLUMNS alpar@1: BIN1 VALUE .03000 YIELD 1.00000 alpar@1: FE .15000 CU .03000 alpar@1: MN .02000 MG .02000 alpar@1: AL .70000 SI .02000 alpar@1: BIN2 VALUE .08000 YIELD 1.00000 alpar@1: FE .04000 CU .05000 alpar@1: MN .04000 MG .03000 alpar@1: AL .75000 SI .06000 alpar@1: BIN3 VALUE .17000 YIELD 1.00000 alpar@1: FE .02000 CU .08000 alpar@1: MN .01000 AL .80000 alpar@1: SI .08000 alpar@1: BIN4 VALUE .12000 YIELD 1.00000 alpar@1: FE .04000 CU .02000 alpar@1: MN .02000 AL .75000 alpar@1: SI .12000 alpar@1: BIN5 VALUE .15000 YIELD 1.00000 alpar@1: FE .02000 CU .06000 alpar@1: MN .02000 MG .01000 alpar@1: AL .80000 SI .02000 alpar@1: ALUM VALUE .21000 YIELD 1.00000 alpar@1: FE .01000 CU .01000 alpar@1: AL .97000 SI .01000 alpar@1: SILICON VALUE .38000 YIELD 1.00000 alpar@1: FE .03000 SI .97000 alpar@1: RHS alpar@1: RHS1 YIELD 2000.00000 FE 60.00000 alpar@1: CU 100.00000 MN 40.00000 alpar@1: SI 300.00000 alpar@1: MG 30.00000 AL 1500.00000 alpar@1: RANGES alpar@1: RNG1 SI 50.00000 alpar@1: BOUNDS alpar@1: UP BND1 BIN1 200.00000 alpar@1: UP BIN2 2500.00000 alpar@1: LO BIN3 400.00000 alpar@1: UP BIN3 800.00000 alpar@1: LO BIN4 100.00000 alpar@1: UP BIN4 700.00000 alpar@1: UP BIN5 1500.00000 alpar@1: ENDATA alpar@1: \end{verbatim} alpar@1: alpar@1: \section{MIP features} alpar@1: alpar@1: The MPS format provides two ways for introducing integer variables into alpar@1: the problem. alpar@1: alpar@1: The first way is most general and based on using special marker cards alpar@1: INTORG and INTEND. These marker cards are placed in the COLUMNS section. alpar@1: The INTORG card indicates the start of a group of integer variables alpar@1: (columns), and the card INTEND indicates the end of the group. The MPS alpar@1: file may contain arbitrary number of the marker cards. alpar@1: alpar@1: The marker cards have the same format as the data cards (see Section alpar@1: \ref{secmps}, page \pageref{secmps}). alpar@1: alpar@1: The fields 1, 2, and 6 are not used and should be empty. alpar@1: alpar@1: The field 2 should contain a marker name. This name may be arbitrary. alpar@1: alpar@1: The field 3 should contain the word \verb|'MARKER'| (including alpar@1: apostrophes). alpar@1: alpar@1: The field 5 should contain either the word \verb|'INTORG'| (including alpar@1: apostrophes) for the marker card, which begins a group of integer alpar@1: columns, or the word \verb|'INTEND'| (including apostrophes) for the alpar@1: marker card, which ends the group. alpar@1: alpar@1: The second way is less general but more convenient in some cases. It alpar@1: allows the user declaring integer columns using three additional types alpar@1: of bounds, which are specified in the field 1 of data cards in the alpar@1: BOUNDS section (see Section \ref{secbounds}, page \pageref{secbounds}): alpar@1: alpar@1: \begin{tabular}{@{}lp{112.3mm}@{}} alpar@1: \verb|LI| & lower integer. This bound type specifies that the alpar@1: corresponding column (structural variable), whose name is specified in alpar@1: field 3, is of integer kind. In this case an lower bound of the alpar@1: column should be specified in field 4 (like in the case of \verb|LO| alpar@1: bound type). \\ alpar@1: \verb|UI| & upper integer. This bound type specifies that the alpar@1: corresponding column (structural variable), whose name is specified in alpar@1: field 3, is of integer kind. In this case an upper bound of the alpar@1: column should be specified in field 4 (like in the case of \verb|UP| alpar@1: bound type). \\ alpar@1: \end{tabular} alpar@1: alpar@1: \pagebreak alpar@1: alpar@1: \begin{tabular}{@{}lp{112.3mm}@{}} alpar@1: \verb|BV| & binary variable. This bound type specifies that the alpar@1: corresponding column (structural variable), whose name is specified in alpar@1: the field 3, is of integer kind, its lower bound is zero, and its upper alpar@1: bound is one (thus, such variable being of integer kind can have only alpar@1: two values zero and one). In this case a numeric value specified in the alpar@1: field 4 is ignored and may be omitted.\\ alpar@1: \end{tabular} alpar@1: alpar@1: Consider the following example of MIP problem: alpar@1: alpar@1: \medskip alpar@1: alpar@1: \noindent alpar@1: \hspace{1in} minimize alpar@1: $$Z = 3 x_1 + 7 x_2 - x_3 + x4$$ alpar@1: \hspace{1in} subject to linear constraints alpar@1: $$ alpar@1: \begin{array}{c} alpar@1: \nonumber r_1 = 2 x_1 - \ \ x_2 + \ \ x_3 - \ \;x_4 \\ alpar@1: \nonumber r_2 = \ \;x_1 - \ \;x_2 - 6 x_3 + 4 x_4 \\ alpar@1: \nonumber r_3 = 5 x_1 + 3 x_2 \ \ \ \ \ \ \ \ \ + \ \ x_4 \\ alpar@1: \end{array} alpar@1: $$ alpar@1: \hspace{1in} and bound of variables alpar@1: $$ alpar@1: \begin{array}{cccl} alpar@1: \nonumber 1 \leq r_1 < +\infty && 0 \leq x_1 \leq 4 &{\rm(continuous)}\\ alpar@1: \nonumber 8 \leq r_2 < +\infty && 2 \leq x_2 \leq 5 &{\rm(integer)} \\ alpar@1: \nonumber 5 \leq r_3 < +\infty && 0 \leq x_3 \leq 1 &{\rm(integer)} \\ alpar@1: \nonumber && 3 \leq x_4 \leq 8 &{\rm(continuous)}\\ alpar@1: \end{array} alpar@1: $$ alpar@1: alpar@1: The corresponding MPS file may look like the following: alpar@1: alpar@1: \begin{verbatim} alpar@1: NAME SAMP1 alpar@1: ROWS alpar@1: N Z alpar@1: G R1 alpar@1: G R2 alpar@1: G R3 alpar@1: COLUMNS alpar@1: X1 R1 2.0 R2 1.0 alpar@1: X1 R3 5.0 Z 3.0 alpar@1: MARK0001 'MARKER' 'INTORG' alpar@1: X2 R1 -1.0 R2 -1.0 alpar@1: X2 R3 3.0 Z 7.0 alpar@1: X3 R1 1.0 R2 -6.0 alpar@1: X3 Z -1.0 alpar@1: MARK0002 'MARKER' 'INTEND' alpar@1: X4 R1 -1.0 R2 4.0 alpar@1: X4 R3 1.0 Z 1.0 alpar@1: RHS alpar@1: RHS1 R1 1.0 alpar@1: RHS1 R2 8.0 alpar@1: RHS1 R3 5.0 alpar@1: BOUNDS alpar@1: UP BND1 X1 4.0 alpar@1: LO BND1 X2 2.0 alpar@1: UP BND1 X2 5.0 alpar@1: UP BND1 X3 1.0 alpar@1: LO BND1 X4 3.0 alpar@1: UP BND1 X4 8.0 alpar@1: ENDATA alpar@1: \end{verbatim} alpar@1: alpar@1: The same example may be coded without INTORG/INTEND markers using the alpar@1: bound type UI for the variable $x_2$ and the bound type BV for the alpar@1: variable $x_3$: alpar@1: alpar@1: \begin{verbatim} alpar@1: NAME SAMP2 alpar@1: ROWS alpar@1: N Z alpar@1: G R1 alpar@1: G R2 alpar@1: G R3 alpar@1: COLUMNS alpar@1: X1 R1 2.0 R2 1.0 alpar@1: X1 R3 5.0 Z 3.0 alpar@1: X2 R1 -1.0 R2 -1.0 alpar@1: X2 R3 3.0 Z 7.0 alpar@1: X3 R1 1.0 R2 -6.0 alpar@1: X3 Z -1.0 alpar@1: X4 R1 -1.0 R2 4.0 alpar@1: X4 R3 1.0 Z 1.0 alpar@1: RHS alpar@1: RHS1 R1 1.0 alpar@1: RHS1 R2 8.0 alpar@1: RHS1 R3 5.0 alpar@1: BOUNDS alpar@1: UP BND1 X1 4.0 alpar@1: LO BND1 X2 2.0 alpar@1: UI BND1 X2 5.0 alpar@1: BV BND1 X3 alpar@1: LO BND1 X4 3.0 alpar@1: UP BND1 X4 8.0 alpar@1: ENDATA alpar@1: \end{verbatim} alpar@1: alpar@1: %\section{Specifying predefined basis} alpar@1: %\label{secbas} alpar@1: % alpar@1: %The MPS format can also be used to specify some predefined basis for an alpar@1: %LP problem, i.e. to specify which rows and columns are basic and which alpar@1: %are non-basic. alpar@1: % alpar@1: %The order of a basis file in the MPS format is: alpar@1: % alpar@1: %$\bullet$ NAME indicator card; alpar@1: % alpar@1: %$\bullet$ data cards (can appear in arbitrary order); alpar@1: % alpar@1: %$\bullet$ ENDATA indicator card. alpar@1: % alpar@1: %Each data card specifies either a pair "basic column---non-basic row" alpar@1: %or a non-basic column. All the data cards have the following format. alpar@1: % alpar@1: %`\verb|XL|' in the field 1 means that a column, whose name is given in alpar@1: %the field 2, is basic, and a row, whose name is given in the field 3, alpar@1: %is non-basic and placed on its lower bound. alpar@1: % alpar@1: %`\verb|XU|' in the field 1 means that a column, whose name is given in alpar@1: %the field 2, is basic, and a row, whose name is given in the field 3, alpar@1: %is non-basic and placed on its upper bound. alpar@1: % alpar@1: %`\verb|LL|' in the field 1 means that a column, whose name is given in alpar@1: %the field 3, is non-basic and placed on its lower bound. alpar@1: % alpar@1: %`\verb|UL|' in the field 1 means that a column, whose name is given in alpar@1: %the field 3, is non-basic and placed on its upper bound. alpar@1: % alpar@1: %The field 2 contains a column name. alpar@1: % alpar@1: %If the indicator given in the field 1 is `\verb|XL|' or `\verb|XU|', alpar@1: %the field 3 contains a row name. Otherwise, if the indicator is alpar@1: %`\verb|LL|' or `\verb|UL|', the field 3 is not used and should be alpar@1: %empty. alpar@1: % alpar@1: %The field 4, 5, and 6 are not used and should be empty. alpar@1: % alpar@1: %A basis file in the MPS format acts like a patch: it doesn't specify alpar@1: %a basis completely, instead that it is just shows in what a given basis alpar@1: %differs from the "standard" basis, where all rows (auxiliary variables) alpar@1: %are assumed to be basic and all columns (structural variables) are alpar@1: %assumed to be non-basic. alpar@1: % alpar@1: %As an example here is a basis file that specifies an optimal basis alpar@1: %for the example LP problem given in Section \ref{secmpsex}, alpar@1: %Page \pageref{secmpsex}: alpar@1: % alpar@1: %\pagebreak alpar@1: % alpar@1: %\begin{verbatim} alpar@1: %*000000001111111111222222222233333333334444444444555555555566 alpar@1: %*234567890123456789012345678901234567890123456789012345678901 alpar@1: %NAME PLAN alpar@1: % XL BIN2 YIELD alpar@1: % XL BIN3 FE alpar@1: % XL BIN4 MN alpar@1: % XL ALUM AL alpar@1: % XL SILICON SI alpar@1: % LL BIN1 alpar@1: % LL BIN5 alpar@1: %ENDATA alpar@1: %\end{verbatim} alpar@1: alpar@1: %* eof *%