Link Load Balancing Optimization of Telecommunication Networks: a Column Generation based Approach
Author
Summary, in English
This paper deals with optimal load balancing in telecommunication networks. For a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, we wish to determine the routing paths aiming at min-max optimization of link loads. To solve this problem, we propose a column (path) generation based heuristic. In the first step, we use column generation to solve a linear programming relaxation of the basic problem (obtaining a lower bound and a set of paths). In the second step, we apply a multi-start local search heuristic with path-relinking to the search space defined by the paths found in the first step. In order to assess the merits of this approach, we also implemented a search heuristic which is equivalent to the second step of the proposed one but with no constraints on the set of paths that can be used. Through a set of computational results, we show that the proposed heuristic is efficient in obtaining near optimal routing solutions within short running times. Moreover, the comparison of the two heuristics show that constraining the search space to the columns given by column generation gives better results since this solution space contains good quality solutions and, due to its size, enables to find them in short running times.
Department/s
Publishing year
2010
Language
English
Publication/Series
[Host publication title missing]
Document type
Conference paper
Publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
Topic
- Electrical Engineering, Electronic Engineering, Information Engineering
Conference name
14th International Telecommunications Network Strategy and Planning Symposium (NETWORKS)
Conference date
2010-09-27 - 2010-09-30
Conference place
Warsaw, Poland
Status
Published
ISBN/ISSN/Other
- ISBN: 978-1-4244-6704-4