[Math] Minimizing the sum of absolute values with a linear solver

absolute valuelinear programming

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

Best Answer

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.

Related Question