[9] | 1 | %* glpk09.tex *% |
---|
| 2 | |
---|
| 3 | \chapter{CPLEX LP Format} |
---|
| 4 | \label{chacplex} |
---|
| 5 | |
---|
| 6 | \section{Prelude} |
---|
| 7 | |
---|
| 8 | The CPLEX LP format\footnote{The CPLEX LP format was developed in |
---|
| 9 | the end of 1980's by CPLEX Optimization, Inc. as an input format for |
---|
| 10 | the CPLEX linear programming system. Although the CPLEX LP format is |
---|
| 11 | not as widely used as the MPS format, being row-oriented it is more |
---|
| 12 | convenient for coding mathematical programming models by human. This |
---|
| 13 | appendix describes only the features of the CPLEX LP format which are |
---|
| 14 | implemented in the GLPK package.} is intended for coding LP/MIP problem |
---|
| 15 | data. It is a row-oriented format that assumes the formulation of LP/MIP |
---|
| 16 | problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}). |
---|
| 17 | |
---|
| 18 | CPLEX LP file is a plain text file written in CPLEX LP format. Each text |
---|
| 19 | line of this file may contain up to 255 characters\footnote{GLPK allows |
---|
| 20 | text lines of arbitrary length.}. Blank lines are ignored. If a line |
---|
| 21 | contains the backslash character ($\backslash$), this character and |
---|
| 22 | everything that follows it until the end of line are considered as a |
---|
| 23 | comment and also ignored. |
---|
| 24 | |
---|
| 25 | An LP file is coded by the user using the following elements: |
---|
| 26 | |
---|
| 27 | $\bullet$ keywords; |
---|
| 28 | |
---|
| 29 | $\bullet$ symbolic names; |
---|
| 30 | |
---|
| 31 | $\bullet$ numeric constants; |
---|
| 32 | |
---|
| 33 | $\bullet$ delimiters; |
---|
| 34 | |
---|
| 35 | $\bullet$ blanks. |
---|
| 36 | |
---|
| 37 | \newpage |
---|
| 38 | |
---|
| 39 | {\it Keywords} which may be used in the LP file are the following: |
---|
| 40 | |
---|
| 41 | \begin{verbatim} |
---|
| 42 | minimize minimum min |
---|
| 43 | maximize maximum max |
---|
| 44 | subject to such that s.t. st. st |
---|
| 45 | bounds bound |
---|
| 46 | general generals gen |
---|
| 47 | integer integers int |
---|
| 48 | binary binaries bin |
---|
| 49 | infinity inf |
---|
| 50 | free |
---|
| 51 | end |
---|
| 52 | \end{verbatim} |
---|
| 53 | |
---|
| 54 | \noindent |
---|
| 55 | All the keywords are case insensitive. Keywords given above on the same |
---|
| 56 | line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|, |
---|
| 57 | and \verb|free|) being used in the LP file must start at the beginning |
---|
| 58 | of a text line. |
---|
| 59 | |
---|
| 60 | {\it Symbolic names} are used to identify the objective function, |
---|
| 61 | constraints (rows), and variables (columns). All symbolic names are case |
---|
| 62 | sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK |
---|
| 63 | allows symbolic names having up to 255 characters.} (\verb|a|, \dots, |
---|
| 64 | \verb|z|, \verb|A|, \dots, \verb|Z|, \verb|0|, \dots, \verb|9|) as well |
---|
| 65 | as the following characters: |
---|
| 66 | |
---|
| 67 | \begin{verbatim} |
---|
| 68 | ! " # $ % & ( ) / , . ; ? @ _ ` ' { } | ~ |
---|
| 69 | \end{verbatim} |
---|
| 70 | |
---|
| 71 | \noindent |
---|
| 72 | with exception that no symbolic name can begin with a digit or a period. |
---|
| 73 | |
---|
| 74 | {\it Numeric constants} are used to denote constraint and objective |
---|
| 75 | coefficients, right-hand sides of constraints, and bounds of variables. |
---|
| 76 | They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is |
---|
| 77 | a real number with optional decimal point, $s$ is a sign (\verb|+| or |
---|
| 78 | \verb|-|), $yy$ is an integer decimal exponent. Numeric constants may |
---|
| 79 | contain arbitrary number of characters. The exponent part is optional. |
---|
| 80 | The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is |
---|
| 81 | omitted, plus is assumed. |
---|
| 82 | |
---|
| 83 | {\it Delimiters} that may be used in the LP file are the following: |
---|
| 84 | |
---|
| 85 | \begin{verbatim} |
---|
| 86 | : |
---|
| 87 | + |
---|
| 88 | - |
---|
| 89 | < <= =< |
---|
| 90 | > >= => |
---|
| 91 | = |
---|
| 92 | \end{verbatim} |
---|
| 93 | |
---|
| 94 | \noindent |
---|
| 95 | Delimiters given above on the same line are equivalent. The meaning of |
---|
| 96 | the delimiters will be explained below. |
---|
| 97 | |
---|
| 98 | {\it Blanks} are non-significant characters. They may be used freely to |
---|
| 99 | improve readability of the LP file. Besides, blanks should be used to |
---|
| 100 | separate elements from each other if there is no other way to do that |
---|
| 101 | (for example, to separate a keyword from a following symbolic name). |
---|
| 102 | |
---|
| 103 | The order of an LP file is: |
---|
| 104 | |
---|
| 105 | $\bullet$ objective function definition; |
---|
| 106 | |
---|
| 107 | $\bullet$ constraints section; |
---|
| 108 | |
---|
| 109 | $\bullet$ bounds section; |
---|
| 110 | |
---|
| 111 | $\bullet$ general, integer, and binary sections (can appear in arbitrary |
---|
| 112 | order); |
---|
| 113 | |
---|
| 114 | $\bullet$ end keyword. |
---|
| 115 | |
---|
| 116 | These components are discussed in following sections. |
---|
| 117 | |
---|
| 118 | \section{Objective function definition} |
---|
| 119 | |
---|
| 120 | The objective function definition must appear first in the LP file. It |
---|
| 121 | defines the objective function and specifies the optimization direction. |
---|
| 122 | |
---|
| 123 | The objective function definition has the following form: |
---|
| 124 | $$ |
---|
| 125 | \left\{ |
---|
| 126 | \begin{array}{@{}c@{}} |
---|
| 127 | {\tt minimize} \\ {\tt maximize} |
---|
| 128 | \end{array} |
---|
| 129 | \right\}\ f\ {\tt :}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x |
---|
| 130 | $$ |
---|
| 131 | where $f$ is a symbolic name of the objective function, $s$ is a sign |
---|
| 132 | \verb|+| or \verb|-|, $c$ is a numeric constant that denotes an |
---|
| 133 | objective coefficient, $x$ is a symbolic name of a variable. |
---|
| 134 | |
---|
| 135 | If necessary, the objective function definition can be continued on as |
---|
| 136 | many text lines as desired. |
---|
| 137 | |
---|
| 138 | The name of the objective function is optional and may be omitted |
---|
| 139 | (together with the semicolon that follows it). In this case the default |
---|
| 140 | name `\verb|obj|' is assigned to the objective function. |
---|
| 141 | |
---|
| 142 | If the very first sign $s$ is omitted, the sign plus is assumed. Other |
---|
| 143 | signs cannot be omitted. |
---|
| 144 | |
---|
| 145 | If some objective coefficient $c$ is omitted, 1 is assumed. |
---|
| 146 | |
---|
| 147 | Symbolic names $x$ used to denote variables are recognized by context |
---|
| 148 | and therefore needn't to be declared somewhere else. |
---|
| 149 | |
---|
| 150 | Here is an example of the objective function definition: |
---|
| 151 | |
---|
| 152 | \begin{verbatim} |
---|
| 153 | Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 + |
---|
| 154 | x7 - .01x8 |
---|
| 155 | \end{verbatim} |
---|
| 156 | |
---|
| 157 | \section{Constraints section} |
---|
| 158 | |
---|
| 159 | The constraints section must follow the objective function definition. |
---|
| 160 | It defines a system of equality and/or inequality constraints. |
---|
| 161 | |
---|
| 162 | The constraint section has the following form: |
---|
| 163 | |
---|
| 164 | \begin{center} |
---|
| 165 | \begin{tabular}{l} |
---|
| 166 | \verb|subject to| \\ |
---|
| 167 | {\it constraint}$_1$ \\ |
---|
| 168 | {\it constraint}$_2$ \\ |
---|
| 169 | \hspace{20pt}\dots \\ |
---|
| 170 | {\it constraint}$_m$ \\ |
---|
| 171 | \end{tabular} |
---|
| 172 | \end{center} |
---|
| 173 | |
---|
| 174 | \noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular |
---|
| 175 | constraint definition. |
---|
| 176 | |
---|
| 177 | Each constraint definition can be continued on as many text lines as |
---|
| 178 | desired. However, each constraint definition must begin on a new line |
---|
| 179 | except the very first constraint definition which can begin on the same |
---|
| 180 | line as the keyword `\verb|subject to|'. |
---|
| 181 | |
---|
| 182 | Constraint definitions have the following form: |
---|
| 183 | $$ |
---|
| 184 | r\ {\tt:}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x |
---|
| 185 | \ \left\{ |
---|
| 186 | \begin{array}{@{}c@{}} |
---|
| 187 | \mbox{\tt<=} \\ \mbox{\tt>=} \\ \mbox{\tt=} |
---|
| 188 | \end{array} |
---|
| 189 | \right\}\ b |
---|
| 190 | $$ |
---|
| 191 | where $r$ is a symbolic name of a constraint, $s$ is a sign \verb|+| or |
---|
| 192 | \verb|-|, $c$ is a numeric constant that denotes a constraint |
---|
| 193 | coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand |
---|
| 194 | side. |
---|
| 195 | |
---|
| 196 | The name $r$ of a constraint (which is the name of the corresponding |
---|
| 197 | auxiliary variable) is optional and may be omitted (together with the |
---|
| 198 | semicolon that follows it). In this case the default names like |
---|
| 199 | `\verb|r.nnn|' are assigned to unnamed constraints. |
---|
| 200 | |
---|
| 201 | The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand |
---|
| 202 | side of a constraint definition has exactly the same meaning as in the |
---|
| 203 | case of the objective function definition (see above). |
---|
| 204 | |
---|
| 205 | After the linear form one of the following delimiters that indicate |
---|
| 206 | the constraint sense must be specified: |
---|
| 207 | |
---|
| 208 | \verb|<=| \ means `less than or equal to' |
---|
| 209 | |
---|
| 210 | \verb|>=| \ means `greater than or equal to' |
---|
| 211 | |
---|
| 212 | \verb|= | \ means `equal to' |
---|
| 213 | |
---|
| 214 | The right hand side $b$ is a numeric constant with an optional sign. |
---|
| 215 | |
---|
| 216 | Here is an example of the constraints section: |
---|
| 217 | |
---|
| 218 | \begin{verbatim} |
---|
| 219 | Subject To |
---|
| 220 | one: y1 + 3 a1 - a2 - b >= 1.5 |
---|
| 221 | y2 + 2 a3 + 2 |
---|
| 222 | a4 - b >= -1.5 |
---|
| 223 | two : y4 + 3 a1 + 4 a5 - b <= +1 |
---|
| 224 | .20y5 + 5 a2 - b = 0 |
---|
| 225 | 1.7 y6 - a6 + 5 a777 - b >= 1 |
---|
| 226 | \end{verbatim} |
---|
| 227 | |
---|
| 228 | (Should note that it is impossible to express ranged constraints in the |
---|
| 229 | CPLEX LP format. Each a ranged constraint can be coded as two |
---|
| 230 | constraints with identical linear forms in the left-hand side, one of |
---|
| 231 | which specifies a lower bound and other does an upper one of the |
---|
| 232 | original ranged constraint.) |
---|
| 233 | |
---|
| 234 | \section{Bounds section} |
---|
| 235 | |
---|
| 236 | The bounds section is intended to define bounds of variables. This |
---|
| 237 | section is optional; if it is specified, it must follow the constraints |
---|
| 238 | section. If the bound section is omitted, all variables are assumed to |
---|
| 239 | be non-negative (i.e. that they have zero lower bound and no upper |
---|
| 240 | bound). |
---|
| 241 | |
---|
| 242 | The bounds section has the following form: |
---|
| 243 | |
---|
| 244 | \begin{center} |
---|
| 245 | \begin{tabular}{l} |
---|
| 246 | \verb|bounds| \\ |
---|
| 247 | {\it definition}$_1$ \\ |
---|
| 248 | {\it definition}$_2$ \\ |
---|
| 249 | \hspace{20pt}\dots \\ |
---|
| 250 | {\it definition}$_p$ \\ |
---|
| 251 | \end{tabular} |
---|
| 252 | \end{center} |
---|
| 253 | |
---|
| 254 | \noindent |
---|
| 255 | where {\it definition}$_k, k=1,\dots,p,$ is a particular bound |
---|
| 256 | definition. |
---|
| 257 | |
---|
| 258 | Each bound definition must begin on a new line\footnote{The GLPK |
---|
| 259 | implementation allows several bound definitions to be placed on the same |
---|
| 260 | line.} except the very first bound definition which can begin on the |
---|
| 261 | same line as the keyword `\verb|bounds|'. |
---|
| 262 | |
---|
| 263 | Syntactically constraint definitions can have one of the following six |
---|
| 264 | forms: |
---|
| 265 | |
---|
| 266 | \begin{center} |
---|
| 267 | \begin{tabular}{ll} |
---|
| 268 | $x$ \verb|>=| $l$ & specifies a lower bound \\ |
---|
| 269 | $l$ \verb|<=| $x$ & specifies a lower bound \\ |
---|
| 270 | $x$ \verb|<=| $u$ & specifies an upper bound \\ |
---|
| 271 | $l$ \verb|<=| $x$ \verb|<=| $u$ &specifies both lower and upper bounds\\ |
---|
| 272 | $x$ \verb|=| $t$ &specifies a fixed value \\ |
---|
| 273 | $x$ \verb|free| &specifies free variable |
---|
| 274 | \end{tabular} |
---|
| 275 | \end{center} |
---|
| 276 | |
---|
| 277 | \noindent |
---|
| 278 | where $x$ is a symbolic name of a variable, $l$ is a numeric constant |
---|
| 279 | with an optional sign that defines a lower bound of the variable or |
---|
| 280 | \verb|-inf| that means that the variable has no lower bound, $u$ is a |
---|
| 281 | numeric constant with an optional sign that defines an upper bound of |
---|
| 282 | the variable or \verb|+inf| that means that the variable has no upper |
---|
| 283 | bound, $t$ is a numeric constant with an optional sign that defines a |
---|
| 284 | fixed value of the variable. |
---|
| 285 | |
---|
| 286 | By default all variables are non-negative, i.e. have zero lower bound |
---|
| 287 | and no upper bound. Therefore definitions of these default bounds can be |
---|
| 288 | omitted in the bounds section. |
---|
| 289 | |
---|
| 290 | Here is an example of the bounds section: |
---|
| 291 | |
---|
| 292 | \begin{verbatim} |
---|
| 293 | Bounds |
---|
| 294 | -inf <= a1 <= 100 |
---|
| 295 | -100 <= a2 |
---|
| 296 | b <= 100 |
---|
| 297 | x2 = +123.456 |
---|
| 298 | x3 free |
---|
| 299 | \end{verbatim} |
---|
| 300 | |
---|
| 301 | \section{General, integer, and binary sections} |
---|
| 302 | |
---|
| 303 | The general, integer, and binary sections are intended to define |
---|
| 304 | some variables as integer or binary. All these sections are optional |
---|
| 305 | and needed only in case of MIP problems. If they are specified, they |
---|
| 306 | must follow the bounds section or, if the latter is omitted, the |
---|
| 307 | constraints section. |
---|
| 308 | |
---|
| 309 | All the general, integer, and binary sections have the same form as |
---|
| 310 | follows: |
---|
| 311 | |
---|
| 312 | \begin{center} |
---|
| 313 | \begin{tabular}{l} |
---|
| 314 | $ |
---|
| 315 | \left\{ |
---|
| 316 | \begin{array}{@{}l@{}} |
---|
| 317 | \verb|general| \\ |
---|
| 318 | \verb|integer| \\ |
---|
| 319 | \verb|binary | \\ |
---|
| 320 | \end{array} |
---|
| 321 | \right\} |
---|
| 322 | $ \\ |
---|
| 323 | \hspace{10pt}$x_1$ \\ |
---|
| 324 | \hspace{10pt}$x_2$ \\ |
---|
| 325 | \hspace{10pt}\dots \\ |
---|
| 326 | \hspace{10pt}$x_q$ \\ |
---|
| 327 | \end{tabular} |
---|
| 328 | \end{center} |
---|
| 329 | |
---|
| 330 | \noindent |
---|
| 331 | where $x_k$ is a symbolic name of variable, $k=1,\dots,q$. |
---|
| 332 | |
---|
| 333 | Each symbolic name must begin on a new line\footnote{The GLPK |
---|
| 334 | implementation allows several symbolic names to be placed on the same |
---|
| 335 | line.} except the very first symbolic name which can begin on the same |
---|
| 336 | line as the keyword `\verb|general|', `\verb|integer|', or |
---|
| 337 | `\verb|binary|'. |
---|
| 338 | |
---|
| 339 | If a variable appears in the general or the integer section, it is |
---|
| 340 | assumed to be general integer variable. If a variable appears in the |
---|
| 341 | binary section, it is assumed to be binary variable, i.e. an integer |
---|
| 342 | variable whose lower bound is zero and upper bound is one. (Note that |
---|
| 343 | if bounds of a variable are specified in the bounds section and then |
---|
| 344 | the variable appears in the binary section, its previously specified |
---|
| 345 | bounds are ignored.) |
---|
| 346 | |
---|
| 347 | Here is an example of the integer section: |
---|
| 348 | |
---|
| 349 | \begin{verbatim} |
---|
| 350 | Integer |
---|
| 351 | z12 |
---|
| 352 | z22 |
---|
| 353 | z35 |
---|
| 354 | \end{verbatim} |
---|
| 355 | |
---|
| 356 | \section{End keyword} |
---|
| 357 | |
---|
| 358 | The keyword `\verb|end|' is intended to end the LP file. It must begin |
---|
| 359 | on a separate line and no other elements (except comments and blank |
---|
| 360 | lines) must follow it. Although this keyword is optional, it is strongly |
---|
| 361 | recommended to include it in the LP file. |
---|
| 362 | |
---|
| 363 | \section{Example of CPLEX LP file} |
---|
| 364 | |
---|
| 365 | Here is a complete example of CPLEX LP file that corresponds to the |
---|
| 366 | example given in Section \ref{secmpsex}, page \pageref{secmpsex}. |
---|
| 367 | |
---|
| 368 | {\footnotesize |
---|
| 369 | \begin{verbatim} |
---|
| 370 | \* plan.lp *\ |
---|
| 371 | |
---|
| 372 | Minimize |
---|
| 373 | value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 + |
---|
| 374 | .21 alum + .38 silicon |
---|
| 375 | |
---|
| 376 | Subject To |
---|
| 377 | yield: bin1 + bin2 + bin3 + bin4 + bin5 + |
---|
| 378 | alum + silicon = 2000 |
---|
| 379 | |
---|
| 380 | fe: .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 + |
---|
| 381 | .01 alum + .03 silicon <= 60 |
---|
| 382 | |
---|
| 383 | cu: .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 + |
---|
| 384 | .01 alum <= 100 |
---|
| 385 | |
---|
| 386 | mn: .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5 <= 40 |
---|
| 387 | |
---|
| 388 | mg: .02 bin1 + .03 bin2 + .01 bin5 <= 30 |
---|
| 389 | |
---|
| 390 | al: .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 + |
---|
| 391 | .97 alum >= 1500 |
---|
| 392 | |
---|
| 393 | si1: .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 + |
---|
| 394 | .01 alum + .97 silicon >= 250 |
---|
| 395 | |
---|
| 396 | si2: .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 + |
---|
| 397 | .01 alum + .97 silicon <= 300 |
---|
| 398 | |
---|
| 399 | Bounds |
---|
| 400 | bin1 <= 200 |
---|
| 401 | bin2 <= 2500 |
---|
| 402 | 400 <= bin3 <= 800 |
---|
| 403 | 100 <= bin4 <= 700 |
---|
| 404 | bin5 <= 1500 |
---|
| 405 | |
---|
| 406 | End |
---|
| 407 | |
---|
| 408 | \* eof *\ |
---|
| 409 | \end{verbatim} |
---|
| 410 | |
---|
| 411 | } |
---|
| 412 | |
---|
| 413 | %* eof *% |
---|