1

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?

Filip
  • 141

1 Answers1

2

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

baudolino
  • 1,885