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?

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

No. Linear programming optimizes one linear objective, which can be comprised of several variables. In your case, use the following trick.

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


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.