4 présentations

• 
  15h30 - 15h55

  Modeling a Scenario-Based Network Design Problem in an Open Distribution Web Context

  • Helia Sohrabi, prés., Université Laval
  • Walid Klibi, Bordeaux Management School
  • Benoît Montreuil, Université Laval

  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 scenario-based approach is proposed to model this strategic design problem and an approximate solution approach is under development to solve it.

• 
  15h55 - 16h20

  Slope-Scaling Heuristic for a Service Network Design with Resource Constraints

  • Vu Duc Minh, prés., Université de Montréal
  • Teodor Gabriel Crainic, Université du Québec à Montréal
  • Michel Toulouse, Oklahoma State University
  • Mike Hewitt, Rochester Institute of Technology

  In this paper, we present the first slope-scaling algorithm heuristic column generation approach with cycle-based 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

  • Stefan Gollowitzer, prés., University of Vienna
  • Bernard Gendron, Université de Montréal, CIRRELT
  • Ivana Ljubic, University of Vienna

  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 single-source capacitated facility location problem (SSCFLP). We develop a basic integer
  programming model based on multi-commodity 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 branch-and-cut framework and show the efficiency of our approach on a set of benchmark instances.

• 
  16h45 - 17h10

  Relaxations for the RWA Problem

  • Babacar Thiongane, prés., ADOPT - Kronos

  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 node-arc formulations and arc-path formulation. It is shown that
  relaxing the demand constraints yields an edge-disjoint path problem with profits that is NP-hard,
  while the Lagrangean problem obtained when the clash constraints are relaxed becomes a shortest
  path problem or a 0-1 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.