%* 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 *%