# Turning the program with absolute terms into the linear program

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$

• 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

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

• Then what become the decision variables? Shouldn't i decide x first to solve for y? – N1227 Apr 26 '15 at 16:35
• You need all of them. – AndreaCassioli Apr 26 '15 at 19:27