4 Presentations

• 
  10:30 AM - 10:55 AM

  Efficient Exact Methods for the Capacitated Vehicle Routing Problem (CVRP)

  • Marcus Poggi, presenter, Pontifícia Universidade Católica do Rio de Janeiro
  • Eduardo B. Uchoa, Universidade Federal Fluminense

  We present a discussion over the current most efficient exact methods for solving the CVRP. In common is the set partitioning formulation. The main issues are: the choice of routes to price (q-routes, ng-routes or elementary routes); to add or not non-robust cuts and to branch or to enumerate routes.

• 
  10:55 AM - 11:20 AM

  Improved Primal Simplex (IPS) Strongly Polynomial for Certain Types of Network Problems

  • Jean-Bertrand Gauthier, GERAD - HEC Montréal
  • Jacques Desrosiers, presenter, GERAD, HEC Montréal
  • Marco E. Lübbecke, RWTH Aachen University

  Inspired by recent advances in coping with degeneracy in the primal simplex method, we apply the \emph{Improved Primal Simplex} (IPS) method to specific network instances, namely the assignment and max flow problems. We show it echoes the mechanics of the minimum mean cycle-canceling algorithm of Goldberg and Tarjan (1989). The strongly polynomial algorithm operates as follows. Each iteration works on the \emph{residual network} to retrieve a negative mean cost cycle indicating a strictly improving direction. We take the time to analyze the behavior of the algorithm through key concepts of the complexity analysis.

• 
  11:20 AM - 11:45 AM

  A Contraction-Expansion Algorithm for the Capacitated Minimum Cost Flow Problem

  • Jean-Bertrand Gauthier, presenter, GERAD - HEC Montréal
  • Jacques Desrosiers, GERAD, HEC Montréal
  • Marco E. Lübbecke, RWTH Aachen University

  We show that a slight modification of the \emph{Improved Primal Simplex} (IPS) used for solving degenerate linear programs (Raymond et~al. 2010, Elhallaoui et~al. 2011) results in a strongly polynomial algorithm for solving arbitrary capacitated minimum cost network flow problems. The key additive is that the traditional residual network is contracted with respect to non-degenerate variables. Acceleration strategies used in the implementation are also discussed and involve the concepts established in IPS such as compatibility and independent cycles. Moreover, we bias the algorithm around the residual capacities and the reduced cost of previous iterations to speed up the search.

• 
  11:45 AM - 12:10 PM

  Efficient Elementary and Restricted Non-Elementary Shortest Path Problems with Resource Constraints

  • Rafael Martinelli, presenter, GERAD - Polytechnique Montréal
  • Diego Pecin, Pontifícia Universidade Católica do Rio de Janeiro
  • Marcus Poggi, Pontifícia Universidade Católica do Rio de Janeiro

  Our work aims at efficiently solving the Shortest Path Problem with Resource Constraints (SPPRC) with restricted non-elementary routes and also the Elementary SPPRC. We adapt the Decremental State-Space Relaxation to the SPPRC using completion bounds. We show how to extend this approach by dynamically rebuilding the ng-sets to obtain only elementary routes.