1

I am studying the linear programming and stuck with the following two problems. I don't have any clues how to convert programs with absolute terms into a linear program. I highly appreciate your help.

  1. $min f(x)= 5 \lvert x-3\rvert + 2 \lvert x-5\rvert +3 \lvert x-9\rvert$

  2. $min f(x)= \lvert x-y-7\rvert + \lvert 2x+3y-5\rvert + \lvert 3x+7+1\rvert$

N1227
  • 11
  • Split each one up into cases, eg in the first one there are 4 cases, depending on the value of x, ie whether it's less than 3, between 3 and 5, between 5 and 9, and greater than 9 – danimal Apr 26 '15 at 15:38

1 Answers1

1

Here how you should proceed in general:

$$ min \sum_i | x + b_i | $$

you first introduce some auxiliary variables

$$ \begin{array}{ll} min & \sum_i y_i \\ s.t. & \\ & y_i\geq |x + b_i| \quad \forall i=1\ldots\end{array}$$

Then you can convert easily each constraint:

$$y_i\geq |x+b_i|$$

is equivalent to

$$y_i\geq x_i+ b, y_i\geq -x -b_i.$$

AndreaCassioli
  • 932