Simultaneous convexification for the planar obnoxious facility location problem

Nonconvex quadratically constrained optimization problems are known to be difficult to solve to global optimality and constitute a very active area of research. We identify a particularly challenging such problem arising from applications in planar obnoxious facility location. Even small instances of this problem are currently beyond the capabilities of modern global optimization solvers, owing to weak convex relaxations. We address this limitation by characterizing the simultaneous convex hull of the intersection of reverse convex reduced domains inherent in these problems. We derive tighter variable bounds and optimality-based cutting planes based on this simultaneous convexification method, along with an efficient algorithm to compute them. Given an optimal solution, our approach embedded within a spatial branch-and-bound scheme is able to certify global optimality two orders of magnitude faster compared to state-of-the-art general purpose global optimization solvers also initialized to the optimal solution. Even when provided with no starting point, it is competitive with global solvers initialized to the global solution. Using our method, global optimality is certified for the first time for 24 open instances from the literature. For three of these instances, we improve upon the previously best known solutions.