Including an Industrial Optimization Day
HEC Montréal, May 7  9, 2012
JOPT2012
HEC Montréal, May 7 — 9, 2012
TD6 Conception de réseaux / Network Design
May 8, 2012 03:30 PM – 05:10 PM
Location: Société canadienne des postes
Chaired by Babacar Thiongane
4 Presentations

03:30 PM  03:55 PM
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.

03:55 PM  04:20 PM
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.

04:20 PM  04:45 PM
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. 
04:45 PM  05:10 PM
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.