2016 Optimization Days

HEC Montréal, Québec, Canada, 2 — 4 May 2016

Schedule Authors My Schedule

MA3 Network Design

May 2, 2016 10:30 AM – 12:10 PM

Location: EY

Chaired by Sagnik Das

4 Presentations

  • 10:30 AM - 10:55 AM

    Relief network design under congestion

    • Jyotirmoy Dalal, presenter, Indian Institute of Management Udaipur
    • Navneet Vidyarthi, Concordia University

    We present a three-echelon (evacuation source, shelter, and DC) relief network design problem considering congestion at links. In addition to locating shelters and DCs, our model attempts to obtain a system-optimal multi-period evacuation and distribution policy to ensure a timely service to all, alleviating suffering due to congestion.

  • 10:55 AM - 11:20 AM

    Cut selection strategies for Benders decomposition in uncapacitated multicommodity network design

    • Carlos Zetina, presenter, CIRRELT
    • Ivan Contreras, Concordia University
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

    In this talk we compare cut selection strategies for choosing Benders optimality cuts in the uncapacitated multicommodity network design problem. Additionally we test different strategies for selecting core points to use in the Magnanti-Wong subproblem and study their effect on the overall algorithm performance. We perform computational experiments to compare their convergence rate, number of iterations and CPU time.

  • 11:20 AM - 11:45 AM

    A Learning-Based Matheuristic Approach for Stochastic Network Design Problems with Uncertain Demands

    • Fatemeh Sarayloo, presenter, Université de Montréal
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Walter Rei, Université du Québec à Montréal

    Network design problems (NDPs) define an important class of discrete optimization problems that naturally appear in several applications including transportation, logistics and telecommunications. Introducing stochastic demand into a network design model produces solutions qualitatively different from those stemming from deterministic models. In order to overcome these challenges and also considering the large-scale nature of the problem, we propose a mat-heuristic framework based on learning techniques that specifically designed for stochastic problems to efficiently explore the search space.

  • 11:45 AM - 12:10 PM

    Outer-approximation algorithms for multicommodity network design problem with congestion

    • Sagnik Das, presenter, University of Illinois at Urbana-Champaign
    • Sachin Jayaswal, Indian Institute of Management Ahmedabad
    • Navneet Vidyarthi, Concordia University
    • Bernard Gendron, Université de Montréal, CIRRELT

    We account for congestion in the fixed charge multicommodity network design problem by modelling the arcs as M/M/1 queues (with stochastic arrival and service times). We present a nonlinear mixed integer programming formulation of the model. Outer approximation based exact solution approach is proposed and computational results are presented.