Department of Economics and Business Economics

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Documents

DOI

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.
Original languageEnglish
JournalEURO Journal on Computational Optimization
Volume6
Issue1
Pages (from-to)1-27
Number of pages27
ISSN2192-4406
DOIs
Publication statusPublished - 2018

    Research areas

  • Capacitated facility location, Cut-and-solve, Cutting planes, Facility location, KNAPSACK POLYTOPE, LAGRANGEAN RELAXATION, Local branching, OPTIMIZATION, PRICE ALGORITHM, SEARCH, SOURCE CONSTRAINTS, Single-sourcing

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 112396896