Maximize sum of absolute values over a box set

Question

I am interested in the following linear problem: $$ \begin{array}{cl} \max & |a_{11} x_1 + a_{12} x_2| + |a_{21} x_1 + a_{22} x_2| \\ \mathrm{s.t.} & 0 \leq x_1 \leq b_1 \\ & 0 \leq x_2 \leq b_2. \end{array} $$ Do we have any clever ways to derive the tractable reformulation of this problem?

I am thinking of using some binary variables to indicate the signs of $|a_{11} x_1 + a_{12} x_2|$ and $|a_{21} x_1 + a_{22} x_2|$ as follows. $$ \begin{array}{cl} \min & t_1 + t_2 + t_3 + t_4 \\ \mathrm{s. t.} & t_1 \geq \Big([(a_{11} + a_{21}) \vee 0] b_1 + [(a_{12} + a_{22})\vee0]b_2\Big) \Big(-1 + I_{11} + I_{12}\Big) \\ & a_{11} b_1 {\bf 1}_{\{a_{11} + a_{21} \,> 0\}} + a_{12} b_2 {\bf 1}_{\{a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{11} \\ & a_{11} b_1 {\bf 1}_{\{a_{11} + a_{21} \,> 0\}} \leq M \cdot I_{11} \\ & a_{12} b_2 {\bf 1}_{\{a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{11} \\ & a_{21} b_1 {\bf 1}_{\{a_{11} + a_{21} \,> 0\}} + a_{22} b_2 {\bf 1}_{\{a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{12} \\ & a_{21} b_1 {\bf 1}_{\{a_{11} + a_{21} \,> 0\}} \leq M \cdot I_{12} \\ & a_{22} b_2 {\bf 1}_{\{a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{12} \\ & t_2 \geq \Big([(-a_{11} + a_{21}) \vee 0] b_1 + [(-a_{12} + a_{22})\vee0]b_2\Big) \Big(-1 + I_{21} + I_{22}\Big) \\ & -a_{11} b_1 {\bf 1}_{\{-a_{11} + a_{21} \,> 0\}} - a_{12} b_2 {\bf 1}_{\{-a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{21} \\ & -a_{11} b_1 {\bf 1}_{\{-a_{11} + a_{21} \,> 0\}} \leq M \cdot I_{21} \\ & -a_{12} b_2 {\bf 1}_{\{-a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{21} \\ & a_{21} b_1 {\bf 1}_{\{-a_{11} + a_{21} \,> 0\}} + a_{22} b_2 {\bf 1}_{\{-a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{22} \\ & a_{21} b_1 {\bf 1}_{\{-a_{11} + a_{21} \,> 0\}} \leq M \cdot I_{22} \\ & a_{22} b_2 {\bf 1}_{\{-a_{12} + a_{22} \,> 0\}} \leq M \cdot I_{22} \\ & \quad \vdots \quad (\text{Similar for } I_{31}, I_{32}, I_{41}, I_{42}) \\ & I_{11}, I_{12}, \ldots, I_{42} \in \{0, 1\}, \quad t_1, t_1, \ldots, t_4 \geq 0, \end{array} $$ where $M$ is a number big enough, ${\bf 1}_{\{\cdot\}}$ is a indicator function which is one if $\{\cdot\}$ is valid.

This method works but is complicated, how to improve it to make it more elegant?

Answer 1

Without the absolute values, $f(x, y) = a x_1 + b x_2$ is just a linear map, so $\{(x, y, f(x, y))\}$ is just a plane in 3d. There's some line where its zero. If we take the absolute values, there's a side of the line where $|f| = f$ and one where $|f| = -f$. So $\{(x, y, |f(x, y)|)\}$ is therefore, two planes, meeting at a line where $|f|= 0$, and postive elsewhere.

In this simpler case, its easy to see that the extreme points of the block are, ie the corners, are where the maxima must occur.

Now, add two of these things together. If neither of the zero lines pass through the block, its easy to see that we just have to check the corners, as we're just looking at a plane. If one or more of the lines pass through the block, we have a function whose graph is the union of two or more plane fragments. I claim that the maximizing point must be at or between one of the three nonzero corners (nb: the functions values along any ray starting at zero is nondecreasing, so if we have an internal maxima, we can draw the ray through that point and get a larger value at the boundary).

A bit more argument should show you that you must be at one of the corners (The values along this boundary are continuous and form straight lines, with the ends of any straight line segment being a corner or a place where one of our zero lines intersect the boundary. I claim if we are in the middle of a line segment, one of its ends will be better, and if we are on one of the zero lines, then either we are at a local minima, or moving in one way or the other will increase the function value (this last part is handwavy, but if you think on it, I think you'll find an algebraically tight reason for it)).

Answer 2

The simplest approach is to solve four LPs, with the following constraints that allow the removal of the absolute values in the objective:

• $a_{11}x_1+a_{12}x_2 \ge 0$, $a_{21}x_1+a_{22}x_2 \ge 0$
• $a_{11}x_1+a_{12}x_2 \ge 0$, $a_{21}x_1+a_{22}x_2 \le 0$
• $a_{11}x_1+a_{12}x_2 \le 0$, $a_{21}x_1+a_{22}x_2 \ge 0$
• $a_{11}x_1+a_{12}x_2 \le 0$, $a_{21}x_1+a_{22}x_2 \le 0$

---

Alternatively, you can introduce binary variables $y_1$ and $y_2$ and nonnegative variables $z_1$ and $z_2$ to represent the absolute values, replace the objective function with $z_1+z_2$, and impose the following four implications: \begin{align} y_1 = 0 &\implies z_1 = a_{11}x_1+a_{12}x_2 \\ y_1 = 1 &\implies z_1 = -a_{11}x_1-a_{12}x_2 \\ y_2 = 0 &\implies z_2=a_{21}x_1+a_{22}x_2 \\ y_2 = 1 &\implies z_2=-a_{21}x_1-a_{22}x_2 \end{align} The following linear big-M constraints do that: \begin{align} 0\le a_{11}x_1+a_{12}x_2 -z_1 &\le M_1 y_1 \\ 0\le -a_{11}x_1-a_{12}x_2 -z_1 &\le M_2 (1-y_1) \\ 0\le a_{21}x_1+a_{22}x_2 -z_2&\le M_3 y_2 \\0\le -a_{21}x_1-a_{22}x_2 -z_2 &\le M_4 (1-y_2) \end{align}

Answer 3

We can consider the following tractable reformulation: $$ \begin{array}{cl} \min & t_1 + t_2 + t_3 + t_4 \\ \mathrm{s. t.} & t_1 \geq (a_{11} + a_{21}) b_1 {\bf 1}_{a_{11} + a_{21} \,\geq\, 0} + (a_{12} + a_{22}) b_1 {\bf 1}_{a_{12} + a_{22} \,\geq\, 0} \\ & t_2 \geq (-a_{11} + a_{21}) b_1 {\bf 1}_{-a_{11} + a_{21} \,\geq\, 0} + (-a_{12} + a_{22}) b_1 {\bf 1}_{-a_{12} + a_{22} \,\geq\, 0} \\ & t_3 \geq (a_{11} - a_{21}) b_1 {\bf 1}_{a_{11} - a_{21} \,\geq\, 0} + (a_{12} - a_{22}) b_1 {\bf 1}_{a_{12} - a_{22} \,\geq\, 0} \\ & t_4 \geq (-a_{11} - a_{21}) b_1 {\bf 1}_{-a_{11} - a_{21} \,\geq\, 0} + (-a_{12} - a_{22}) b_1 {\bf 1}_{-a_{12} - a_{22} \,\geq\, 0}. \end{array} $$ This method works if the number of $|\cdot|$ is small.