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 \\ Konrad-Zuse-Zentrum fuer
- Informationstechnik \\
- Heilbronner Str. 10 \\ D1000 Berlin 31 \\ Federal Republic of Germany \\
- melenk@sc.zib-berlin.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
- branch-and-bound 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
- branch-and-bound 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}
|