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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2013
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/6ac47a5f87ae4c67bb0c68d3c6e5b35b |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|