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.