Improved strategies for branching on general disjunctions

• 成果类型: Article
• 署名作者: Cornuejols, G.; Liberti, L.; Nannicini, G.
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; Carnegie Mellon University; Aix-Marseille Universite
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0333-2
• 发表日期: 2011
• 页码: 225-247
• 关键词: split; cuts

摘要

Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the enumeration tree is reduced by more than a factor of two, and computing time is comparable. On a few instances, the improvements are of several orders of magnitude in both number of nodes and computing time.