Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

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 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.