Valid inequalities for mixed integer linear programs

• 成果类型: Article; Proceedings Paper
• 署名作者: Cornuejols, Gerard
• 署名单位: Carnegie Mellon University; Aix-Marseille Universite
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0086-0
• 发表日期: 2008
• 页码: 3-44
• 关键词: gomory cuts; intersection cuts; cutting planes; split cuts; closure; optimization; relaxations; polyhedron; rank

摘要

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength.