Valid inequalities for mixed integer linear programs |
| |
Authors: | Gérard Cornuéjols |
| |
Affiliation: | (1) Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;(2) LIF, Faculté des Sciences de Luminy, Université d’ Aix-Marseille, 13288 Marseille, France |
| |
Abstract: | 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. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894. |
| |
Keywords: | Mixed integer linear program Lift-and-project Split cut Gomory cut Mixed integer rounding Elementary closure Polyhedra Union of polyhedra |
本文献已被 SpringerLink 等数据库收录! |
|