Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/26596
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKazachkov, Aleksandr M.-
dc.contributor.authorBodic, Pierre Le-
dc.contributor.authorSankaranarayanan, Sriram-
dc.date.accessioned2023-07-14T10:15:40Z-
dc.date.available2023-07-14T10:15:40Z-
dc.date.issued2023-06-30-
dc.identifier.citationKazachkov, A. M., Bodic, P. L., & Sankaranarayanan, S. (2023). An abstract model for branch and cut. Mathematical Programming. https://doi.org/10.1007/s10107-023-01991-zen_US
dc.identifier.issn14364646-
dc.identifier.urihttp://hdl.handle.net/11718/26596-
dc.description.abstractBranch and cut is the dominant paradigm for solving a wide range of mathematical programming problems—linear or nonlinear—combining efficient search (via branch and bound) and relaxation-tightening procedures (via cutting planes, or cuts). While there is a wealth of computational experience behind existing cutting strategies, there is simultaneously a relative lack of theoretical explanations for these choices, and for the tradeoffs involved therein. Recent papers have explored abstract models for branching and for comparing cuts with branch and bound. However, to model practice, it is crucial to understand the impact of jointly considering branching and cutting decisions. In this paper, we provide a framework for analyzing how cuts affect the size of branch-and-cut trees, as well as their impact on solution time. Our abstract model captures some of the key characteristics of real-world phenomena in branch-and-cut experiments, regarding whether to generate cuts only at the root or throughout the tree, how many rounds of cuts to add before starting to branch, and why cuts seem to exhibit nonmonotonic effects on the solution process.en_US
dc.language.isoenen_US
dc.publisherSpringer Linken_US
dc.relation.ispartofMathematical Programmingen_US
dc.subjectMathematical programming problemsen_US
dc.subjectLinear programmingen_US
dc.subjectNonlinear programmingen_US
dc.subjectBranch and bounden_US
dc.subjectRelaxation-tightening proceduresen_US
dc.subjectComputational experienceen_US
dc.subjectTheoretical explanationsen_US
dc.subjectBranching decisionsen_US
dc.subjectCutting decisionsen_US
dc.subjectReal-world phenomenaen_US
dc.subjectBranch-and-cut experimentsen_US
dc.subjectRounds of cutsen_US
dc.subjectNonmonotonic effectsen_US
dc.subjectCutting planesen_US
dc.titleAn abstract model for branch and cuten_US
dc.typeArticleen_US
Appears in Collections:Open Access Journal Articles

Files in This Item:
File Description SizeFormat 
An_abstract_model_for_branch_and_cut.pdf1.76 MBAdobe PDFView/Open


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.