Solving Mixed Integer Programs with Gomory Cutting Planes

ARGOMENTI: Seminars Ph.D. Program

Wednesday 11 February 2009 h. 15:00, room 2AB/40
Arrigo ZANETTE (Ph.D. in Applied Math., Dip. Mat.)
"Solving Mixed Integer Programs with Gomory Cutting Planes"

Gomory cutting planes were first introduced by Gomory in 1958 to solve Integer and Mixed Integer ('60) Programs (MIP). However they were soon abandoned in favor of enumeration tecniques, until, in 1996, they were revisited by Balas et al., becoming a fundamental tool for commercial MIP solver. Despite their long history and relative success, the lack of understanding on their practical behaviour makes Gomory Cutting Planes an interesting research topic. In particular it is clear that they might perform much better than current implementations have managed to do, but nobody has found the right way of using them yet.
In the talk we will review Gomory cutting planes, their typical usage in commercial MIP solvers and recent research findings that might eventually lead to a new performance breakthrough.

Rif. int. C. Marastoni, T. Vargiolu, M. Dalla Riva

Download Seminario Dottorato