Decomposition Branching for Mixed Integer Programming

• 成果类型: Article; Early Access
• 署名作者: Yildiz, Baris; Boland, Natashia; Savelsbergh, Martin
• 署名单位: Koc University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2210
• 发表日期: 2022
• 关键词: Mixed Integer Programming; Combinatorial Optimization; branch-and-bound; decomposition algorithms; set covering; Facility Location

摘要

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.