13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ could you please add a reference to the hardness result, please? $\endgroup$ – Marco Lübbecke Jul 1 '19 at 23:39
  • $\begingroup$ 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. $\endgroup$ – Ryan Cory-Wright Jul 1 '19 at 23:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Marco Lübbecke Jul 2 '19 at 6:35
  • $\begingroup$ 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. $\endgroup$ – Ryan Cory-Wright Jul 2 '19 at 13:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Johan Löfberg Jul 4 '19 at 18:52
15
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.