Methode zum Auffinden einer Lösung eines Systems

\begin{eqnarray}\begin{equation} a_{i}^{T}\cdot x\leq b_{i},i=1\ldots,s \end{equation}\end{eqnarray}

Dabei werden die einzelnen Variablen schrittweise eliminiert. Um beispielsweise x₁ zu eliminieren, werden in allen Ungleichungen der jeweilige Koeffizient von x₁ zu 0, −1 oder 1 normiert (durch Multiplikation der entsprechenden Ungleichung mit einer geeigneten positiven Zahl). Das so entstehende System laute

\begin{eqnarray}\begin{align} &\max\{\tilde{a}^{T}_{j}\cdot(x_{2},\ldots,x_{n})-\tilde{b_{j}};m_{1}+1\leq j \leq m_{2}\}\\ &\leq x_{1}\leq \min\{-\tilde{a}^{T}_{i}\cdot (x_{2},\ldots,x_{n})+\tilde{b}_{i};1\leq t\leq m_{1}\}. \end{align}\end{eqnarray}

\begin{eqnarray}\begin{equation} \tilde{a}^{T}_{i}\cdot(x_{2},\ldots,x_{n})-\tilde{b}_{j}\leq -\tilde{a}^{T}_{i}\cdot(x_{2},\ldots,x_{n})+\tilde{b}_{i} \end{equation}\end{eqnarray}

Analog verfährt man mit den restlichen Variablen weiter. Geometrisch entspricht dieses Vorgehen einer Projektion. Das Verfahren ist im worst case-Verhalten nicht effizient, da bei jedem Eliminationsschritt die Anzahl der Ungleichungen auf m₁ · m₂ + m₃ anwächst, was sich auf eine exponentielle Anzahl auswachsen kann.