Branching on general disjunctions

• 成果类型: Article
• 署名作者: Karamanov, Miroslav; Cornuejols, Gerard
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0332-3
• 发表日期: 2011
• 页码: 403-436
• 关键词: lift-and-project; basis reduction; 0-1 programs; integer; variables; algorithm

摘要

This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relaxation. The procedure is tested on instances from the literature. Experiments show that, for a majority of the instances, the enumeration tree obtained by branching on these general disjunctions has a smaller size than the tree obtained by branching on variables, even when variable branching is performed using full strong branching.