alpar@9: %* glpk09.tex *%
alpar@9: 
alpar@9: \chapter{CPLEX LP Format}
alpar@9: \label{chacplex}
alpar@9: 
alpar@9: \section{Prelude}
alpar@9: 
alpar@9: The CPLEX LP format\footnote{The CPLEX LP format was developed in
alpar@9: the end of 1980's by CPLEX Optimization, Inc. as an input format for
alpar@9: the CPLEX linear programming system. Although the CPLEX LP format is
alpar@9: not as widely used as the MPS format, being row-oriented it is more
alpar@9: convenient for coding mathematical programming models by human. This
alpar@9: appendix describes only the features of the CPLEX LP format which are
alpar@9: implemented in the GLPK package.} is intended for coding LP/MIP problem
alpar@9: data. It is a row-oriented format that assumes the formulation of LP/MIP
alpar@9: problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}).
alpar@9: 
alpar@9: CPLEX LP file is a plain text file written in CPLEX LP format. Each text
alpar@9: line of this file may contain up to 255 characters\footnote{GLPK allows
alpar@9: text lines of arbitrary length.}. Blank lines are ignored. If a line
alpar@9: contains the backslash character ($\backslash$), this character and
alpar@9: everything that follows it until the end of line are considered as a
alpar@9: comment and also ignored.
alpar@9: 
alpar@9: An LP file is coded by the user using the following elements:
alpar@9: 
alpar@9: $\bullet$ keywords;
alpar@9: 
alpar@9: $\bullet$ symbolic names;
alpar@9: 
alpar@9: $\bullet$ numeric constants;
alpar@9: 
alpar@9: $\bullet$ delimiters;
alpar@9: 
alpar@9: $\bullet$ blanks.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: {\it Keywords} which may be used in the LP file are the following:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:       minimize        minimum        min
alpar@9:       maximize        maximum        max
alpar@9:       subject to      such that      s.t.      st.      st
alpar@9:       bounds          bound
alpar@9:       general         generals       gen
alpar@9:       integer         integers       int
alpar@9:       binary          binaries       bin
alpar@9:       infinity        inf
alpar@9:       free
alpar@9:       end
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: All the keywords are case insensitive. Keywords given above on the same
alpar@9: line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|,
alpar@9: and \verb|free|) being used in the LP file must start at the beginning
alpar@9: of a text line.
alpar@9: 
alpar@9: {\it Symbolic names} are used to identify the objective function,
alpar@9: constraints (rows), and variables (columns). All symbolic names are case
alpar@9: sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK
alpar@9: allows symbolic names having up to 255 characters.} (\verb|a|, \dots,
alpar@9: \verb|z|, \verb|A|, \dots, \verb|Z|, \verb|0|, \dots, \verb|9|) as well
alpar@9: as the following characters:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: !  "  #  $  %  &  (  )  /  ,  .  ;  ?  @  _  `  '  {  }  |  ~
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: with exception that no symbolic name can begin with a digit or a period.
alpar@9: 
alpar@9: {\it Numeric constants} are used to denote constraint and objective
alpar@9: coefficients, right-hand sides of constraints, and bounds of variables.
alpar@9: They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is
alpar@9: a real number with optional decimal point, $s$ is a sign (\verb|+| or
alpar@9: \verb|-|), $yy$ is an integer decimal exponent. Numeric constants may
alpar@9: contain arbitrary number of characters. The exponent part is optional.
alpar@9: The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is
alpar@9: omitted, plus is assumed.
alpar@9: 
alpar@9: {\it Delimiters} that may be used in the LP file are the following:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:       :
alpar@9:       +
alpar@9:       -
alpar@9:       <   <=   =<
alpar@9:       >   >=   =>
alpar@9:       =
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: Delimiters given above on the same line are equivalent. The meaning of
alpar@9: the delimiters will be explained below.
alpar@9: 
alpar@9: {\it Blanks} are non-significant characters. They may be used freely to
alpar@9: improve readability of the LP file. Besides, blanks should be used to
alpar@9: separate elements from each other if there is no other way to do that
alpar@9: (for example, to separate a keyword from a following symbolic name).
alpar@9: 
alpar@9: The order of an LP file is:
alpar@9: 
alpar@9: $\bullet$ objective function definition;
alpar@9: 
alpar@9: $\bullet$ constraints section;
alpar@9: 
alpar@9: $\bullet$ bounds section;
alpar@9: 
alpar@9: $\bullet$ general, integer, and binary sections (can appear in arbitrary
alpar@9: order);
alpar@9: 
alpar@9: $\bullet$ end keyword.
alpar@9: 
alpar@9: These components are discussed in following sections.
alpar@9: 
alpar@9: \section{Objective function definition}
alpar@9: 
alpar@9: The objective function definition must appear first in the LP file. It
alpar@9: defines the objective function and specifies the optimization direction.
alpar@9: 
alpar@9: The objective function definition has the following form:
alpar@9: $$
alpar@9: \left\{
alpar@9: \begin{array}{@{}c@{}}
alpar@9: {\tt minimize} \\ {\tt maximize}
alpar@9: \end{array}
alpar@9: \right\}\ f\ {\tt :}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
alpar@9: $$
alpar@9: where $f$ is a symbolic name of the objective function, $s$ is a sign
alpar@9: \verb|+| or \verb|-|, $c$ is a numeric constant that denotes an
alpar@9: objective coefficient, $x$ is a symbolic name of a variable.
alpar@9: 
alpar@9: If necessary, the objective function definition can be continued on as
alpar@9: many text lines as desired.
alpar@9: 
alpar@9: The name of the objective function is optional and may be omitted
alpar@9: (together with the semicolon that follows it). In this case the default
alpar@9: name `\verb|obj|' is assigned to the objective function.
alpar@9: 
alpar@9: If the very first sign $s$ is omitted, the sign plus is assumed. Other
alpar@9: signs cannot be omitted.
alpar@9: 
alpar@9: If some objective coefficient $c$ is omitted, 1 is assumed.
alpar@9: 
alpar@9: Symbolic names $x$ used to denote variables are recognized by context
alpar@9: and therefore needn't to be declared somewhere else.
alpar@9: 
alpar@9: Here is an example of the objective function definition:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 +
alpar@9:       x7 - .01x8
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \section{Constraints section}
alpar@9: 
alpar@9: The constraints section must follow the objective function definition.
alpar@9: It defines a system of equality and/or inequality constraints.
alpar@9: 
alpar@9: The constraint section has the following form:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{l}
alpar@9: \verb|subject to| \\
alpar@9: {\it constraint}$_1$ \\
alpar@9: {\it constraint}$_2$ \\
alpar@9: \hspace{20pt}\dots \\
alpar@9: {\it constraint}$_m$ \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular
alpar@9: constraint definition.
alpar@9: 
alpar@9: Each constraint definition can be continued on as many text lines as
alpar@9: desired. However, each constraint definition must begin on a new line
alpar@9: except the very first constraint definition which can begin on the same
alpar@9: line as the keyword `\verb|subject to|'.
alpar@9: 
alpar@9: Constraint definitions have the following form:
alpar@9: $$
alpar@9: r\ {\tt:}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
alpar@9: \ \left\{
alpar@9: \begin{array}{@{}c@{}}
alpar@9: \mbox{\tt<=} \\ \mbox{\tt>=} \\ \mbox{\tt=}
alpar@9: \end{array}
alpar@9: \right\}\ b
alpar@9: $$
alpar@9: where $r$ is a symbolic name of a constraint, $s$ is a sign \verb|+| or
alpar@9: \verb|-|, $c$ is a numeric constant that denotes a constraint
alpar@9: coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand
alpar@9: side.
alpar@9: 
alpar@9: The name $r$ of a constraint (which is the name of the corresponding
alpar@9: auxiliary variable) is optional and may be omitted (together with the
alpar@9: semicolon that follows it). In this case the default names like
alpar@9: `\verb|r.nnn|' are assigned to unnamed constraints.
alpar@9: 
alpar@9: The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand
alpar@9: side of a constraint definition has exactly the same meaning as in the
alpar@9: case of the objective function definition (see above).
alpar@9: 
alpar@9: After the linear form one of the following delimiters that indicate
alpar@9: the constraint sense must be specified:
alpar@9: 
alpar@9: \verb|<=| \ means `less than or equal to'
alpar@9: 
alpar@9: \verb|>=| \ means `greater than or equal to'
alpar@9: 
alpar@9: \verb|= | \ means `equal to'
alpar@9: 
alpar@9: The right hand side $b$ is a numeric constant with an optional sign.
alpar@9: 
alpar@9: Here is an example of the constraints section:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    Subject To
alpar@9:       one: y1 + 3 a1 - a2 - b >= 1.5
alpar@9:       y2 + 2 a3 + 2
alpar@9:          a4 - b >= -1.5
alpar@9:       two : y4 + 3 a1 + 4 a5 - b <= +1
alpar@9:       .20y5 + 5 a2 - b = 0
alpar@9:       1.7 y6 - a6 + 5 a777 - b >= 1
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: (Should note that it is impossible to express ranged constraints in the
alpar@9: CPLEX LP format. Each a ranged constraint can be coded as two
alpar@9: constraints with identical linear forms in the left-hand side, one of
alpar@9: which specifies a lower bound and other does an upper one of the
alpar@9: original ranged constraint.)
alpar@9: 
alpar@9: \section{Bounds section}
alpar@9: 
alpar@9: The bounds section is intended to define bounds of variables. This
alpar@9: section is optional; if it is specified, it must follow the constraints
alpar@9: section. If the bound section is omitted, all variables are assumed to
alpar@9: be non-negative (i.e. that they have zero lower bound and no upper
alpar@9: bound).
alpar@9: 
alpar@9: The bounds section has the following form:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{l}
alpar@9: \verb|bounds| \\
alpar@9: {\it definition}$_1$ \\
alpar@9: {\it definition}$_2$ \\
alpar@9: \hspace{20pt}\dots \\
alpar@9: {\it definition}$_p$ \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent
alpar@9: where {\it definition}$_k, k=1,\dots,p,$ is a particular bound
alpar@9: definition.
alpar@9: 
alpar@9: Each bound definition must begin on a new line\footnote{The GLPK
alpar@9: implementation allows several bound definitions to be placed on the same
alpar@9: line.} except the very first bound definition which can begin on the
alpar@9: same line as the keyword `\verb|bounds|'.
alpar@9: 
alpar@9: Syntactically constraint definitions can have one of the following six
alpar@9: forms:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{ll}
alpar@9: $x$ \verb|>=| $l$ &              specifies a lower bound \\
alpar@9: $l$ \verb|<=| $x$ &              specifies a lower bound \\
alpar@9: $x$ \verb|<=| $u$ &              specifies an upper bound \\
alpar@9: $l$ \verb|<=| $x$ \verb|<=| $u$ &specifies both lower and upper bounds\\
alpar@9: $x$ \verb|=| $t$                &specifies a fixed value \\
alpar@9: $x$ \verb|free|                 &specifies free variable
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent
alpar@9: where $x$ is a symbolic name of a variable, $l$ is a numeric constant
alpar@9: with an optional sign that defines a lower bound of the variable or
alpar@9: \verb|-inf| that means that the variable has no lower bound, $u$ is a
alpar@9: numeric constant with an optional sign that defines an upper bound of
alpar@9: the variable or \verb|+inf| that means that the variable has no upper
alpar@9: bound, $t$ is a numeric constant with an optional sign that defines a
alpar@9: fixed value of the variable.
alpar@9: 
alpar@9: By default all variables are non-negative, i.e. have zero lower bound
alpar@9: and no upper bound. Therefore definitions of these default bounds can be
alpar@9: omitted in the bounds section.
alpar@9: 
alpar@9: Here is an example of the bounds section:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    Bounds
alpar@9:       -inf <= a1 <= 100
alpar@9:       -100 <= a2
alpar@9:       b <= 100
alpar@9:       x2 = +123.456
alpar@9:       x3 free
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \section{General, integer, and binary sections}
alpar@9: 
alpar@9: The general, integer, and binary sections are intended to define
alpar@9: some variables as integer or binary. All these sections are optional
alpar@9: and needed only in case of MIP problems. If they are specified, they
alpar@9: must follow the bounds section or, if the latter is omitted, the
alpar@9: constraints section.
alpar@9: 
alpar@9: All the general, integer, and binary sections have the same form as
alpar@9: follows:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{l}
alpar@9: $
alpar@9: \left\{
alpar@9: \begin{array}{@{}l@{}}
alpar@9: \verb|general| \\
alpar@9: \verb|integer| \\
alpar@9: \verb|binary | \\
alpar@9: \end{array}
alpar@9: \right\}
alpar@9: $ \\
alpar@9: \hspace{10pt}$x_1$ \\
alpar@9: \hspace{10pt}$x_2$ \\
alpar@9: \hspace{10pt}\dots \\
alpar@9: \hspace{10pt}$x_q$ \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent
alpar@9: where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.
alpar@9: 
alpar@9: Each symbolic name must begin on a new line\footnote{The GLPK
alpar@9: implementation allows several symbolic names to be placed on the same
alpar@9: line.} except the very first symbolic name which can begin on the same
alpar@9: line as the keyword `\verb|general|', `\verb|integer|', or
alpar@9: `\verb|binary|'.
alpar@9: 
alpar@9: If a variable appears in the general or the integer section, it is
alpar@9: assumed to be general integer variable. If a variable appears in the
alpar@9: binary section, it is assumed to be binary variable, i.e. an integer
alpar@9: variable whose lower bound is zero and upper bound is one. (Note that
alpar@9: if bounds of a variable are specified in the bounds section and then
alpar@9: the variable appears in the binary section, its previously specified
alpar@9: bounds are ignored.)
alpar@9: 
alpar@9: Here is an example of the integer section:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    Integer
alpar@9:       z12
alpar@9:       z22
alpar@9:       z35
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \section{End keyword}
alpar@9: 
alpar@9: The keyword `\verb|end|' is intended to end the LP file. It must begin
alpar@9: on a separate line and no other elements (except comments and blank
alpar@9: lines) must follow it. Although this keyword is optional, it is strongly
alpar@9: recommended to include it in the LP file.
alpar@9: 
alpar@9: \section{Example of CPLEX LP file}
alpar@9: 
alpar@9: Here is a complete example of CPLEX LP file that corresponds to the
alpar@9: example given in Section \ref{secmpsex}, page \pageref{secmpsex}.
alpar@9: 
alpar@9: {\footnotesize
alpar@9: \begin{verbatim}
alpar@9: \* plan.lp *\
alpar@9: 
alpar@9: Minimize
alpar@9:    value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +
alpar@9:           .21 alum + .38 silicon
alpar@9: 
alpar@9: Subject To
alpar@9:    yield:     bin1 +     bin2 +     bin3 +     bin4 +     bin5 +
alpar@9:               alum +     silicon                                 =  2000
alpar@9: 
alpar@9:    fe:    .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 +
alpar@9:           .01 alum + .03 silicon                                 <=   60
alpar@9: 
alpar@9:    cu:    .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 +
alpar@9:           .01 alum                                               <=  100
alpar@9: 
alpar@9:    mn:    .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5   <=   40
alpar@9: 
alpar@9:    mg:    .02 bin1 + .03 bin2                       + .01 bin5   <=   30
alpar@9: 
alpar@9:    al:    .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 +
alpar@9:           .97 alum                                               >= 1500
alpar@9: 
alpar@9:    si1:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
alpar@9:           .01 alum + .97 silicon                                 >=  250
alpar@9: 
alpar@9:    si2:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
alpar@9:           .01 alum + .97 silicon                                 <=  300
alpar@9: 
alpar@9: Bounds
alpar@9:           bin1 <=  200
alpar@9:           bin2 <= 2500
alpar@9:    400 <= bin3 <=  800
alpar@9:    100 <= bin4 <=  700
alpar@9:           bin5 <= 1500
alpar@9: 
alpar@9: End
alpar@9: 
alpar@9: \* eof *\
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: }
alpar@9: 
alpar@9: %* eof *%