3
$\begingroup$

Look for $x$ that minimizes $$\sum\limits_{i = 1}^N| x – a_i |$$ with numbers $a_1, \dots, a_N$ that are given and formulate this as a linear program.


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.

$\endgroup$
1

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$ Oct 5, 2016 at 15:26
  • $\begingroup$ Many modeling systems can handle this problem transformation and others automatically. $\endgroup$ Oct 5, 2016 at 17:45
3
$\begingroup$

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$

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .