Simultaneous convexification for the planar obnoxious facility location problem

Anatoliy Kuznetsov and Nikolaos V. Sahinidis ()
Additional contact information
Anatoliy Kuznetsov: Georgia Institute of Technology
Nikolaos V. Sahinidis: Georgia Institute of Technology

Journal of Global Optimization, 2025, vol. 92, issue 1, No 1, 20 pages

Abstract: Abstract 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.

Keywords: Simultaneous convexification; Cutting planes; Facility location; Reverse convex (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01464-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:1:d:10.1007_s10898-025-01464-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01464-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().