How to transform absolute values in the objective function of a linear program?

Referring to this, in the Numerical Example, clearly $$x_3$$ is useless (looks like the page is not well maintained). I find the explanation confusing though. If I simply have an objective function
min | t - 23 |
then 23 is the optimal solution

when I use U = | t - 23|
s.t. - t + 23 $$\leq$$ U $$\leq$$ t -23

then it seems like 22 is illegal, which is not the point, and, what is U? is it | t - 23 | or t -23 because this is not given in the last line of the numerical example in the link.

Actually, I have,
min p = 2 * | $$t_{1} - q_{1}$$ | + 3 * | $$t_{1} - q_{1}$$ | + 2 * | $$t_{2} - q_{2}$$ |
s.t. $$t_{1} + t_{2}$$ = 10

The $$q_i$$ are given. How do I linearize such a problem?

1 Answer

Let $$U = t_{14} - q_{14}$$ and $$V = t_{13} - q_{13}$$ and solve the four systems

min p = 2 U + 3 U + 2 V
s.t. U>= 0, V>=0,
U = t_{14} - q_{14},
V = t_{13} - q_{13}, and
t_{13} - t_{14} = 10

min p = -2U - 3U + 2V
s.t. U< 0, V>=0,
U = t_{14} - q_{14},
V = t_{13} - q_{13}, and
t_{13} - t_{14} = 10

min p = 2 U + 3 U - 2 V
s.t. U>= 0, V<0,
U = t_{14} - q_{14},
V = t_{13} - q_{13}, and
t_{13} - t_{14} = 10

min p = -2U - 3U - 2V
s.t. U< 0, V<0,
U = t_{14} - q_{14},
V = t_{13} - q_{13}, and
t_{13} - t_{14} = 10


This splits into cases along the piecewise definition of the absolute value and uses that, for instance, $$2|V| = 2V$$ when $$V \geq 0$$ and $$2|V| = -2V$$ when $$V < 0$$ (and similarly for $$U$$).

• I'm surprised that this is necessary. I only wrote part of the objective function. t, q are 1-15. If the number of systems is quadratic in the number of variables, then I must be doing it wrong. – Julius Baer Oct 27 '19 at 7:24
• @JuliusBaer : You want to do linear programming with absolute values. How many linear parts are there in an absolute value? Also, this is not quadratic. With three absolute values, there are eight LPs to run; this is exponential growth. – Eric Towers Oct 27 '19 at 7:26
• ouch... let me check – Julius Baer Oct 27 '19 at 7:30
• @JuliusBaer : Sometimes, one can show that a single one of these inequalities excludes any feasible solutions. But this is special enough that you shouldn't expect it. – Eric Towers Oct 27 '19 at 7:31
• looks like 20 absolute values – Julius Baer Oct 27 '19 at 7:39