SYMPHONY

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 25 articles )

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

1 2 next

  1. Borndörfer, Ralf; Schenker, Sebastian; Skutella, Martin; Strunk, Timo: PolySCIP (2016)
  2. Gassmann, Horand; Ma, Jun; Martin, Kipp: Communication protocols for options and results in a distributed optimization environment (2016)
  3. Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (2015)
  4. Ceselli, A.; Righini, G.; Tresoldi, E.: Modeling and solving profitable location and distribution problems (2013)
  5. Gkortsilas, Dimitrios; Zaroliagis, Christos: An experimental study of bicriteria models for robust timetabling (2013)
  6. Guzelsoy, Menal; Nemhauser, George; Savelsbergh, Martin: Restrict-and-relax search for 0-1 mixed-integer programs (2013)
  7. Lang, Jan Christian; Widjaja, Thomas: OREX-J: Towards a universal software framework for the experimental analysis of optimization algorithms (2013)
  8. Vanderbeck, François: Branching in branch-and-price: A generic scheme (2011)
  9. Groër, Chris; Golden, Bruce; Wasil, Edward: A library of local search heuristics for the vehicle routing problem (2010)
  10. Novoa, Clara; Storer, Robert: An approximate dynamic programming approach for the vehicle routing problem with stochastic demands (2009)
  11. Secomandi, Nicola; Margot, François: Reoptimization approaches for the vehicle-routing problem with stochastic demands (2009)
  12. Xu, Yan; Ralphs, Ted K.; Ladányi, László; Saltzman, Matthew J.: Computational experience with a software framework for parallel integer programming (2009)
  13. Chandran, Bala; Raghavan, S.: Modeling and solving the capacitated vehicle routing problem on trees (2008)
  14. Kallehauge, Brian: Formulations and exact algorithms for the vehicle routing problem with time windows (2008)
  15. Munapo, Elias: The variable sequencing approach: A solution to the capital budget allocation model (2007)
  16. Fortz, B.; Mahjoub, A.R.; McCormick, S.T.; Pesneau, P.: Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut (2006)
  17. Linderoth, Jeffrey T.; Ralphs, Ted K.: Noncommercial software for mixed-integer linear programming (2006)
  18. Ralphs, Ted K.; Saltzman, Matthew J.; Wiecek, Margaret M.: An improved algorithm for solving biobjective integer programs (2006)
  19. Wang, Bow-Yaw: On the satisfiability of modular arithmetic formulae (2006)
  20. Fügenschuh, Armin; Martin, Alexander: Computational integer programming and cutting planes (2005)

1 2 next