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$

  • $\begingroup$ 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 $\endgroup$ – 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.$$

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

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.