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