@inproceedings{ed2d75bcdbfb4e4c8a98ea29371daf12,

title = "On the exact separation of mixed integer knapsack cuts",

abstract = "During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integer programming polyhedrons. However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed integer polyhedron, and either proves the point is in the convex hull of said polyhedron, or finds a separating hyperplane. The main feature of this algorithm is a specialized subroutine for solving the Mixed Integer Knapsack Problem which exploits cost and lexicographic dominance. Separating over the entire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.",

keywords = "Cutting plane algorithms, Integer programming",

author = "Ricardo Fukasawa and Marcos Goycoolea",

year = "2007",

doi = "10.1007/978-3-540-72792-7_18",

language = "English",

isbn = "9783540727910",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "225--239",

booktitle = "Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings",

note = "null ; Conference date: 25-06-2007 Through 27-06-2007",

}