%* glpk09.tex *%

 \chapter{CPLEX LP Format}

 \label{chacplex}

 \section{Prelude}

 The CPLEX LP format\footnote{The CPLEX LP format was developed in

 the end of 1980's by CPLEX Optimization, Inc. as an input format for

 the CPLEX linear programming system. Although the CPLEX LP format is

 not as widely used as the MPS format, being row-oriented it is more

 convenient for coding mathematical programming models by human. This

 appendix describes only the features of the CPLEX LP format which are

 implemented in the GLPK package.} is intended for coding LP/MIP problem

 data. It is a row-oriented format that assumes the formulation of LP/MIP

 problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}).

 CPLEX LP file is a plain text file written in CPLEX LP format. Each text

 line of this file may contain up to 255 characters\footnote{GLPK allows

 text lines of arbitrary length.}. Blank lines are ignored. If a line

 contains the backslash character ($\backslash$), this character and

 everything that follows it until the end of line are considered as a

 comment and also ignored.

 An LP file is coded by the user using the following elements:

 $\bullet$ keywords;

 $\bullet$ symbolic names;

 $\bullet$ numeric constants;

 $\bullet$ delimiters;

 $\bullet$ blanks.

 \newpage

 {\it Keywords} which may be used in the LP file are the following:

 \begin{verbatim}

       minimize        minimum        min

       maximize        maximum        max

       subject to      such that      s.t.      st.      st

       bounds          bound

       general         generals       gen

       integer         integers       int

       binary          binaries       bin

       infinity        inf

       free

       end

 \end{verbatim}

 \noindent

 All the keywords are case insensitive. Keywords given above on the same

 line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|,

 and \verb|free|) being used in the LP file must start at the beginning

 of a text line.

 {\it Symbolic names} are used to identify the objective function,

 constraints (rows), and variables (columns). All symbolic names are case

 sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK

 allows symbolic names having up to 255 characters.} (\verb|a|, \dots,

 \verb|z|, \verb|A|, \dots, \verb|Z|, \verb|0|, \dots, \verb|9|) as well

 as the following characters:

 \begin{verbatim}

 !  "  #  $  %  &  (  )  /  ,  .  ;  ?  @  _  `  '  {  }  |  ~

 \end{verbatim}

 \noindent

 with exception that no symbolic name can begin with a digit or a period.

 {\it Numeric constants} are used to denote constraint and objective

 coefficients, right-hand sides of constraints, and bounds of variables.

 They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is

 a real number with optional decimal point, $s$ is a sign (\verb|+| or

 \verb|-|), $yy$ is an integer decimal exponent. Numeric constants may

 contain arbitrary number of characters. The exponent part is optional.

 The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is

 omitted, plus is assumed.

 {\it Delimiters} that may be used in the LP file are the following:

 \begin{verbatim}

       :

       +

       -

       <   <=   =<

       >   >=   =>

       =

 \end{verbatim}

 \noindent

 Delimiters given above on the same line are equivalent. The meaning of

 the delimiters will be explained below.

 {\it Blanks} are non-significant characters. They may be used freely to

 improve readability of the LP file. Besides, blanks should be used to

 separate elements from each other if there is no other way to do that

 (for example, to separate a keyword from a following symbolic name).

 The order of an LP file is:

 $\bullet$ objective function definition;

 $\bullet$ constraints section;

 $\bullet$ bounds section;

 $\bullet$ general, integer, and binary sections (can appear in arbitrary

 order);

 $\bullet$ end keyword.

 These components are discussed in following sections.

 \section{Objective function definition}

 The objective function definition must appear first in the LP file. It

 defines the objective function and specifies the optimization direction.

 The objective function definition has the following form:

 $$

 \left\{

 \begin{array}{@{}c@{}}

 {\tt minimize} \\ {\tt maximize}

 \end{array}

 \right\}\ f\ {\tt :}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x

 $$

 where $f$ is a symbolic name of the objective function, $s$ is a sign

 \verb|+| or \verb|-|, $c$ is a numeric constant that denotes an

 objective coefficient, $x$ is a symbolic name of a variable.

 If necessary, the objective function definition can be continued on as

 many text lines as desired.

 The name of the objective function is optional and may be omitted

 (together with the semicolon that follows it). In this case the default

 name `\verb|obj|' is assigned to the objective function.

 If the very first sign $s$ is omitted, the sign plus is assumed. Other

 signs cannot be omitted.

 If some objective coefficient $c$ is omitted, 1 is assumed.

 Symbolic names $x$ used to denote variables are recognized by context

 and therefore needn't to be declared somewhere else.

 Here is an example of the objective function definition:

 \begin{verbatim}

    Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 +

       x7 - .01x8

 \end{verbatim}

 \section{Constraints section}

 The constraints section must follow the objective function definition.

 It defines a system of equality and/or inequality constraints.

 The constraint section has the following form:

 \begin{center}

 \begin{tabular}{l}

 \verb|subject to| \\

 {\it constraint}$_1$ \\

 {\it constraint}$_2$ \\

 \hspace{20pt}\dots \\

 {\it constraint}$_m$ \\

 \end{tabular}

 \end{center}

 \noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular

 constraint definition.

 Each constraint definition can be continued on as many text lines as

 desired. However, each constraint definition must begin on a new line

 except the very first constraint definition which can begin on the same

 line as the keyword `\verb|subject to|'.

 Constraint definitions have the following form:

 $$

 r\ {\tt:}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x

 \ \left\{

 \begin{array}{@{}c@{}}

 \mbox{\tt<=} \\ \mbox{\tt>=} \\ \mbox{\tt=}

 \end{array}

 \right\}\ b

 $$

 where $r$ is a symbolic name of a constraint, $s$ is a sign \verb|+| or

 \verb|-|, $c$ is a numeric constant that denotes a constraint

 coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand

 side.

 The name $r$ of a constraint (which is the name of the corresponding

 auxiliary variable) is optional and may be omitted (together with the

 semicolon that follows it). In this case the default names like

 `\verb|r.nnn|' are assigned to unnamed constraints.

 The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand

 side of a constraint definition has exactly the same meaning as in the

 case of the objective function definition (see above).

 After the linear form one of the following delimiters that indicate

 the constraint sense must be specified:

 \verb|<=| \ means `less than or equal to'

 \verb|>=| \ means `greater than or equal to'

 \verb|= | \ means `equal to'

 The right hand side $b$ is a numeric constant with an optional sign.

 Here is an example of the constraints section:

 \begin{verbatim}

    Subject To

       one: y1 + 3 a1 - a2 - b >= 1.5

       y2 + 2 a3 + 2

          a4 - b >= -1.5

       two : y4 + 3 a1 + 4 a5 - b <= +1

       .20y5 + 5 a2 - b = 0

       1.7 y6 - a6 + 5 a777 - b >= 1

 \end{verbatim}

 (Should note that it is impossible to express ranged constraints in the

 CPLEX LP format. Each a ranged constraint can be coded as two

 constraints with identical linear forms in the left-hand side, one of

 which specifies a lower bound and other does an upper one of the

 original ranged constraint.)

 \section{Bounds section}

 The bounds section is intended to define bounds of variables. This

 section is optional; if it is specified, it must follow the constraints

 section. If the bound section is omitted, all variables are assumed to

 be non-negative (i.e. that they have zero lower bound and no upper

 bound).

 The bounds section has the following form:

 \begin{center}

 \begin{tabular}{l}

 \verb|bounds| \\

 {\it definition}$_1$ \\

 {\it definition}$_2$ \\

 \hspace{20pt}\dots \\

 {\it definition}$_p$ \\

 \end{tabular}

 \end{center}

 \noindent

 where {\it definition}$_k, k=1,\dots,p,$ is a particular bound

 definition.

 Each bound definition must begin on a new line\footnote{The GLPK

 implementation allows several bound definitions to be placed on the same

 line.} except the very first bound definition which can begin on the

 same line as the keyword `\verb|bounds|'.

 Syntactically constraint definitions can have one of the following six

 forms:

 \begin{center}

 \begin{tabular}{ll}

 $x$ \verb|>=| $l$ &              specifies a lower bound \\

 $l$ \verb|<=| $x$ &              specifies a lower bound \\

 $x$ \verb|<=| $u$ &              specifies an upper bound \\

 $l$ \verb|<=| $x$ \verb|<=| $u$ &specifies both lower and upper bounds\\

 $x$ \verb|=| $t$                &specifies a fixed value \\

 $x$ \verb|free|                 &specifies free variable

 \end{tabular}

 \end{center}

 \noindent

 where $x$ is a symbolic name of a variable, $l$ is a numeric constant

 with an optional sign that defines a lower bound of the variable or

 \verb|-inf| that means that the variable has no lower bound, $u$ is a

 numeric constant with an optional sign that defines an upper bound of

 the variable or \verb|+inf| that means that the variable has no upper

 bound, $t$ is a numeric constant with an optional sign that defines a

 fixed value of the variable.

 By default all variables are non-negative, i.e. have zero lower bound

 and no upper bound. Therefore definitions of these default bounds can be

 omitted in the bounds section.

 Here is an example of the bounds section:

 \begin{verbatim}

    Bounds

       -inf <= a1 <= 100

       -100 <= a2

       b <= 100

       x2 = +123.456

       x3 free

 \end{verbatim}

 \section{General, integer, and binary sections}

 The general, integer, and binary sections are intended to define

 some variables as integer or binary. All these sections are optional

 and needed only in case of MIP problems. If they are specified, they

 must follow the bounds section or, if the latter is omitted, the

 constraints section.

 All the general, integer, and binary sections have the same form as

 follows:

 \begin{center}

 \begin{tabular}{l}

 $

 \left\{

 \begin{array}{@{}l@{}}

 \verb|general| \\

 \verb|integer| \\

 \verb|binary | \\

 \end{array}

 \right\}

 $ \\

 \hspace{10pt}$x_1$ \\

 \hspace{10pt}$x_2$ \\

 \hspace{10pt}\dots \\

 \hspace{10pt}$x_q$ \\

 \end{tabular}

 \end{center}

 \noindent

 where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.

 Each symbolic name must begin on a new line\footnote{The GLPK

 implementation allows several symbolic names to be placed on the same

 line.} except the very first symbolic name which can begin on the same

 line as the keyword `\verb|general|', `\verb|integer|', or

 `\verb|binary|'.

 If a variable appears in the general or the integer section, it is

 assumed to be general integer variable. If a variable appears in the

 binary section, it is assumed to be binary variable, i.e. an integer

 variable whose lower bound is zero and upper bound is one. (Note that

 if bounds of a variable are specified in the bounds section and then

 the variable appears in the binary section, its previously specified

 bounds are ignored.)

 Here is an example of the integer section:

 \begin{verbatim}

    Integer

       z12

       z22

       z35

 \end{verbatim}

 \section{End keyword}

 The keyword `\verb|end|' is intended to end the LP file. It must begin

 on a separate line and no other elements (except comments and blank

 lines) must follow it. Although this keyword is optional, it is strongly

 recommended to include it in the LP file.

 \section{Example of CPLEX LP file}

 Here is a complete example of CPLEX LP file that corresponds to the

 example given in Section \ref{secmpsex}, page \pageref{secmpsex}.

 {\footnotesize

 \begin{verbatim}

 \* plan.lp *\

 Minimize

    value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +

           .21 alum + .38 silicon

 Subject To

    yield:     bin1 +     bin2 +     bin3 +     bin4 +     bin5 +

               alum +     silicon                                 =  2000

    fe:    .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 +

           .01 alum + .03 silicon                                 <=   60

    cu:    .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 +

           .01 alum                                               <=  100

    mn:    .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5   <=   40

    mg:    .02 bin1 + .03 bin2                       + .01 bin5   <=   30

    al:    .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 +

           .97 alum                                               >= 1500

    si1:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +

           .01 alum + .97 silicon                                 >=  250

    si2:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +

           .01 alum + .97 silicon                                 <=  300

 Bounds

           bin1 <=  200

           bin2 <= 2500

    400 <= bin3 <=  800

    100 <= bin4 <=  700

           bin5 <= 1500

 End

 \* eof *\

 \end{verbatim}

 }

 %* eof *%