Advanced

Link Load Balancing Optimization of Telecommunication Networks: a Column Generation based Approach

Santos, D.; Sousa, A.; Alvelos, F. and Pioro, Michal LU (2010) 14th International Telecommunications Network Strategy and Planning Symposium (NETWORKS) In [Host publication title missing]
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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
[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)
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
2015-05-06 14:33:45
date last changed
2016-10-13 04:48:13
@misc{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},
  isbn         = {978-1-4244-6704-4},
  language     = {eng},
  pages        = {6},
  publisher    = {ARRAY(0xa417a28)},
  series       = {[Host publication title missing]},
  title        = {Link Load Balancing Optimization of Telecommunication Networks: a Column Generation based Approach},
  url          = {http://dx.doi.org/10.1109/NETWKS.2010.5624911},
  year         = {2010},
}