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