lemon-project-template-glpk: deps/glpk/doc/glpk09.tex comparison

lemon-project-template-glpk

comparison deps/glpk/doc/glpk09.tex @ 9:33de93886c88

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

comparison

equal deleted inserted replaced

--1:000000000000
+:7749d5ab1169
+%* 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 *%