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.