A Randomized CostSmoothing Approach for Optical NetworkDesign
Balazs Dezsot · 2007
Indesigning infocommunications networks thecostofoptical ports andlinks growsindiscrete steps asthe capacity isbeing increased. Thiscostfunction isreferred toasstep function orstaged capacity cost. Ifasequential algorithm isusedtodesign thenetworks itoften results insub-optimal solution duetotheso called long pathproblem, wheretheweighted shortest pathalgorithms rather choose verylongpaths where suchlinks arechosen where noadditional capacity step(andtherefore noadditional coststep) hastobemade. Inthis paper wepropose andcompare methods that perform randomised smoothing ofthese staged capacity cost functions toallow decomposition ofthenetwork design problem toasequence ofweighted shortest path searches, that isthemostly usedapproach. Theproblem canbeinterpreted asanUnsplittable Multi-Commodity FlowProblem withstaged capacity costs.