Valid inequalities for MIPs and group polyhedra from approximate liftings

• 成果类型: Article
• 署名作者: Richard, Jean-Philippe P.; Li, Yanjun; Miller, Lisa A.
• 署名单位: Purdue University System; Purdue University; Purdue University System; Purdue University; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0190-9
• 发表日期: 2009
• 页码: 253-277
• 关键词: lifted inequalities; cutting planes; integer; facets

摘要

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation.