Workshop on Branch-Cut-and-Price (BCP) algorithms which are obtaining the best results on the exact solution of several combinatorial problems, in particular, those related to Big Data, Learning, Cyber Security, Energy Saving or Vehicle Routing Problems.
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.