glpk09.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

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