Sum of Max terms maximization

Question

Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.

CPLEX and GUROBI solve these problems to global optimality. I don't know what method they use. I guess they first eliminate the obviously bad terms in the beginning and then follow a branching tree to optimize each combination. Is this correct? What methods do they use, how can I (roughly) learn about this?

I am interested in linear constraints. For example: \begin{align} \begin{array}{ll} \max & \left\{\max\{3x_1 + 4x_2 , -2x_1 +7x_2 \} + \max\{-x_1 + 6x_2 , 5x_1 +3x_2 \} \right\} \\ \text{st} & a \leq x_1 + x_2 \leq b \\ & x_1 \geq c, x_2 \geq d \end{array} \end{align}

I am solving a way bigger case.

Edit: Apparently, CPLEX and GUROBI solve Mixed Integer Optimization problems. The equivalent formulation as given in the accepted answer is being generated by YALMIP parser which I use.

Answer 1

If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.

Suppose that our objective is to maximize $$\sum_i g_i(x),$$ where each $g_i(x):=\max_j a_j^{i\top} x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $\theta_i$ such that $\theta_i \leq g_i(x)$, letting $z_{i,j}=1$ if the $j$th affine function in $g_i(x)$ is the largest at $x$, and maximizing the following problem: \begin{align*} \max \quad & \sum_i \theta_i\\ \text{s.t.} \quad & \theta_i \leq a_j^{i\top}x+b_j^i+M(1-z_{i,j}), \forall i, \forall j,\\ & \sum_j z_{i,j}=1, \forall i,\\ & z_{i,j} \in \{0, 1 \}, \forall i, \forall j. \end{align*} The combination of the big-M constraints and "objective pressure" ensures that $\theta_i=g_i(x)$ at optimality.

If the problem is larger, the above big-M approach won't give tight enough relaxations for branch-and-bound to perform well and we will need to think about using more complicated formulations. In this case, you should think about exploiting the structure of the problem, i.e., explicitly treating the problem as maximizing the sum of piecewise linear functions.

Tighter formulations than the generic big-M approach have been developed here.

I have no idea whether or not this approach is what CPLEX/Gurobi use.