A Geometric Perspective on Lifting

• 成果类型: Article
• 署名作者: Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo
• 署名单位: University of Padua; Carnegie Mellon University; University of London; London School Economics & Political Science
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0916
• 发表日期: 2011
• 页码: 569-577
• 关键词: minimal-inequalities; integer programs

摘要

Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to lift these inequalities for integral nonbasic variables by considering maximal lattice-free convex sets in a higher dimensional space. We apply this approach to several examples. In particular, we identify cases in which the lifting is unique.