Title: On the depth of cutting planesOn the depth of cutting planes
| Speaker: | Laurent Poirrier |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We tackle one of the most important open problems in computational integer programming: cut selection.
For four decades, cutting planes were believed to be useful only for structured combinatorial problems. This changed in 1995 when Balas, Ceria and Cornuéjols showed that Gomory cuts could helpfully strengthen the formulation of general integer programming problems. Since then, many other cut generation techniques have been developed, but their practical success has been moderate at best.A major issue is that many families of cuts are too large, and selecting only the good ones becomes difficult. Despite its critical importance, the cut selection problem has seen little theoretical attention. Furthermore, Dey and Molinaro recently noted that even when it did receive attention, ``these results have so far failed to directly help in actual cutting-plane selection.''
We propose a simple notion of ``cut depth'' that is intuitive and easy to work with. We show that it explains two properties of ``good''
cutting planes that have been previously observed computationally. For a given LP and an individual cut, the depth can be computed in polynomial time through an LP formulation. This is arguably still too costly, but the depth can be usefully approximated by exploiting corner relaxations; in which case it can be computed in closed form.
This talk will require no prior knowledge of cutting planes, and we will briefly cover the current state of cutting planes for general IP in practice. This is joint work with James Yu.