Speeding up column generation for robust wireless network planning

The wireless network planning problem consists of base station placement and traffic node assignment to base stations. To incorporate traffic demand uncertainties, we follow the Γ-robustness approach by Bertsimas and Sim. In this paper, we develop a branch-and-price algorithm, with the aim to enhanc...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Grit Claßen, Arie M.C.A. Koster, Anke Schmeink
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	90B18 90C11 90-08 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/6ac47a5f87ae4c67bb0c68d3c6e5b35b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6ac47a5f87ae4c67bb0c68d3c6e5b35b
record_format	dspace
spelling	oai:doaj.org-article:6ac47a5f87ae4c67bb0c68d3c6e5b35b2021-12-02T05:00:37ZSpeeding up column generation for robust wireless network planning2192-440610.1007/s13675-013-0013-0https://doaj.org/article/6ac47a5f87ae4c67bb0c68d3c6e5b35b2013-11-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000216https://doaj.org/toc/2192-4406The wireless network planning problem consists of base station placement and traffic node assignment to base stations. To incorporate traffic demand uncertainties, we follow the Γ-robustness approach by Bertsimas and Sim. In this paper, we develop a branch-and-price algorithm, with the aim to enhance the solution process and improve the dual bounds. Instead of assigning individual traffic nodes to base stations, subsets of traffic nodes are assigned to a base station, implying that the pricing problem essentially is a robust knapsack. Since a straightforward implementation does not give satisfactory results, we present techniques, which we apply to the master problem as well as to the pricing problems, to improve the performance. We investigate the effectiveness of these techniques in an extensive computational study.Grit ClaßenArie M.C.A. KosterAnke SchmeinkElsevierarticle90B1890C1190-08Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 3, Pp 253-281 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B18 90C11 90-08 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B18 90C11 90-08 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Grit Claßen Arie M.C.A. Koster Anke Schmeink Speeding up column generation for robust wireless network planning
description	The wireless network planning problem consists of base station placement and traffic node assignment to base stations. To incorporate traffic demand uncertainties, we follow the Γ-robustness approach by Bertsimas and Sim. In this paper, we develop a branch-and-price algorithm, with the aim to enhance the solution process and improve the dual bounds. Instead of assigning individual traffic nodes to base stations, subsets of traffic nodes are assigned to a base station, implying that the pricing problem essentially is a robust knapsack. Since a straightforward implementation does not give satisfactory results, we present techniques, which we apply to the master problem as well as to the pricing problems, to improve the performance. We investigate the effectiveness of these techniques in an extensive computational study.
format	article
author	Grit Claßen Arie M.C.A. Koster Anke Schmeink
author_facet	Grit Claßen Arie M.C.A. Koster Anke Schmeink
author_sort	Grit Claßen
title	Speeding up column generation for robust wireless network planning
title_short	Speeding up column generation for robust wireless network planning
title_full	Speeding up column generation for robust wireless network planning
title_fullStr	Speeding up column generation for robust wireless network planning
title_full_unstemmed	Speeding up column generation for robust wireless network planning
title_sort	speeding up column generation for robust wireless network planning
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/6ac47a5f87ae4c67bb0c68d3c6e5b35b
work_keys_str_mv	AT gritclaßen speedingupcolumngenerationforrobustwirelessnetworkplanning AT ariemcakoster speedingupcolumngenerationforrobustwirelessnetworkplanning AT ankeschmeink speedingupcolumngenerationforrobustwirelessnetworkplanning
_version_	1718400832894926848

Speeding up column generation for robust wireless network planning

Ejemplares similares