# Linear Programming Transformations

What is the process of performing a transformation from a given problem to another linear programming problem such that the transformed problem has an optimal solution iff the initial problem has a solution. I've learned about reductions (working with complexity), and the question seems quite similar, but now that the optimal keyword is included, I know that it can't be exactly like a reduction.

For reference, here is the question that has spurred my own question:

Consider the linear inequalities $L0$ in a finite number of unknowns ${x_1,\ldots,x_n}$ given below:

$$\sum_{j=1}^{n}a_{ij}x_j \le b_i \tag{L0}$$ for $i=1,2,\ldots,m$.

Show how to transform this into a linear program $L1$ so that $L1$ has an optimum solution if and only if $L0$ has a solution. Argue the correctness of your transformation.

I found this PDF really helpful. Look at the second system of equations.

The basic idea is to change it to a minimization problem. It's clear that for all $b_i \geq 0$ the original system $L0$ is solvable: just set all $x_i$ to $0$ for a feasible (not optimal, but feasible) solution.

But for $b_i$ < $0$ it is possible that $L0$ is not solvable. So for every i s.t. $b_i<0$ , introduce a new variable $w_i \geq 0$ Then the equation becomes: $$\sum_{j=1}^{n}a_{ij}x_j - w_i \le b_i \tag{L0}$$ for all i s.t. $b_i$ < $0$, and

$$\sum_{j=1}^{n}a_{ij}x_j \le b_i \tag{L0}$$ for all i s.t. $b_i \ge 0$.

So the minimization problem is to minimize $$Z=\sum_{i \text{ s.t. } b_i < 0}w_i$$

If minimum $Z=0$ (the optimum solution), $L0$ has a feasible solution (because you get back the original system.)

• Great PDF and explanation! – Alex Chumbley Mar 13 '14 at 19:00