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

Standard

An improved cut-and-solve algorithm for the single-source capacitated facility location problem. / Gadegaard, Sune Lauth; Klose, Andreas; Nielsen, Lars Relund.

In: EURO Journal on Computational Optimization, Vol. 6, No. 1, 2018, p. 1-27.

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

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@article{181a52dac9cb4bd1a6db328f9868cee3,
title = "An improved cut-and-solve algorithm for the single-source capacitated facility location problem",
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 = "Capacitated facility location, Cut-and-solve, Cutting planes, Facility location, KNAPSACK POLYTOPE, LAGRANGEAN RELAXATION, Local branching, OPTIMIZATION, PRICE ALGORITHM, SEARCH, SOURCE CONSTRAINTS, Single-sourcing",
author = "Gadegaard, {Sune Lauth} and Andreas Klose and Nielsen, {Lars Relund}",
year = "2018",
doi = "10.1007/s13675-017-0084-4",
language = "English",
volume = "6",
pages = "1--27",
journal = "EURO Journal on Computational Optimization",
issn = "2192-4406",
publisher = "Springer",
number = "1",

}

RIS

TY - JOUR

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

AU - Gadegaard, Sune Lauth

AU - Klose, Andreas

AU - Nielsen, Lars Relund

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Capacitated facility location

KW - Cut-and-solve

KW - Cutting planes

KW - Facility location

KW - KNAPSACK POLYTOPE

KW - LAGRANGEAN RELAXATION

KW - Local branching

KW - OPTIMIZATION

KW - PRICE ALGORITHM

KW - SEARCH

KW - SOURCE CONSTRAINTS

KW - Single-sourcing

UR - http://www.scopus.com/inward/record.url?scp=85042286914&partnerID=8YFLogxK

U2 - 10.1007/s13675-017-0084-4

DO - 10.1007/s13675-017-0084-4

M3 - Journal article

VL - 6

SP - 1

EP - 27

JO - EURO Journal on Computational Optimization

JF - EURO Journal on Computational Optimization

SN - 2192-4406

IS - 1

ER -