COIN-OR::LEMON - Graph Library

source: glpk-cmake/doc/glpk09.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: 12.9 KB
Line 
1%* glpk09.tex *%
2
3\chapter{CPLEX LP Format}
4\label{chacplex}
5
6\section{Prelude}
7
8The CPLEX LP format\footnote{The CPLEX LP format was developed in
9the end of 1980's by CPLEX Optimization, Inc. as an input format for
10the CPLEX linear programming system. Although the CPLEX LP format is
11not as widely used as the MPS format, being row-oriented it is more
12convenient for coding mathematical programming models by human. This
13appendix describes only the features of the CPLEX LP format which are
14implemented in the GLPK package.} is intended for coding LP/MIP problem
15data. It is a row-oriented format that assumes the formulation of LP/MIP
16problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}).
17
18CPLEX LP file is a plain text file written in CPLEX LP format. Each text
19line of this file may contain up to 255 characters\footnote{GLPK allows
20text lines of arbitrary length.}. Blank lines are ignored. If a line
21contains the backslash character ($\backslash$), this character and
22everything that follows it until the end of line are considered as a
23comment and also ignored.
24
25An 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
55All the keywords are case insensitive. Keywords given above on the same
56line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|,
57and \verb|free|) being used in the LP file must start at the beginning
58of a text line.
59
60{\it Symbolic names} are used to identify the objective function,
61constraints (rows), and variables (columns). All symbolic names are case
62sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK
63allows 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
65as the following characters:
66
67\begin{verbatim}
68!  "  #  $  %  &  (  )  /  ,  .  ;  ?  @  _  `  '  {  }  |  ~
69\end{verbatim}
70
71\noindent
72with 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
75coefficients, right-hand sides of constraints, and bounds of variables.
76They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is
77a real number with optional decimal point, $s$ is a sign (\verb|+| or
78\verb|-|), $yy$ is an integer decimal exponent. Numeric constants may
79contain arbitrary number of characters. The exponent part is optional.
80The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is
81omitted, 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
95Delimiters given above on the same line are equivalent. The meaning of
96the delimiters will be explained below.
97
98{\it Blanks} are non-significant characters. They may be used freely to
99improve readability of the LP file. Besides, blanks should be used to
100separate 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
103The 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
112order);
113
114$\bullet$ end keyword.
115
116These components are discussed in following sections.
117
118\section{Objective function definition}
119
120The objective function definition must appear first in the LP file. It
121defines the objective function and specifies the optimization direction.
122
123The 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$$
131where $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
133objective coefficient, $x$ is a symbolic name of a variable.
134
135If necessary, the objective function definition can be continued on as
136many text lines as desired.
137
138The name of the objective function is optional and may be omitted
139(together with the semicolon that follows it). In this case the default
140name `\verb|obj|' is assigned to the objective function.
141
142If the very first sign $s$ is omitted, the sign plus is assumed. Other
143signs cannot be omitted.
144
145If some objective coefficient $c$ is omitted, 1 is assumed.
146
147Symbolic names $x$ used to denote variables are recognized by context
148and therefore needn't to be declared somewhere else.
149
150Here 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
159The constraints section must follow the objective function definition.
160It defines a system of equality and/or inequality constraints.
161
162The 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
175constraint definition.
176
177Each constraint definition can be continued on as many text lines as
178desired. However, each constraint definition must begin on a new line
179except the very first constraint definition which can begin on the same
180line as the keyword `\verb|subject to|'.
181
182Constraint definitions have the following form:
183$$
184r\ {\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$$
191where $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
193coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand
194side.
195
196The name $r$ of a constraint (which is the name of the corresponding
197auxiliary variable) is optional and may be omitted (together with the
198semicolon that follows it). In this case the default names like
199`\verb|r.nnn|' are assigned to unnamed constraints.
200
201The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand
202side of a constraint definition has exactly the same meaning as in the
203case of the objective function definition (see above).
204
205After the linear form one of the following delimiters that indicate
206the 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
214The right hand side $b$ is a numeric constant with an optional sign.
215
216Here 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
229CPLEX LP format. Each a ranged constraint can be coded as two
230constraints with identical linear forms in the left-hand side, one of
231which specifies a lower bound and other does an upper one of the
232original ranged constraint.)
233
234\section{Bounds section}
235
236The bounds section is intended to define bounds of variables. This
237section is optional; if it is specified, it must follow the constraints
238section. If the bound section is omitted, all variables are assumed to
239be non-negative (i.e. that they have zero lower bound and no upper
240bound).
241
242The 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
255where {\it definition}$_k, k=1,\dots,p,$ is a particular bound
256definition.
257
258Each bound definition must begin on a new line\footnote{The GLPK
259implementation allows several bound definitions to be placed on the same
260line.} except the very first bound definition which can begin on the
261same line as the keyword `\verb|bounds|'.
262
263Syntactically constraint definitions can have one of the following six
264forms:
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
278where $x$ is a symbolic name of a variable, $l$ is a numeric constant
279with 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
281numeric constant with an optional sign that defines an upper bound of
282the variable or \verb|+inf| that means that the variable has no upper
283bound, $t$ is a numeric constant with an optional sign that defines a
284fixed value of the variable.
285
286By default all variables are non-negative, i.e. have zero lower bound
287and no upper bound. Therefore definitions of these default bounds can be
288omitted in the bounds section.
289
290Here 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
303The general, integer, and binary sections are intended to define
304some variables as integer or binary. All these sections are optional
305and needed only in case of MIP problems. If they are specified, they
306must follow the bounds section or, if the latter is omitted, the
307constraints section.
308
309All the general, integer, and binary sections have the same form as
310follows:
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
331where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.
332
333Each symbolic name must begin on a new line\footnote{The GLPK
334implementation allows several symbolic names to be placed on the same
335line.} except the very first symbolic name which can begin on the same
336line as the keyword `\verb|general|', `\verb|integer|', or
337`\verb|binary|'.
338
339If a variable appears in the general or the integer section, it is
340assumed to be general integer variable. If a variable appears in the
341binary section, it is assumed to be binary variable, i.e. an integer
342variable whose lower bound is zero and upper bound is one. (Note that
343if bounds of a variable are specified in the bounds section and then
344the variable appears in the binary section, its previously specified
345bounds are ignored.)
346
347Here 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
358The keyword `\verb|end|' is intended to end the LP file. It must begin
359on a separate line and no other elements (except comments and blank
360lines) must follow it. Although this keyword is optional, it is strongly
361recommended to include it in the LP file.
362
363\section{Example of CPLEX LP file}
364
365Here is a complete example of CPLEX LP file that corresponds to the
366example given in Section \ref{secmpsex}, page \pageref{secmpsex}.
367
368{\footnotesize
369\begin{verbatim}
370\* plan.lp *\
371
372Minimize
373   value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +
374          .21 alum + .38 silicon
375
376Subject 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
399Bounds
400          bin1 <=  200
401          bin2 <= 2500
402   400 <= bin3 <=  800
403   100 <= bin4 <=  700
404          bin5 <= 1500
405
406End
407
408\* eof *\
409\end{verbatim}
410
411}
412
413%* eof *%
Note: See TracBrowser for help on using the repository browser.