Branch and Price for WDM Optical Networks with No Bifurcation of Flow

作     者：Raghavan, S. Stanojevic, Daliborka 

作者机构：Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (美国运筹学与管理学会计算杂志)

年 卷 期：2011年第23卷第1期

页      面：56-74页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：optical networks multilayer network design network flows mixed-integer programming models branch-and-price procedure 

摘      要：The second generation of optical networks with wavelength division multiplexing (WDM) is based on the notion of two layer networks, where the first layer represents a logical topology defined over the physical topology of optical fibers and the second layer represents multiple traffic requests combined (multiplexed) over the paths established in the logical topology. Because the design of both of these layers is challenging by itself, researchers have mainly focused on solving these problems either independently or in a sequential fashion. In this paper, we look at the WDM optical network design problem with nonbifurcated traffic flows and propose an exact branch-and-price procedure that simultaneously solves logical topology design and traffic routing over the established logical topology. The unique feature of the proposed algorithm is that it works with a row-incomplete mathematical formulation and two types of variables that exponentially grow in number with the problem size. We discuss computational issues related to the use of this procedure and propose two approximate branch-and-price procedures that can be used to obtain lower and upper bounds for this problem. Finally, we present the results of our computational experiments for two design objectives and alternative optical network settings.