Link Load Balancing Optimization of Telecommunication Networks: a Column Generation based Approach
(2010) 14th International Telecommunications Network Strategy and Planning Symposium (NETWORKS)- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5366477
- author
- Santos, D. ; Sousa, A. ; Alvelos, F. and Pioro, Michal LU
- organization
- publishing date
- 2010
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- [Host publication title missing]
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 14th International Telecommunications Network Strategy and Planning Symposium (NETWORKS)
- conference location
- Warsaw, Poland
- conference dates
- 2010-09-27 - 2010-09-30
- external identifiers
-
- scopus:78650228745
- ISBN
- 978-1-4244-6704-4
- DOI
- 10.1109/NETWKS.2010.5624911
- language
- English
- LU publication?
- yes
- id
- 92252487-27e2-4ffa-b68c-8c15771089f9 (old id 5366477)
- date added to LUP
- 2016-04-04 11:51:38
- date last changed
- 2022-01-29 22:31:10
@inproceedings{92252487-27e2-4ffa-b68c-8c15771089f9,
abstract = {{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.}},
author = {{Santos, D. and Sousa, A. and Alvelos, F. and Pioro, Michal}},
booktitle = {{[Host publication title missing]}},
isbn = {{978-1-4244-6704-4}},
language = {{eng}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Link Load Balancing Optimization of Telecommunication Networks: a Column Generation based Approach}},
url = {{http://dx.doi.org/10.1109/NETWKS.2010.5624911}},
doi = {{10.1109/NETWKS.2010.5624911}},
year = {{2010}},
}