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