An improved cut-and-solve algorithm for the single-source capacitated facility location problem

Sune Lauth Gadegaard (), Andreas Klose and Lars Relund Nielsen
Additional contact information
Sune Lauth Gadegaard: Aarhus University
Andreas Klose: Aarhus University
Lars Relund Nielsen: Aarhus University

EURO Journal on Computational Optimization, 2018, vol. 6, issue 1, No 1, 27 pages

Abstract: Abstract In this paper, we present an improved cut-and-solve algorithm for the single-source capacitated facility location problem. The algorithm consists of three phases. The first phase strengthens the integer program by a cutting plane algorithm to obtain a tight lower bound. The second phase uses a two-level local branching heuristic to find an upper bound, and if optimality has not yet been established, the third phase uses the cut-and-solve framework to close the optimality gap. Extensive computational results are reported, showing that the proposed algorithm runs 10–80 times faster on average compared to state-of-the-art problem-specific algorithms.

Keywords: Facility location; Capacitated facility location; Single-sourcing; Cutting planes; Local branching; Cut-and-solve; 90-08; 90C10; 90C11; 90B80 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-017-0084-4 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:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0084-4

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

DOI: 10.1007/s13675-017-0084-4

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().