Minimizing the sum of absolute values with a linear solver

Question

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

Answer 1

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.

Answer 2

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 \\$$