1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/glpk09.tex	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,413 @@
     1.4 +%* glpk09.tex *%
     1.5 +
     1.6 +\chapter{CPLEX LP Format}
     1.7 +\label{chacplex}
     1.8 +
     1.9 +\section{Prelude}
    1.10 +
    1.11 +The CPLEX LP format\footnote{The CPLEX LP format was developed in
    1.12 +the end of 1980's by CPLEX Optimization, Inc. as an input format for
    1.13 +the CPLEX linear programming system. Although the CPLEX LP format is
    1.14 +not as widely used as the MPS format, being row-oriented it is more
    1.15 +convenient for coding mathematical programming models by human. This
    1.16 +appendix describes only the features of the CPLEX LP format which are
    1.17 +implemented in the GLPK package.} is intended for coding LP/MIP problem
    1.18 +data. It is a row-oriented format that assumes the formulation of LP/MIP
    1.19 +problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}).
    1.20 +
    1.21 +CPLEX LP file is a plain text file written in CPLEX LP format. Each text
    1.22 +line of this file may contain up to 255 characters\footnote{GLPK allows
    1.23 +text lines of arbitrary length.}. Blank lines are ignored. If a line
    1.24 +contains the backslash character ($\backslash$), this character and
    1.25 +everything that follows it until the end of line are considered as a
    1.26 +comment and also ignored.
    1.27 +
    1.28 +An LP file is coded by the user using the following elements:
    1.29 +
    1.30 +$\bullet$ keywords;
    1.31 +
    1.32 +$\bullet$ symbolic names;
    1.33 +
    1.34 +$\bullet$ numeric constants;
    1.35 +
    1.36 +$\bullet$ delimiters;
    1.37 +
    1.38 +$\bullet$ blanks.
    1.39 +
    1.40 +\newpage
    1.41 +
    1.42 +{\it Keywords} which may be used in the LP file are the following:
    1.43 +
    1.44 +\begin{verbatim}
    1.45 +      minimize        minimum        min
    1.46 +      maximize        maximum        max
    1.47 +      subject to      such that      s.t.      st.      st
    1.48 +      bounds          bound
    1.49 +      general         generals       gen
    1.50 +      integer         integers       int
    1.51 +      binary          binaries       bin
    1.52 +      infinity        inf
    1.53 +      free
    1.54 +      end
    1.55 +\end{verbatim}
    1.56 +
    1.57 +\noindent
    1.58 +All the keywords are case insensitive. Keywords given above on the same
    1.59 +line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|,
    1.60 +and \verb|free|) being used in the LP file must start at the beginning
    1.61 +of a text line.
    1.62 +
    1.63 +{\it Symbolic names} are used to identify the objective function,
    1.64 +constraints (rows), and variables (columns). All symbolic names are case
    1.65 +sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK
    1.66 +allows symbolic names having up to 255 characters.} (\verb|a|, \dots,
    1.67 +\verb|z|, \verb|A|, \dots, \verb|Z|, \verb|0|, \dots, \verb|9|) as well
    1.68 +as the following characters:
    1.69 +
    1.70 +\begin{verbatim}
    1.71 +!  "  #  $  %  &  (  )  /  ,  .  ;  ?  @  _  `  '  {  }  |  ~
    1.72 +\end{verbatim}
    1.73 +
    1.74 +\noindent
    1.75 +with exception that no symbolic name can begin with a digit or a period.
    1.76 +
    1.77 +{\it Numeric constants} are used to denote constraint and objective
    1.78 +coefficients, right-hand sides of constraints, and bounds of variables.
    1.79 +They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is
    1.80 +a real number with optional decimal point, $s$ is a sign (\verb|+| or
    1.81 +\verb|-|), $yy$ is an integer decimal exponent. Numeric constants may
    1.82 +contain arbitrary number of characters. The exponent part is optional.
    1.83 +The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is
    1.84 +omitted, plus is assumed.
    1.85 +
    1.86 +{\it Delimiters} that may be used in the LP file are the following:
    1.87 +
    1.88 +\begin{verbatim}
    1.89 +      :
    1.90 +      +
    1.91 +      -
    1.92 +      <   <=   =<
    1.93 +      >   >=   =>
    1.94 +      =
    1.95 +\end{verbatim}
    1.96 +
    1.97 +\noindent
    1.98 +Delimiters given above on the same line are equivalent. The meaning of
    1.99 +the delimiters will be explained below.
   1.100 +
   1.101 +{\it Blanks} are non-significant characters. They may be used freely to
   1.102 +improve readability of the LP file. Besides, blanks should be used to
   1.103 +separate elements from each other if there is no other way to do that
   1.104 +(for example, to separate a keyword from a following symbolic name).
   1.105 +
   1.106 +The order of an LP file is:
   1.107 +
   1.108 +$\bullet$ objective function definition;
   1.109 +
   1.110 +$\bullet$ constraints section;
   1.111 +
   1.112 +$\bullet$ bounds section;
   1.113 +
   1.114 +$\bullet$ general, integer, and binary sections (can appear in arbitrary
   1.115 +order);
   1.116 +
   1.117 +$\bullet$ end keyword.
   1.118 +
   1.119 +These components are discussed in following sections.
   1.120 +
   1.121 +\section{Objective function definition}
   1.122 +
   1.123 +The objective function definition must appear first in the LP file. It
   1.124 +defines the objective function and specifies the optimization direction.
   1.125 +
   1.126 +The objective function definition has the following form:
   1.127 +$$
   1.128 +\left\{
   1.129 +\begin{array}{@{}c@{}}
   1.130 +{\tt minimize} \\ {\tt maximize}
   1.131 +\end{array}
   1.132 +\right\}\ f\ {\tt :}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
   1.133 +$$
   1.134 +where $f$ is a symbolic name of the objective function, $s$ is a sign
   1.135 +\verb|+| or \verb|-|, $c$ is a numeric constant that denotes an
   1.136 +objective coefficient, $x$ is a symbolic name of a variable.
   1.137 +
   1.138 +If necessary, the objective function definition can be continued on as
   1.139 +many text lines as desired.
   1.140 +
   1.141 +The name of the objective function is optional and may be omitted
   1.142 +(together with the semicolon that follows it). In this case the default
   1.143 +name `\verb|obj|' is assigned to the objective function.
   1.144 +
   1.145 +If the very first sign $s$ is omitted, the sign plus is assumed. Other
   1.146 +signs cannot be omitted.
   1.147 +
   1.148 +If some objective coefficient $c$ is omitted, 1 is assumed.
   1.149 +
   1.150 +Symbolic names $x$ used to denote variables are recognized by context
   1.151 +and therefore needn't to be declared somewhere else.
   1.152 +
   1.153 +Here is an example of the objective function definition:
   1.154 +
   1.155 +\begin{verbatim}
   1.156 +   Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 +
   1.157 +      x7 - .01x8
   1.158 +\end{verbatim}
   1.159 +
   1.160 +\section{Constraints section}
   1.161 +
   1.162 +The constraints section must follow the objective function definition.
   1.163 +It defines a system of equality and/or inequality constraints.
   1.164 +
   1.165 +The constraint section has the following form:
   1.166 +
   1.167 +\begin{center}
   1.168 +\begin{tabular}{l}
   1.169 +\verb|subject to| \\
   1.170 +{\it constraint}$_1$ \\
   1.171 +{\it constraint}$_2$ \\
   1.172 +\hspace{20pt}\dots \\
   1.173 +{\it constraint}$_m$ \\
   1.174 +\end{tabular}
   1.175 +\end{center}
   1.176 +
   1.177 +\noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular
   1.178 +constraint definition.
   1.179 +
   1.180 +Each constraint definition can be continued on as many text lines as
   1.181 +desired. However, each constraint definition must begin on a new line
   1.182 +except the very first constraint definition which can begin on the same
   1.183 +line as the keyword `\verb|subject to|'.
   1.184 +
   1.185 +Constraint definitions have the following form:
   1.186 +$$
   1.187 +r\ {\tt:}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
   1.188 +\ \left\{
   1.189 +\begin{array}{@{}c@{}}
   1.190 +\mbox{\tt<=} \\ \mbox{\tt>=} \\ \mbox{\tt=}
   1.191 +\end{array}
   1.192 +\right\}\ b
   1.193 +$$
   1.194 +where $r$ is a symbolic name of a constraint, $s$ is a sign \verb|+| or
   1.195 +\verb|-|, $c$ is a numeric constant that denotes a constraint
   1.196 +coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand
   1.197 +side.
   1.198 +
   1.199 +The name $r$ of a constraint (which is the name of the corresponding
   1.200 +auxiliary variable) is optional and may be omitted (together with the
   1.201 +semicolon that follows it). In this case the default names like
   1.202 +`\verb|r.nnn|' are assigned to unnamed constraints.
   1.203 +
   1.204 +The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand
   1.205 +side of a constraint definition has exactly the same meaning as in the
   1.206 +case of the objective function definition (see above).
   1.207 +
   1.208 +After the linear form one of the following delimiters that indicate
   1.209 +the constraint sense must be specified:
   1.210 +
   1.211 +\verb|<=| \ means `less than or equal to'
   1.212 +
   1.213 +\verb|>=| \ means `greater than or equal to'
   1.214 +
   1.215 +\verb|= | \ means `equal to'
   1.216 +
   1.217 +The right hand side $b$ is a numeric constant with an optional sign.
   1.218 +
   1.219 +Here is an example of the constraints section:
   1.220 +
   1.221 +\begin{verbatim}
   1.222 +   Subject To
   1.223 +      one: y1 + 3 a1 - a2 - b >= 1.5
   1.224 +      y2 + 2 a3 + 2
   1.225 +         a4 - b >= -1.5
   1.226 +      two : y4 + 3 a1 + 4 a5 - b <= +1
   1.227 +      .20y5 + 5 a2 - b = 0
   1.228 +      1.7 y6 - a6 + 5 a777 - b >= 1
   1.229 +\end{verbatim}
   1.230 +
   1.231 +(Should note that it is impossible to express ranged constraints in the
   1.232 +CPLEX LP format. Each a ranged constraint can be coded as two
   1.233 +constraints with identical linear forms in the left-hand side, one of
   1.234 +which specifies a lower bound and other does an upper one of the
   1.235 +original ranged constraint.)
   1.236 +
   1.237 +\section{Bounds section}
   1.238 +
   1.239 +The bounds section is intended to define bounds of variables. This
   1.240 +section is optional; if it is specified, it must follow the constraints
   1.241 +section. If the bound section is omitted, all variables are assumed to
   1.242 +be non-negative (i.e. that they have zero lower bound and no upper
   1.243 +bound).
   1.244 +
   1.245 +The bounds section has the following form:
   1.246 +
   1.247 +\begin{center}
   1.248 +\begin{tabular}{l}
   1.249 +\verb|bounds| \\
   1.250 +{\it definition}$_1$ \\
   1.251 +{\it definition}$_2$ \\
   1.252 +\hspace{20pt}\dots \\
   1.253 +{\it definition}$_p$ \\
   1.254 +\end{tabular}
   1.255 +\end{center}
   1.256 +
   1.257 +\noindent
   1.258 +where {\it definition}$_k, k=1,\dots,p,$ is a particular bound
   1.259 +definition.
   1.260 +
   1.261 +Each bound definition must begin on a new line\footnote{The GLPK
   1.262 +implementation allows several bound definitions to be placed on the same
   1.263 +line.} except the very first bound definition which can begin on the
   1.264 +same line as the keyword `\verb|bounds|'.
   1.265 +
   1.266 +Syntactically constraint definitions can have one of the following six
   1.267 +forms:
   1.268 +
   1.269 +\begin{center}
   1.270 +\begin{tabular}{ll}
   1.271 +$x$ \verb|>=| $l$ &              specifies a lower bound \\
   1.272 +$l$ \verb|<=| $x$ &              specifies a lower bound \\
   1.273 +$x$ \verb|<=| $u$ &              specifies an upper bound \\
   1.274 +$l$ \verb|<=| $x$ \verb|<=| $u$ &specifies both lower and upper bounds\\
   1.275 +$x$ \verb|=| $t$                &specifies a fixed value \\
   1.276 +$x$ \verb|free|                 &specifies free variable
   1.277 +\end{tabular}
   1.278 +\end{center}
   1.279 +
   1.280 +\noindent
   1.281 +where $x$ is a symbolic name of a variable, $l$ is a numeric constant
   1.282 +with an optional sign that defines a lower bound of the variable or
   1.283 +\verb|-inf| that means that the variable has no lower bound, $u$ is a
   1.284 +numeric constant with an optional sign that defines an upper bound of
   1.285 +the variable or \verb|+inf| that means that the variable has no upper
   1.286 +bound, $t$ is a numeric constant with an optional sign that defines a
   1.287 +fixed value of the variable.
   1.288 +
   1.289 +By default all variables are non-negative, i.e. have zero lower bound
   1.290 +and no upper bound. Therefore definitions of these default bounds can be
   1.291 +omitted in the bounds section.
   1.292 +
   1.293 +Here is an example of the bounds section:
   1.294 +
   1.295 +\begin{verbatim}
   1.296 +   Bounds
   1.297 +      -inf <= a1 <= 100
   1.298 +      -100 <= a2
   1.299 +      b <= 100
   1.300 +      x2 = +123.456
   1.301 +      x3 free
   1.302 +\end{verbatim}
   1.303 +
   1.304 +\section{General, integer, and binary sections}
   1.305 +
   1.306 +The general, integer, and binary sections are intended to define
   1.307 +some variables as integer or binary. All these sections are optional
   1.308 +and needed only in case of MIP problems. If they are specified, they
   1.309 +must follow the bounds section or, if the latter is omitted, the
   1.310 +constraints section.
   1.311 +
   1.312 +All the general, integer, and binary sections have the same form as
   1.313 +follows:
   1.314 +
   1.315 +\begin{center}
   1.316 +\begin{tabular}{l}
   1.317 +$
   1.318 +\left\{
   1.319 +\begin{array}{@{}l@{}}
   1.320 +\verb|general| \\
   1.321 +\verb|integer| \\
   1.322 +\verb|binary | \\
   1.323 +\end{array}
   1.324 +\right\}
   1.325 +$ \\
   1.326 +\hspace{10pt}$x_1$ \\
   1.327 +\hspace{10pt}$x_2$ \\
   1.328 +\hspace{10pt}\dots \\
   1.329 +\hspace{10pt}$x_q$ \\
   1.330 +\end{tabular}
   1.331 +\end{center}
   1.332 +
   1.333 +\noindent
   1.334 +where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.
   1.335 +
   1.336 +Each symbolic name must begin on a new line\footnote{The GLPK
   1.337 +implementation allows several symbolic names to be placed on the same
   1.338 +line.} except the very first symbolic name which can begin on the same
   1.339 +line as the keyword `\verb|general|', `\verb|integer|', or
   1.340 +`\verb|binary|'.
   1.341 +
   1.342 +If a variable appears in the general or the integer section, it is
   1.343 +assumed to be general integer variable. If a variable appears in the
   1.344 +binary section, it is assumed to be binary variable, i.e. an integer
   1.345 +variable whose lower bound is zero and upper bound is one. (Note that
   1.346 +if bounds of a variable are specified in the bounds section and then
   1.347 +the variable appears in the binary section, its previously specified
   1.348 +bounds are ignored.)
   1.349 +
   1.350 +Here is an example of the integer section:
   1.351 +
   1.352 +\begin{verbatim}
   1.353 +   Integer
   1.354 +      z12
   1.355 +      z22
   1.356 +      z35
   1.357 +\end{verbatim}
   1.358 +
   1.359 +\section{End keyword}
   1.360 +
   1.361 +The keyword `\verb|end|' is intended to end the LP file. It must begin
   1.362 +on a separate line and no other elements (except comments and blank
   1.363 +lines) must follow it. Although this keyword is optional, it is strongly
   1.364 +recommended to include it in the LP file.
   1.365 +
   1.366 +\section{Example of CPLEX LP file}
   1.367 +
   1.368 +Here is a complete example of CPLEX LP file that corresponds to the
   1.369 +example given in Section \ref{secmpsex}, page \pageref{secmpsex}.
   1.370 +
   1.371 +{\footnotesize
   1.372 +\begin{verbatim}
   1.373 +\* plan.lp *\
   1.374 +
   1.375 +Minimize
   1.376 +   value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +
   1.377 +          .21 alum + .38 silicon
   1.378 +
   1.379 +Subject To
   1.380 +   yield:     bin1 +     bin2 +     bin3 +     bin4 +     bin5 +
   1.381 +              alum +     silicon                                 =  2000
   1.382 +
   1.383 +   fe:    .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 +
   1.384 +          .01 alum + .03 silicon                                 <=   60
   1.385 +
   1.386 +   cu:    .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 +
   1.387 +          .01 alum                                               <=  100
   1.388 +
   1.389 +   mn:    .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5   <=   40
   1.390 +
   1.391 +   mg:    .02 bin1 + .03 bin2                       + .01 bin5   <=   30
   1.392 +
   1.393 +   al:    .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 +
   1.394 +          .97 alum                                               >= 1500
   1.395 +
   1.396 +   si1:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
   1.397 +          .01 alum + .97 silicon                                 >=  250
   1.398 +
   1.399 +   si2:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
   1.400 +          .01 alum + .97 silicon                                 <=  300
   1.401 +
   1.402 +Bounds
   1.403 +          bin1 <=  200
   1.404 +          bin2 <= 2500
   1.405 +   400 <= bin3 <=  800
   1.406 +   100 <= bin4 <=  700
   1.407 +          bin5 <= 1500
   1.408 +
   1.409 +End
   1.410 +
   1.411 +\* eof *\
   1.412 +\end{verbatim}
   1.413 +
   1.414 +}
   1.415 +
   1.416 +%* eof *%