Absolute Value in Linear Programming

Question

Consider the problem;

$$\min \{5x_1 + 7 |x_2 − 10|\}$$

s.t.

$$|3x_1 + 9| + |x_2| ≤ 5$$

and I want to reformulate it as a linear programming problem. Any idea how to do that ?

Answer 1

First, divide the $x_1,x_2$ plane into four quadrants I, II, III, IV by the vertical line $x_1=-3$ and the horizontal line $x_2=0$. Then your constraints reduce to four inequalities, one for each of the four quadrants (numbered counter-clockwise in the same manner as the Cartesian plane).

$$ \text{I}: x_2\le -3x_1-4$$ $$\text{II}: x_2\le3x_1+14$$ $$\text{III}: x_2\ge-3x_1-14$$ $$\text{IV}: x_2\ge3x_1+4$$

Graphing these four inequalities reveals that the region over which one must minimize the expression is a diamond shaped region with vertices $\left(-\frac{4}{3},0\right)$, $(-3,5)$, $\left(-\frac{14}{3},0\right)$, $(-3,-5)$.

Since for all points in this region satisfy $x_2\le10$ the expression to be minimized reduces to

$$ 5x_1-7x_2+70$$