# Linear programming: minimizing absolute values and formulate in LP

Look for $$x$$ that minimizes $$\sum_i| x – a_i|$$ with numbers $$a_1,\ldots, a_N$$ that are given and formulate this as a LP.

I have searched online and found that first of all this $$\sum_i| x – a_i|$$ should be made linear. The book that I have (aimms optimization modeling) didn't really intuitively help me to grasp how this can be done.

Here's a simple example to get you started:

$\min | x-3 |$

subject to

$x \leq 2$.

The key to formulating these problems is introducing auxilliary variables and additional constraints. Add the constraints

$t \geq (x-3)$

and

$t \geq -(x-3)$.

Since $|x-3|$ is either $+(x-3)$ or $-(x-3)$, these constraints ensure that

$t \geq | x-3|$.

Now, minimize $t$. This will ensure that $t$ is no bigger than $|x-3|$.
So, our problem is

$\min t$

subject to

$t \geq (x-3)$

$t \geq -(x-3)$

$x \leq 2$.

It's important to understand that this technique doesn't work to maximize $|x-3|$.

You can easily extend this to more than one absolute value term, but you'll need an additional variable for each term.

• You'd need a variable $t_{i}$ for each of the absolute value terms, with two inequalities ($t_{i} \geq (x-a_{i})$ and $t_{i} \geq -(x-a_{i})$, and the objective would be $\sum_{i} t_{i}$. – Brian Borchers Oct 5 '16 at 15:26
• Many modeling systems can handle this problem transformation and others automatically. – Brian Borchers Oct 5 '16 at 17:45

The objective with absolute value, can be written as follows

objective: $\min |x-3|$

$\Leftrightarrow$ objective:$\min \max(x-3,3-x)$

The linear programming with $\min \max(x-3,3-x)$ or $\max\min$ can be easily done. For example,

min $z$,

s.t. $t\geq x-3,$

$t\geq3-x$,

BTW, we provide another technique to solve the problem $\max \max (x-3,3-x)$. Introduce a big value M and auxiliary variable b1,b2.

$\max t$,

s.t. $t\leq x-3+M*b_1,$

$t\leq3-x+M*b_2$,

$b_1+b_2=1.$

$b_1,b_2\in Z$