Santiago Chile

Talk is given at Discrette Optimization Session at IFORS 2023

The current state-of-the-art algorithms for solving nonlinear binary optimization problems have two challenges: they are mostly restricted to convex/concave settings and they struggle with large problems. We revisit the outer approximation method, a widely used solution methodology for convex/concave discrete optimization, to a more general nonconvex framework; this involves deriving a new convergence condition allowing for generalized concave cases, such as quasiconcavity and pseudoconcavity, and rigorous convergence analysis quantifying the number of points removed by each cutting plane. We exploit these results to devise a new strategy to accelerate the convergence of the algorithms. We apply the results in certain classes of non-concave binary quadratic programming problems, including cardinality Boolean quadratic programming problems. The new approach outperforms the traditional methods and can handle some instances of up to a thousand variables.