#### linineq.tex9.3 KB Permalink History Raw

 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}