Decomposition Branching for Mixed Integer Programming

Barış Yıldız (), Natashia Boland () and Martin Savelsbergh ()
Additional contact information
Barış Yıldız: Department of Industrial Engineering, Koc University, Istanbul 34450, Turkey
Natashia Boland: H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Martin Savelsbergh: H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2022, vol. 70, issue 3, 1854-1872

Abstract: We introduce a novel and powerful approach for solving certain classes of mixed integer programs (MIPs): decomposition branching . Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized p -median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach.

Keywords: Optimization; mixed integer programming; combinatorial optimization; branch-and-bound; decomposition algorithms; set covering; facility location (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2210 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:3:p:1854-1872

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().