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.

References in zbMATH (referenced in 18 articles )

Showing results 1 to 18 of 18.
Sorted by year (citations)

  1. Maher, Stephen J.: Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework (2021)
  2. Pessoa, Artur Alves; Poss, Michael; Sadykov, Ruslan; Vanderbeck, François: Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty (2021)
  3. Basso, S.; Ceselli, Alberto; Tettamanzi, Andrea: Random sampling and machine learning to understand good decompositions (2020)
  4. Bulhões, Teobaldo; Sadykov, Ruslan; Subramanian, Anand; Uchoa, Eduardo: On the exact solution of a large class of parallel machine scheduling problems (2020)
  5. Marques, Guillaume; Sadykov, Ruslan; Deschamps, Jean-Christophe; Dupas, Rémy: An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem (2020)
  6. Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo; Vanderbeck, François: A generic exact solver for vehicle routing and related problems (2020)
  7. Queiroga, Eduardo; Frota, Yuri; Sadykov, Ruslan; Subramanian, Anand; Uchoa, Eduardo; Vidal, Thibaut: On the exact solution of vehicle routing problems with backhauls (2020)
  8. Clautiaux, François; Guillot, Jérémy; Pesneau, Pierre: Exact approaches for solving a covering problem with capacitated subtrees (2019)
  9. Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo; Vanderbeck, François: A generic exact solver for Vehicle Routing and related problems (2019)
  10. Bulhões, Teobaldo; Sadykov, Ruslan; Uchoa, Eduardo: A branch-and-price algorithm for the minimum latency problem (2018)
  11. Khaniyev, Taghi; Elhedhli, Samir; Erenay, Fatih Safa: Structure detection in mixed-integer programs (2018)
  12. Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo: Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems (2018)
  13. 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)
  14. Sadykov, Ruslan; Vanderbeck, François: Column generation for extended formulations (2013)
  15. Wang, Jiadong; Ralphs, Ted: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization (2013)
  16. Bergner, Martin; Caprara, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Partial convexification of general mips by Dantzig-Wolfe reformulation (2011)
  17. Vanderbeck, François: Branching in branch-and-price: A generic scheme (2011)
  18. Joncour, C.; Michel, S.; Sadykov, R.; Sverdlov, D.; Vanderbeck, F.: Column generation based primal heuristics (2010)