A generic branch-and-price code


BaPCod is a C++ library implementing a generic branch-cut-and-price solver.

BaPCod is a prototype academic code which offers a “black-box” implementation of the method: - the input is the set of constraints and variables of the MIP in its natural/ compact formulation; - the user specifies which of these constraints and variables define the subsystems on which the decomposition is based (it is handy to test different decompositions); - the reformulation is automatically generated by the code, without any input from the user to define master columns, their reduced cost, pricing problem, or Lagrangian bound; - a default column generation procedure is implemented that relies on an underlying LP/MIP solver to handle master and subproblem but the user can define a specific solver for the pricing problem; - a branching scheme that preserves the pricing problem structure is offered by default, it runs based on priorities and directives specified by the user on the original variables; - the user can specify custom cut generation callbacks and custom branching callbacks; - preprocessing, restricted master and diving primal heuristics, some stabilization techniques, and strong branching are available for use; - one can use the VRPSolver extension, which includes a resource constrained shortest path problem (RCSP) solver, and some families of robust and non-robust cut separation and branching functors; - these components can be used to devise state-of-the-art branch-cut-and-price algorithms for vehicle routing and related problems.

Language. C++

Status. Available for academics.