5
$\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$
16
$\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$
  • $\begingroup$ This seems to solve the problem. Thank you! $\endgroup$ – user3040169 Jan 1 '14 at 0:13
7
$\begingroup$

This is really a comment on littlO's answer. Comment box is too small for this. $$ \min (|a1 x + b1 y - c1| + |a2 x + b2 y - c2| + |a3 x + b3 y - c3|), 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$

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.