Topics of SPOC20
Topics of the
"Autumn school on Advanced BCP Tools:
VRPSolver and Coluna"
Branch-Cut-and-Price (BCP) algorithms, based on the combination of column generation with cut separation, are obtaining the best results on the exact solution of several combinatorial problems, in particular, those related to Vehicle Routing Problem (VRP). However, devising and implementing a state-of-the-art BCP can be a very demanding task, measured on several work-months of a skilled team.
This school 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. VRPSolver can be downloaded at https://vrpsolver.math.u-bordeaux.fr
-
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.
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.