1
$\begingroup$

Begin Question

Are there any known algorithms for transforming a system of linear inequalities into a system of linear equalities? The resulting system is only allowed to use equality statements ($=$), not a mixture of ($\leq$) and ($=$).

End Question. Begin Example

For example, consider the following system of inequalities. This an example of input to our algorithm:

$$ \begin{array}{lllcccccccccc|c} 06 & * & x_1 & + & 3 & * & x_2 & + & 3 & * & x_3 & \leq & 8 & IEQ1 \\ 01 & * & x_1 & + & 1 & * & x_2 & + & 2 & * & x_3 & \leq & 1 & IEQ2 \\ 02 & * & x_1 & + & 0 & * & x_2 & + & 1 & * & x_3 & \leq & 2 & IEQ3 \\ 0 & * & x_1 & + & (-1) & * & x_2 & + & (-2) & * & x_3 & \leq & -2 & IEQ4 \\ (-12) & * & x_1 & + & (-2) & * & x_2 & + & (-2) & * & x_3 & \leq & -6 & IEQ5\\ 5 & * & x_1 & + & 0 & * & x_2 & + & 3 & * & x_3 & \leq & 99 & IEQ6\\ (-5) & * & x_1 & + & 0 & * & x_2 & + & (-3) & * & x_3 & \leq & -99 & IEQ7\\ \end{array} $$

The messy system given above is logically equivalent to the following system of equalities. The system of equalities is an example of algorithm output: $$ \begin{array}{rrrrrrrrrrr|l} 12 & * & x_1 & + & 5 & * & x_2 & + & 8 & * & x_3 = 12 & EQ1 \\ 5 & * & x_1 & + & 0 & * & x_2 & + & 3 & * & x_3 = 99 & EQ2 \end{array} $$

Next, we describe how the the system of equalities can be formed the original inequalities. This is not a general algorithm; it only works for the provided example.

First, create new inequalities $EQ1A$ and $EQ1B$ as follows:

$$ \begin{array}{rrrrrrrrrrr|l} EQ1A = 1 & * & IEQ1 & + & 2 & * & IEQ2 & + & 1 & * & IEQ3 \\ EQ1B = 3 & * & IEQ4 & + & 1 & * & IEQ5 \\ \end{array} $$

After that, we have: $$ \begin{array}{rrrrrrrrrrr|l} 12 & * & x_1 & + & 5 & * & x_2 & + & 8 & * & x_3 & \leq & 12 & EQ1A \\ (-12) & * & x_1 & + & (-5) & * & x_2 & + & (-8) & * & x_3 & \leq & -12 & EQ1B\\ 5 & * & x_1 & + & 0 & * & x_2 & + & 3 & * & x_3 & \leq & 99 & IEQ6\\ (-5) & * & x_1 & + & 0 & * & x_2 & + & (-3) & * & x_3 & \leq & -99 & IEQ7\\ \end{array} $$

Combining $\textrm{EQ1A}$ and $\textrm{EQ1B}$ gives us $\textrm{EQ1}$:
$$ \begin{array}{rrrrrrrrrrr|l} 12 & * & x_1 & + & 5 & * & x_2 & + & 8 & * & x_3 = 12 \end{array} $$

Combining $\textrm{IEQ6}$ and $\textrm{IEQ7}$ gives us $\textrm{EQ2}$:
$$ \begin{array}{rrrrrrrrrrr|l} 5 & * & x_1 & + & 3 & * & x_3 = 99 \end{array} $$

End Example. Begin Discussion of Auxiliary Variables

The algorithm is allowed to introduce a small number of new variables. If there were $n$ variables originally, we should have at most $n$, or $2*n$, or $3*n$ new variables.

For example, suppose that we have
$$ \begin{array}{rrrrrr} 4 & \leq & 3 & * & y_1 & + & 5 & * & y_2 & \leq & 10 \end{array} $$

Then we might introduce an auxiliary variable $\alpha$ such that we obtain: $$ \begin{array}{rrrrrrr} 3 * y_1 + 5 * y_2 + \alpha & = 10 \\ \alpha & \geq -6 \alpha & \leq 0 \end{array} $$

However, traditional slack variables are not that useful.

Traditionally, $$ x_{55} \leq 99 $$ would become $$ \begin{array}{rrrrrrrr} x_{55} + \alpha & = 99 \\ \alpha & \leq 0 \end{array} $$
$\alpha \leq 0$ is an in-equality, and we want equalities only in our final result.

End Discussion of Auxiliary Variables.

Begin Discussion on Existence of Solutions

In general, a system of inequalities cannot always be reduced to a systems of equalities. However, looking for an algorithm which works for the cases where it is possible.

End

$\endgroup$
  • 1
    $\begingroup$ $6x_1+3x_2+3x_3\le8$ looks better than $$6\quad*\quad x_1\quad+\quad3\quad*\quad x_2\quad+\quad3\quad*\quad x_3\quad\le\quad8$$ $\endgroup$ – Gerry Myerson Feb 12 at 3:18
  • 2
    $\begingroup$ If there were, linear algebra and linear programming would have total overlap, and they don't. If you relax the "linear equality" part, use quadratic slack variables instead, which are nonnegative by construction. $\endgroup$ – Rodrigo de Azevedo Feb 12 at 15:56
  • 1
    $\begingroup$ You might be interested in what can be done with Fourier-Motzkin elimination. However, the solution set of a system of linear equations is in general an affine subspace of $R^{n}$ and the feasible set of a linear system of inequalities is a polyhedron, so it's simply not possible to reduce every system of linear inequalities to a system of linear equations. $\endgroup$ – Brian Borchers Feb 13 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.