On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

• 成果类型: Article
• 署名作者: Awate, Yogesh; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
• 署名单位: Carnegie Mellon University; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0775-z
• 发表日期: 2015
• 页码: 459-489
• 关键词: valid inequalities; triangle; split

摘要

We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type 2 triangle (resp. Type 3 triangle; quadrilateral) inequalities, are all within a factor of of the integer hull, and provide examples showing that the approximation factor is not less than . There is no fixed approximation ratio for split or Type 1 triangle inequalities however.