Branch, cut, and price (BCP) is an LP-based branch and bound technique for solving large-scale discrete optimization problems (DOPs). In BCP, both cuts and variables can be generated dynamically throughout the search tree. The ability to handle constantly changing sets of cuts and variables allows these algorithms to undertake the solution of very large-scale DOPs; however, it also leads to interesting implementational challenges. These lecture notes, based on our experience over the last six years with implementing a generic framework for BCP called SYMPHONY (Single- or Multi-Process Optimization over Networks), address these challenges. They are an attempt to summarize some of what we and others have learned about implementing BCP, both sequential and parallel, and to provide a useful reference for those who wish to use BCP techniques in their own research. SYMPHONY, the software from which we have drawn most of our experience, is a powerful, state-of-the-art library that implements the generic framework of a BCP algorithm. The library’s modular design makes it easy to use in a variety of problem settings and on a variety of hardware platforms. All library subroutines are generic – their implementation does not depend on the problem-setting. To develop a full-scale BCP algorithm, the user has only to specify a few problem-specific methods such as cut generation. The vast majority of the computation takes place within a “black box,” of which the user need have no knowledge. Within the black box, SYMPHONY performs all the normal functions of branch and cut – tree management, LP solution, cut pool management, as well as inter-process comm

References in zbMATH (referenced in 36 articles )

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

1 2 next

  1. Maher, Stephen J.: Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework (2021)
  2. Tahernejad, Sahar; Ralphs, Ted K.; DeNegre, Scott T.: A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation (2020)
  3. Shinano, Yuji; Heinz, Stefan; Vigerske, Stefan; Winkler, Michael: FiberSCIP -- a shared memory parallelization of SCIP (2018)
  4. Herrera, Juan F. R.; Salmerón, José M. G.; Hendrix, Eligius M. T.; Asenjo, Rafael; Casado, Leocadio G.: On parallel branch and bound frameworks for global optimization (2017)
  5. Borndörfer, Ralf; Schenker, Sebastian; Skutella, Martin; Strunk, Timo: PolySCIP (2016)
  6. Gassmann, Horand; Ma, Jun; Martin, Kipp: Communication protocols for options and results in a distributed optimization environment (2016)
  7. Morrison, David R.; Jacobson, Sheldon H.; Sauppe, Jason J.; Sewell, Edward C.: Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning (2016)
  8. Munapo, Elias; Kumar, Santosh: Knapsack constraint reformulation: a new approach that significantly reduces the number of sub-problems in the branch and bound algorithm (2016)
  9. Santos, Haroldo G.; Toffolo, Túlio A. M.; Gomes, Rafael A. M.; Ribas, Sabir: Integer programming techniques for the nurse rostering problem (2016)
  10. Berthold, Timo; Hendel, Gregor: Shift-and-propagate (2015)
  11. Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (2015)
  12. Mason, Luke R.; Mak-Hau, Vicky H.; Ernst, Andreas T.: A parallel optimisation approach for the realisation problem in intensity modulated radiotherapy treatment planning (2015)
  13. Ceselli, A.; Righini, G.; Tresoldi, E.: Modeling and solving profitable location and distribution problems (2013)
  14. Gkortsilas, Dimitrios; Zaroliagis, Christos: An experimental study of bicriteria models for robust timetabling (2013)
  15. Guzelsoy, Menal; Nemhauser, George; Savelsbergh, Martin: Restrict-and-relax search for 0-1 mixed-integer programs (2013)
  16. Lang, Jan Christian; Widjaja, Thomas: OREX-J: Towards a universal software framework for the experimental analysis of optimization algorithms (2013)
  17. Vanderbeck, François: Branching in branch-and-price: A generic scheme (2011)
  18. Dorta, I.; León, C.; Rodríguez, C.: Performance analysis of branch-and-bound skeletons (2010)
  19. Groër, Chris; Golden, Bruce; Wasil, Edward: A library of local search heuristics for the vehicle routing problem (2010)
  20. Novoa, Clara; Storer, Robert: An approximate dynamic programming approach for the vehicle routing problem with stochastic demands (2009)

1 2 next