Premium
Multiperiod network design with incremental routing
Author(s) -
Lardeux Benoit,
Nace Dritan,
Geffard Jérôme
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20171
Subject(s) - routing (electronic design automation) , computer science , dimensioning , network planning and design , mathematical optimization , multi commodity flow problem , curse of dimensionality , flow network , computer network , mathematics , engineering , machine learning , aerospace engineering
In this paper, we study a special case of multiperiod network design (MPND) problems, multiperiod network design with incremental routing (MPNDI), as applied to the transmission layer of an optical network. We optimize simultaneously the network architecture and the link dimensioning under discrete cost functions in order to route all traffic demands in line with traffic growth over a discrete time horizon. Because of operational requirements, routing paths used at a given period to route some traffic demands have to be preserved over subsequent periods; this is called incremental routing with respect to incremental flow. To handle the high dimensionality, a compact formulation omitting explicitly written flow variables is given. We examine the dominant polyhedron of the incremental multicommodity flow and provide a polyhedral study of it. Finally, a solution approach taking advantage of the polyhedral structure of MPNDI is proposed, and computational results for a range of instances with 8 and 10 nodes are provided. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 109–117 2007