On Cutting Plane Algorithms for Nonlinear Binary Optimization

This is the authors' abstract. We don't add key points for this paper.

The cutting plane method is known to converge for concave discrete maximization problems. This paper introduces a new condition for convergence that is weaker than concavity, allowing for extensions to generalized concave cases such as quasiconcavity and pseudoconcavity. More significantly, the new convergence condition enables the use of smaller penalty values in the standard concave reformulation technique for general nonconcave problems, yielding stronger cuts and faster convergence. In concave cases, this condition can even be applied to “deconcavify” concave problems to enhance convergence speed. Numerical results show that exploiting the new convergence condition can yield substantial computational improvements for complex, large-scale discrete optimization problems with up to one thousand variables.