6
$\begingroup$

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, but none of the fixes I've seen apply when you're trying to minimize a sum of several absolute values.

Specifically, I have 3 sets of constants ($a_1, a2,\ldots$; $\ b_1, b_2,\ldots$; & $\ c_1, c_2,\ldots$) and 2 variables ($x$ & $y$). The gist of my program is below.

$$\min (|a_1 x + b_1 y - c_1| + |a_2 x + b_2 y - c_2| + |a_3 x + b_3 y - c_3|)$$

such that

$$x + y = 1$$

$\endgroup$

2 Answers 2

18
$\begingroup$

You can introduce new variables $t_i$ and constraints $t_i \geq a_i x + b_i y - c_i$ and $t_i \geq -(a_i x + b_i y - c_i)$, and then minimize $\sum_i t_i$ subject to the new constraints and your additional constraints.

$\endgroup$
4
  • $\begingroup$ This seems to solve the problem. Thank you! $\endgroup$ Jan 1, 2014 at 0:13
  • $\begingroup$ don't you also need $t_i\geq 0$ ? $\endgroup$ Mar 2, 2023 at 8:30
  • $\begingroup$ @DimaPasechnik The constraints I mentioned already imply that $t_i \geq 0$. $\endgroup$
    – littleO
    Mar 2, 2023 at 8:55
  • $\begingroup$ ah, right. I was being silly, sorry. $\endgroup$ Mar 2, 2023 at 15:09
10
$\begingroup$

This is really a comment on littlO's answer. Comment box is too small for this. $$ \min (|a_1 x + b_1 y - c_1| + |a_2 x + b_2 y - c_2| + |a_3 x + b_3 y - c_3|), x+y = 1$$ is equivalent to $$ \min t_1 + t_2 + t_3 \text{ such that} \\ a_1 x + b_1 y -c_1 \le t_1 \\ a_1 x + b_1 y -c_1 \ge -t_1 \\ a_2 x + b_2 y -c_2 \le t_2\\ a_2 x + b_2 y -c_2 \ge -t_2 \\ a_3 x + b_3 y -c_3 \le t_3 \\ a_3 x + b_3 y -c_3 \ge -t_3 \\ x+y = 1 $$ This just expands on littleO's answer. Please give littleO the credit.

Edited: (typo revised) from: $$a_3 x + b_3 y -c_3 \le t_1 \\$$ to: $$a_3 x + b_3 y -c_3 \le t_3 \\$$

$\endgroup$

You must log in to answer this question.

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