2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.)

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.