An abstract model for branch-and-cut

Aleksandr M. Kazachkov, Pierre Le Bodic, Sriram Sankaranarayanan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Branch-and-cut is the dominant paradigm for solving a wide range of mathematical programming problems—linear or nonlinear—combining intelligent 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.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022 Eindhoven, The Netherlands, June 27–29, 2022 Proceedings
EditorsKaren Aardal, Laura Sanità
Place of PublicationCham Switzerland
PublisherSpringer
Pages333-346
Number of pages14
ISBN (Electronic)9783031069017
ISBN (Print)9783031069000
DOIs
Publication statusPublished - 2022
EventInternational Conference on Integer Programming and Combinatorial Optimization 2022 - Eindhoven, Netherlands
Duration: 27 Jun 202229 Jun 2022
Conference number: 23rd
https://link.springer.com/book/10.1007/978-3-031-06901-7 (Proceedings)
https://www.ipco2022.com/home#:~:text=The%2023rd%20Conference%20on,of%20Mathematics%20and%20Computer%20Science. (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13265
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integer Programming and Combinatorial Optimization 2022
Abbreviated titleIPCO 2022
Country/TerritoryNetherlands
CityEindhoven
Period27/06/2229/06/22
Internet address

Keywords

  • Branch-and-bound
  • Cutting planes
  • Integer programming

Cite this