2
$\begingroup$

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.

$\endgroup$
2
$\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$
  • $\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$ – Brian Borchers Oct 5 '16 at 15:26
  • $\begingroup$ Many modeling systems can handle this problem transformation and others automatically. $\endgroup$ – Brian Borchers Oct 5 '16 at 17:45
1
$\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$

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.