BaPCod is a prototype code that solves Mixed Integer Programs (MIP) by application of a Dantzig-Wolfe reformulation technique. The reformulated problem is solved using a branch-and-price (column generation) algorithm. The specificity of this prototype is to offer 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 MIP solver to handle master and subproblem but the user can upload a specific subproblem solver; 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; default primal heuristics and preprocessing features are under developments.
Keywords for this software
References in zbMATH (referenced in 6 articles )
Showing results 1 to 6 of 6.
- Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Automatic Dantzig-Wolfe reformulation of mixed integer programs (2015)
- Sadykov, Ruslan; Vanderbeck, François: Column generation for extended formulations (2013)
- Wang, Jiadong; Ralphs, Ted: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization (2013)
- Bergner, Martin; Caprara, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Partial convexification of general mips by Dantzig-Wolfe reformulation (2011)
- Vanderbeck, François: Branching in branch-and-price: A generic scheme (2011)
- Joncour, C.; Michel, S.; Sadykov, R.; Sverdlov, D.; Vanderbeck, F.: Column generation based primal heuristics (2010)