Incluant une Journée industrielle de l'optimisation
HEC Montréal, 7  9 mai 2012
JOPT2012
HEC Montréal, 7 — 9 mai 2012
TD6 Conception de réseaux / Network Design
8 mai 2012 15h30 – 17h10
Salle: Société canadienne des postes
Présidée par Babacar Thiongane
4 présentations

15h30  15h55
Modeling a ScenarioBased Network Design Problem in an Open Distribution Web Context
This research studies network deployment strategies in a Physical Internet enabled open distribution web where companies can exploit a widely dispersed set of open storage facilities. Under uncertainty, a scenariobased approach is proposed to model this strategic design problem and an approximate solution approach is under development to solve it.

15h55  16h20
SlopeScaling Heuristic for a Service Network Design with Resource Constraints
In this paper, we present the first slopescaling algorithm heuristic column generation approach with cyclebased formulation for a service network design with resource constraints. The heuristic includes column generation idea plus a fast heuristic as its core components. The experiment shows that the result is able to identify feasible and high quality solutions for the studied hard problem.

16h20  16h45
Capacitated Network Design with Facility Location
We consider the Capacitated Connected Facility Location Problem which arises in the design of last mile telecommunication networks. It combines the capacitated network design problem (CNDP) with the singlesource capacitated facility location problem (SSCFLP). We develop a basic integer
programming model based on multicommodity flows. Based on valid inequalities for the subproblems, CNDP and SSCFLP, we derive several (new) classes of valid inequalities for the CapConFL. We use them in a branchandcut framework and show the efficiency of our approach on a set of benchmark instances. 
16h45  17h10
Relaxations for the RWA Problem
This work deals with solving the Routing and Wavelength Assignment problem where the number
of accepted connections is to be maximized. Lagrangean decomposition as well as Lagrangean
relaxation are studied for both nodearc formulations and arcpath formulation. It is shown that
relaxing the demand constraints yields an edgedisjoint path problem with profits that is NPhard,
while the Lagrangean problem obtained when the clash constraints are relaxed becomes a shortest
path problem or a 01 linear knapsack problem, depending on the formulation used. Moreover, it
is shown that the Lagrangean decomposition is not stronger than the Lagrangean relaxation of the
demand constraints. We also propose a subgradient algorithm to solve the Lagrangean dual obtained
by relaxing the clash constraints. Numerical results demonstrate a high quality of Lagrangean dual
bounds with fast computation time.