Papers › An Exact Algorithm for Large-scale Non-convex Quadratic Facility Location
An Exact Algorithm for Large-scale Non-convex Quadratic Facility Location
C. A. Zetina, I. Contreras, S. Jayaswal
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study a general class of quadratic capacitated p-location problems facility location problems with single assignment where a non-separable, non-convex, quadratic term is introduced in the objective function to account for the interaction cost between facilities and customer assignments. This problem has many applications in the field of transportation and logistics where its most well-known special case is the single-allocation hub location problem and its many variants. The non-convex, binary quadratic program is linearized by applying a reformulation-linearization technique and the resulting continuous auxiliary variables are projected out using Benders decomposition. The obtained Benders reformulation is then solved using an exact branch-and-cut algorithm that exploits the underlying network flow structure of the decomposed separation subproblems to efficiently generate strong Pareto-optimal Benders cuts. Additional enhancements such as a matheuristic, a partial enumeration procedure, and variable elimination tests are also embedded in the proposed algorithmic framework. Extensive computational experiments on benchmark instances (with up to 500 nodes) and on a new set of instances (with up to 1,000 nodes) of four variants of single-allocation hub location problems confirm the algorithm's ability to scale to large-scale instances.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections