simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 423 insertions, 0 deletions

diff --git a/glpk-5.0/doc/glpk09.tex b/glpk-5.0/doc/glpk09.tex
new file mode 100644
index 0000000..a78e987
--- /dev/null
+++ b/glpk-5.0/doc/glpk09.tex
@@ -0,0 +1,423 @@
+%* 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: keywords,
+symbolic names, numeric constants, delimiters, and blanks.
+
+{\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.
+
+\newpage
+
+{\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 the following:
+
+%\vspace*{-8pt}
+
+%\begin{itemize}
+\Item{---}objective function definition;
+
+\Item{---}constraints section;
+
+\Item{---}bounds section;
+
+\Item{---}general, integer, and binary sections (can appear in
+arbitrary order);
+
+\Item{---}end keyword.
+%\end{itemize}
+
+%\vspace*{-8pt}
+
+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\ \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$ \\
+\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\ \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 the latter case the default names like
+`\verb|r.nnn|' are assigned to unnamed constraints.
+
+The linear form $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 indicates
+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. Another way is to introduce a slack
+double-bounded variable; for example, the
+constraint
+$$10\leq x+2y+3z\leq 50$$
+can be written as follows:
+$$x+2y+3z+t=50,$$
+where $0\leq t\leq 40$ is a slack variable.
+
+\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$ \\
+\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|'.
+
+%\newpage
+
+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}\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|'.
+
+%\newpage
+
+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}
+
+\newpage
+
+\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}.
+
+\medskip
+
+\begin{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}
+\end{footnotesize}
+
+%* eof *%