Image de couverture
Atelier

Autumn school on advanced BCP tools : VRPSolver and Coluna

This workshop intends to:

  • Review the techniques introduced in the last 10 years that significantly increased the capabilities of BCP algorithms for VRPs: ng-routes, hierarchical strong branching, route enumeration, advanced implementation of dynamic programming labeling algorithms for pricing, fixing by reduced costs and rank-1 cuts with limited memory.
     
  • Introduce VRPSolver, a highly generic BCP algorithm for solving VRPs and related problems,that already includes all the above mentioned techniques. The VRPSolver model corresponding to a particular application is coded using Julia language. A typical model has less than 100 lines of code, so users can already have a good working algorithm in one day. Additional work on separation routines for problem specific cuts may be needed for top performance.
     
  • Discuss "creative modeling" on VRPSolver. Several problems that are not standard VRPs can be possibly modeled by using non-trivial transformations, obtaining quite good performances. Known examples include Generalized Assignment Problem, Bin Packing and Vector Packing Problems, Parallel Machine Scheduling and Robust VRP.
     
  • Present to the community the open-source Branch-Cut-and-Price (BCP) framework Coluna, that is being developed collaboratively in Julia language and is available under Mozilla Public Licence. VRPSolver currently uses a private BCP framework. Future versions of VRPSolver will be based on Coluna, allowing much more user control on the algorithm strategies. Coluna should also feature support for parallel computing.
     
  • Provide an overview of challenging future applications of VRPs.
     
  • Showcase BCPs for Graph Coloring problems.

Public: Researchers and PhD students. In particular, people from polyhedral combinatorics that may profit from having a practical way of using their cuts as part of an advanced BCP.

A hands-on tutorial will be given.

 Organizers

  • Sonia Haddad Vanier (SAMM, Université Paris 1 Panthéon-Sorbonne)
  • Pierre Fouilhoux (LIP6 Sorbonne Universite)
  • Fabio Furini (LAMSADE, University Paris-Dauphine)
  • Ivana Ljubic (ESSEC, Paris)
  • A. Ridha Mahjoub (LAMSADE, University Paris-Dauphine)
  • Eduardo Uchoa (Universidade Federal Fluminense)