lemon-project-template-glpk
view deps/glpk/doc/glpk09.tex @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 %* glpk09.tex *%
3 \chapter{CPLEX LP Format}
4 \label{chacplex}
6 \section{Prelude}
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}).
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.
25 An LP file is coded by the user using the following elements:
27 $\bullet$ keywords;
29 $\bullet$ symbolic names;
31 $\bullet$ numeric constants;
33 $\bullet$ delimiters;
35 $\bullet$ blanks.
37 \newpage
39 {\it Keywords} which may be used in the LP file are the following:
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}
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.
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:
67 \begin{verbatim}
68 ! " # $ % & ( ) / , . ; ? @ _ ` ' { } | ~
69 \end{verbatim}
71 \noindent
72 with exception that no symbolic name can begin with a digit or a period.
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.
83 {\it Delimiters} that may be used in the LP file are the following:
85 \begin{verbatim}
86 :
87 +
88 -
89 < <= =<
90 > >= =>
91 =
92 \end{verbatim}
94 \noindent
95 Delimiters given above on the same line are equivalent. The meaning of
96 the delimiters will be explained below.
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).
103 The order of an LP file is:
105 $\bullet$ objective function definition;
107 $\bullet$ constraints section;
109 $\bullet$ bounds section;
111 $\bullet$ general, integer, and binary sections (can appear in arbitrary
112 order);
114 $\bullet$ end keyword.
116 These components are discussed in following sections.
118 \section{Objective function definition}
120 The objective function definition must appear first in the LP file. It
121 defines the objective function and specifies the optimization direction.
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.
135 If necessary, the objective function definition can be continued on as
136 many text lines as desired.
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.
142 If the very first sign $s$ is omitted, the sign plus is assumed. Other
143 signs cannot be omitted.
145 If some objective coefficient $c$ is omitted, 1 is assumed.
147 Symbolic names $x$ used to denote variables are recognized by context
148 and therefore needn't to be declared somewhere else.
150 Here is an example of the objective function definition:
152 \begin{verbatim}
153 Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 +
154 x7 - .01x8
155 \end{verbatim}
157 \section{Constraints section}
159 The constraints section must follow the objective function definition.
160 It defines a system of equality and/or inequality constraints.
162 The constraint section has the following form:
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}
174 \noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular
175 constraint definition.
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|'.
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.
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.
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).
205 After the linear form one of the following delimiters that indicate
206 the constraint sense must be specified:
208 \verb|<=| \ means `less than or equal to'
210 \verb|>=| \ means `greater than or equal to'
212 \verb|= | \ means `equal to'
214 The right hand side $b$ is a numeric constant with an optional sign.
216 Here is an example of the constraints section:
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}
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.)
234 \section{Bounds section}
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).
242 The bounds section has the following form:
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}
254 \noindent
255 where {\it definition}$_k, k=1,\dots,p,$ is a particular bound
256 definition.
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|'.
263 Syntactically constraint definitions can have one of the following six
264 forms:
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}
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.
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.
290 Here is an example of the bounds section:
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}
301 \section{General, integer, and binary sections}
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.
309 All the general, integer, and binary sections have the same form as
310 follows:
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}
330 \noindent
331 where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.
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|'.
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.)
347 Here is an example of the integer section:
349 \begin{verbatim}
350 Integer
351 z12
352 z22
353 z35
354 \end{verbatim}
356 \section{End keyword}
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.
363 \section{Example of CPLEX LP file}
365 Here is a complete example of CPLEX LP file that corresponds to the
366 example given in Section \ref{secmpsex}, page \pageref{secmpsex}.
368 {\footnotesize
369 \begin{verbatim}
370 \* plan.lp *\
372 Minimize
373 value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +
374 .21 alum + .38 silicon
376 Subject To
377 yield: bin1 + bin2 + bin3 + bin4 + bin5 +
378 alum + silicon = 2000
380 fe: .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 +
381 .01 alum + .03 silicon <= 60
383 cu: .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 +
384 .01 alum <= 100
386 mn: .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5 <= 40
388 mg: .02 bin1 + .03 bin2 + .01 bin5 <= 30
390 al: .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 +
391 .97 alum >= 1500
393 si1: .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
394 .01 alum + .97 silicon >= 250
396 si2: .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
397 .01 alum + .97 silicon <= 300
399 Bounds
400 bin1 <= 200
401 bin2 <= 2500
402 400 <= bin3 <= 800
403 100 <= bin4 <= 700
404 bin5 <= 1500
406 End
408 \* eof *\
409 \end{verbatim}
411 }
413 %* eof *%