Valid inequalities for mixed integer linear programs

被引：119

作者：

Cornuejols, Gerard ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA

[2] Univ Aix Marseille, Fac Sci Luminy, LIF, F-13288 Marseille, France

来源：

MATHEMATICAL PROGRAMMING | 2008年 / 112卷 / 01期

关键词：

mixed integer linear program; lift-and-project; split cut; Gomory cut; mixed integer rounding; elementary closure; polyhedra; union of polyhedra;

D O I：

10.1007/s10107-006-0086-0

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：3 / 44

页数：42

共 58 条

[1] Reduce-and-split cuts:: Improving the performance of mixed-integer gomory cuts [J].