# Linear programing: Multiple slack variables

I have to convert folloving problem: $$min\{|x_1| + |x_2| + |x_3|\ |\ \text{conditions..}\}$$

to linear program (if it is possible). Since $|x_1| = max\{x_1,-x_1\}$, i have:

$$x_1 \leq z_1$$ $$-x_1 \leq z_1$$

$$x_2 \leq z_2$$ $$-x_2 \leq z_2$$

$$x_3 \leq z_3$$ $$-x_3 \leq z_3$$

where $z_{1,2,3}$ are slack variables.

How will minimalization function look like? I have to minimalize all three slack variables, but linear program can minimalize only one variable, am I right? Is the answer, that the problem is not solvable by LP?

• I think you're still missing slack variables. You want to ensure that the all variables are nonnegative. – Mark Fantini Dec 19 '13 at 21:26

Let $|x_i| = x_i^+ +x_i^-$, with $x_i^+, x_i^- \geq 0$. Your objective becomes
$$\min \sum_{i=1}^3 (x_i^+ + x_i^-)$$
subject to $x_i = x_i^+ - x_i^-$, for $i=1,2,3$.
Clearly, your original $x_i$ has to be free, otherwise there is no need for the absolute value. Note that once you solve it, exactly one of the $x_i^+$ and $x_i^-$ will be $0$ and the other one will be non-negative, for a fixed $i$.