123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272 
 \documentstyle[12pt]{article}
 \begin{document}
 \begin{center} {\Large LINEAR INEQUALITIES} \end{center}
 \begin{center} Solving sets of linear inequalities and equations \\
 and linear/integer optimization for small problems \end{center}
 \begin{center} Version 2.0 May 1991\end{center}
 \begin{center} Herbert Melenk \\ KonradZuseZentrum fuer
 Informationstechnik \\
 Heilbronner Str. 10 \\ D1000 Berlin 31 \\ Federal Republic of Germany \\
 melenk@sc.zibberlin.de \end{center}
 \section{Introduction}
 This package solves sets of linear inequalities with real valued numerical
 coefficients by applying the method of Fourier and Motzkin, as described
 by G.B. Dantzig in his famous work {\em Linear Programming and Extensions}.
 As input a system of linear inequalities (algebraic expressions composed
 with the relational operators $<=$ and $>=$) and equations are accepted,
 together with an optional specification, in which sequence the variables
 are to be eliminated and  if there is the freedom  which variable should
 take an extremal value in its final interval.
 \section{The Algorithm}
 The set of input formulas is treated in the following steps:
 \begin{itemize}
 \item The variables of the system are determined (together with a general
 analysis); variables, which are not mentioned explicitly during the
 call, are placed in front of the variable list; the following steps
 then are controlled by the variable list.
 \item Each equation (if any) is used to substitute one variable in the whole
 system; if here an inconsistency occurs, the procedure is stopped with
 an error message.
 \item The remaining variables then are eliminated from the system of
 inequalities one after the other by the technique of Fourier/Motzkin:
 a system for the variables ${x_1,\ldots ,x_n}$ is reordered in the form
 \[\begin{array}{cc}
 L_1(x_2,\ldots ,x_n) \ge x_1 & \\
 \ldots & \\
 L_k(x_2,\ldots ,x_n) \ge x_1 & \\
 & x_1 \ge R_1(x_2,\ldots ,x_n) \\
 & \ldots \\
 & x_1 \ge R_m(x_2,\ldots ,x_n)
 \end{array}\]
 and a new system in ${x_2,\ldots ,x_n}$
 \[\begin{array}{c}
 L_1 \ge R_1, \ldots , L_1 \ge R_m, \\
 \ldots \\
 L_k \ge R_1, \ldots , L_k \ge R_m \\
 \end{array}
 \]
 is established and processed in a recursive manner.
 \item When the last variable is encountered, the Li and Ri are numbers
 and they establish an interval; if that interval is not empty, an
 appropriate value for xn can be selected;
 \item During returning from the recursion, the values found already are
 substituted into the local Li and Ri, making them numerical values
 too and allowing a selection in a non empty interval;
 \item Finally the remaining variables are computed from substitutions
 into the equations.
 \end{itemize}
 This procedure is generally valid; its limitation lies in the fact, that
 the number of inequalities grows with each elimination step, if a variable
 occurs with both signs several times. In order to limit this effect as
 much as possible, numerical limits are collected as early as possible (by
 taking the min resp. max value) and the inequalities are converted into a
 canonical form (which actually is {\em homogeneous integer polynomial} $\ge$
 {\em number}), such that multiplicities can be determined and eliminated.
 The internal operation is based completely on REDUCE standard quotients and
 standard forms.
 If some or all variables are restricted to integer values, the
 branchandbound method is used as a macro algorithm:
 \begin{itemize}
 \item First a solution of the system is determined without integer
 restriction.
 \item If the solution contains non integer values $x_0$ for an integer
 variable $x$, new subproblems are generated with the additional
 restrictions $x<=[x_0]$ resp. $x>=[x_0]+1$, where $[]$ denotes the next
 integer below (floor value). With more than one integer variable this
 leads to a tree of subproblems.
 \item Among all feasable solutions the best one is selected.
 \end{itemize}
 \section{Algebraic Interface}
 When the package is loaded, the operators $>=$ and $<=$ are declared as
 operators, such that they can be used in algebraic expressions. The
 operator for the solution of a linear system is:
 \begin{center}
 {\tt LININEQ($<$sys$>$ [,$<$vars$>$] [,RECORD=T] [,INT=$<$ivars$>$])}
 \end{center}
 \noindent
 where $<$sys$>$ is the list of equations/inequalities either as explicit
 list or as a value which evaluates to such a list, $<$vars$>$ (optional)
 is a list of variables and/or expressions of the type $<$var$>$ $=$ min or
 $<$var$>$ = max which means, that the corresponding variable is to be
 taken at the corresponding edge of its limitating interval. Note,
 that the last (or only) variable is the first one which gets a value
 assigned; so this should be the target function in a linear
 optimization context. If the keyword parameter RECORD is equated
 with T, the intermediate inequalities are included in the result.
 An equation with the lhs INT denotes a list of variables, which
 are restricted to integer values. Note, that this does not automatically
 include a restrition to poitive numbers: such limitations must
 be given explicitly in the system.
 The result is either an empty list, if the system is inconsistent,
 or a list of equations assigning a numeric value (in the current
 domain) to each variable. If RECORD=T was selected, each element
 of the result itself is a list with the equation for the numerical
 value for the variable, followed by the lower and upper bounds
 of the corresponding interval. In most cases these bounds are
 formal expressions in the other (following) variables, often in
 the form of calls to ``max''or ``min'' If a variable is unbound to one
 side, an {\tt INF} or {\tt INF} appears in the corresponding place for
 ``infinity''.
 If the switch {\tt PRLININEQ} is set, the intervals for the selection
 of variable values are printed during the evaluation.
 If the switch {\tt TRLININEQ} is set, a complete trace of the
 elimination is printed; that may help in cases, where the result of
 the process is not understood immediately; however, this printing may
 result in a large volume.
 By default {\tt PRLININEQ} and {\tt TRLININEQ} are off.
 If the switch {\tt TRLININEQINT} is set, a restricted protocol for
 integer problems is printed, which only shows the action of the
 branchandbound method.
 \noindent An example:
 \begin{verbatim}
 linineq({ 5x1  4x2 + 13x3  2x4 + x5 = 20,
 x1  x2 + 5x3  x4 + x5 = 8,
 x1 + 6x2  7x3 + x4 + 5x5 = z,
 x1>=0,x2>=0,x3>=0,x4>=0,x5>=0}, {z=min});
 \end{verbatim}
 \noindent Result:
 \begin{verbatim}
 12 4 60
 {X5=0,X4=0,X3=,X2=,X1=0,Z=  }
 7 7 7
 \end{verbatim}
 \noindent The same with the tower of intervals:
 \begin{verbatim}
 linineq({ 5x1  4x2 + 13x3  2x4 + x5 = 20,
 x1  x2 + 5x3  x4 + x5 = 8,
 x1 + 6x2  7x3 + x4 + 5x5 = z,
 x1>=0,x2>=0,x3>=0,x4>=0,x5>=0}, {z=min}, record=t);
 \end{verbatim}
 \noindent Result:
 \begin{verbatim}
 {{X5=0,
  X4 + 7*X3  6*X2  X1 + Z
 ,
 5
  X4 + 7*X3  6*X2  X1 + Z
 },
 5
 {X4=0,
 32*X3  11*X2 + 4*X1 + Z  40
 ,
 6
 32*X3  11*X2 + 4*X1 + Z  40
 },
 6
 12
 {X3=,
 7
 7*X2  20*X1 + Z + 32
 ,
 16
 7*X2  20*X1 + Z + 32
 },
 16
 4
 {X2=,
 7
 20*X1  Z  32
 MAX(12*X1  Z  8,,0),
 7
  12*X1 + 3*Z + 32
 },
 11
 7*Z + 60 2*Z + 36 3*Z + 32
 {X1=0,0,MIN(,,)},
 72 19 12
  60  60
 {Z=,,INF}}
 7 7
 \end{verbatim}
 Remark: The operators $>$ and $<$ currently are not handled by the
 system, because in many cases there is no algebraic solution for extremal
 problems with these operators. For example ${x>0}$ has no algebraic solution.
 \section{Symbolic Interface}
 The function {\tt linineq0} offers an interface to the algorithm for symbolic
 mode operation:
 \begin{center} {\tt linineq0(prob,vars,dir,rec)} \end{center}
 where
 \begin{description}
 \item[prob] list (untagged) of linear algebraic expressions
 $(e_1 e_2 \ldots e_n)$ which do NOT contain any relational
 operator; the problem to be solved then is
 $e_1 \ge 0, \ldots , e_n \ge 0$
 \item[vars] list of variables (kernels); the variable list must be
 complete; otherwise an error will occur.
 \item[dir] {\tt nil} or a list of the form
 {\tt ( ( var$_1$ . mm$_1$ ) (var$_2$ . mm$_2$ ) ... )}
 where the $var_i$ are variables and the mmi are either
 {\tt MAX} or {\tt MIN}.
 \item[rec] if not {\tt nil}, the formal bounds for the intermediate
 intervals are collected. They are available in the
 fluid variable {\tt LININEQRECORD!*}: the value of this
 variable is a list, where each element corresponds
 to one element of {\bf vars} in the same sequence. Each
 element is a list with the lower bound and the
 upperbound as algebraic (prefix) expression.
 \end{description}
 The result is {\tt NIL} (if the system is inconsistent) or a list of the form
 {\tt ((var$_1$ . val$_1$) (var$_2$ . val$_2$) ... (var$_n$ . val$_n$))}
 where the val$_i$ are algebraic (prefix) expressions, that are integers
 or quotients of integers if no domain mode is selected.
 \end{document}
