We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.
|Original language||English (US)|
|Title of host publication||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Editors||Michael Junger, Gerhard Reinelt, Giovanni Rinaldi|
|Number of pages||13|
|ISBN (Print)||3540005803, 9783540005803|
|State||Published - 2003|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|