# Sum of Max terms maximization

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.

• could you please add a reference to the hardness result, please? – Marco Lübbecke Jul 1 '19 at 23:39
• Maximizing a convex quadratic form over $\Vert x \Vert_\infty \leq 1$ is equivalent to binary quadratic optimization, which is NP-hard (so the problem is "hard" without needing a sum). The asker may have been referring to this. – Ryan Cory-Wright Jul 1 '19 at 23:46
• Hi @Ryan, only because this is a special case of a hard problem doesn't make it a hard problem. Google doesn't give me an answer either, maybe I am searching for the wrong terms; this is why I ask for a reference. – Marco Lübbecke Jul 2 '19 at 6:35
• If you allow the sum to have $n \geq 1$ terms then isn't the max sum problem a more general version of the hard problem where $n=1$? In any case, I agree that a reference from OP would be nice. – Ryan Cory-Wright Jul 2 '19 at 13:14
• Judging from your question on the YALMIP forum, I interpret this as you actually ask how YALMIP models the max operator in a nonconvex setting, i.e. the question is really not about any specific solver, but modelling. The MILP model YALMIP implements is explained on yalmip.github.io/tutorial/logicprogramming/#functions, and it essentially the model described in Ryans answer. – Johan Löfberg Jul 4 '19 at 18:52

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.