Speeding Up Column Generation for Robust Wireless Network Planning

Authors

G. Claßen, A. M. C. A. Koster, A. Schmeink,

Abstract

        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 the pricing problem essentially being 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.

BibTEX Reference Entry 

@article{ClKoSc13b,
	author = {Grit Cla{\"s}en and Arie Marinus Catharinus Antonius Koster and Anke Schmeink},
	title = "Speeding Up Column Generation for Robust Wireless Network Planning",
	pages = "253-281",
	journal = "EURO Journal on Computational Optimization",
	volume = "1",
	number = "3",
	doi = 10.1007/s13675-013-0013-0,
	month = Jul,
	year = 2013,
	hsb = hsb999910320871 ,
	}

Downloads

 Download paper  Download bibtex-file

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights there in are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.