lemon-project-template-glpk

annotate deps/glpk/doc/glpk09.tex @ 11:4fc6ad2fb8a6

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