COLUMN GENERATION BASED ALGORITHMS FOR THE CAPACITATED MULTI-LAYER NETWORK DESIGN WITH UNSPLITTABLE DEMANDS

ABSTRACT We investigate a variant of the Multi-Layer Network Design problem where minimum cost capacities have to be installed upon a virtual layer in such a way that (i) a set of traffic demands can be routed AND (ii) each capacity (subband) is assigned a route in the physical layer. The traffic demands cannot be splitted along several paths (nor even several capacities installed on the same link), which makes the problem even more difficult. In this paper, we present new non-compact ILP formulations to model the problem and provide column generation procedures, based on different Dantzig-Wol...