COLUMN GENERATION BASED ALGORITHMS FOR THE CAPACITATED MULTI-LAYER NETWORK DESIGN WITH UNSPLITTABLE DEMANDS
AUTOR(ES)
Benhamiche, Amal, Mahjoub, A. Ridha, Perrot, Nancy, Uchoa, Eduardo
FONTE
Pesqui. Oper.
DATA DE PUBLICAÇÃO
2017-09
RESUMO
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-Wolfe decomposition schemes to solve it. More precisely, an arc-flow formulation is given for the problem and used to derive two different paths formulations: non-aggregated and aggregated. The former contains two families of path variables and requires a double column generation procedure to solve it, while the latter relies on a single path variable with a specific structure. These alternative modeling approaches induce two Branch-and-Price algorithms that allow to solve the problem efficiently for several classes of instances.
Documentos Relacionados
- Non-Linear Unsteady Aerodynamic Response Approximation Using Multi-Layer Functionals
- Engenharia de trafego multi-camada para grades
- Treatment of aortic dissecting aneurysm involving visceral arteries with multi-layer bare stents
- Numerical Study on the Projectile Impact Resistance of Multi-Layer Sandwich Panels with Cellular Cores
- Effect of a multi-layer infection control barrier on the micro-hardness of a composite resin