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
关键词：
摘要：
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.