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

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	SuneLauth Gadegaard, Andreas Klose, LarsRelund Nielsen
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90-08 90C10 90C11 90B80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/1ebdfb8a351d4dc493c6ea3773674fd7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:1ebdfb8a351d4dc493c6ea3773674fd7
record_format	dspace
spelling	oai:doaj.org-article:1ebdfb8a351d4dc493c6ea3773674fd72021-12-02T05:01:05ZAn improved cut-and-solve algorithm for the single-source capacitated facility location problem2192-440610.1007/s13675-017-0084-4https://doaj.org/article/1ebdfb8a351d4dc493c6ea3773674fd72018-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000939https://doaj.org/toc/2192-4406In 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.SuneLauth GadegaardAndreas KloseLarsRelund NielsenElsevierarticle90-0890C1090C1190B80Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 1, Pp 1-27 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-08 90C10 90C11 90B80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-08 90C10 90C11 90B80 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 SuneLauth Gadegaard Andreas Klose LarsRelund Nielsen An improved cut-and-solve algorithm for the single-source capacitated facility location problem
description	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.
format	article
author	SuneLauth Gadegaard Andreas Klose LarsRelund Nielsen
author_facet	SuneLauth Gadegaard Andreas Klose LarsRelund Nielsen
author_sort	SuneLauth Gadegaard
title	An improved cut-and-solve algorithm for the single-source capacitated facility location problem
title_short	An improved cut-and-solve algorithm for the single-source capacitated facility location problem
title_full	An improved cut-and-solve algorithm for the single-source capacitated facility location problem
title_fullStr	An improved cut-and-solve algorithm for the single-source capacitated facility location problem
title_full_unstemmed	An improved cut-and-solve algorithm for the single-source capacitated facility location problem
title_sort	improved cut-and-solve algorithm for the single-source capacitated facility location problem
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/1ebdfb8a351d4dc493c6ea3773674fd7
work_keys_str_mv	AT sunelauthgadegaard animprovedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem AT andreasklose animprovedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem AT larsrelundnielsen animprovedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem AT sunelauthgadegaard improvedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem AT andreasklose improvedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem AT larsrelundnielsen improvedcutandsolvealgorithmforthesinglesourcecapacitatedfacilitylocationproblem
_version_	1718400816654581760

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

Ejemplares similares