Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Split Closure and Intersection Cuts

Kent AndersenContact Information, Gérard CornuéjolsContact Information and Yanjun LiContact Information

(6)  Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, USA
Abstract
In the seventies, Balas introduced intersection cuts for a Mixed Integer Linear Program (MILP), and showed that these cuts can be obtained by a closed form formula from a basis of the standard linear programming relaxation. In the early nineties, Cook, Kannan and Schrijver introduced the split closure of an MILP, and showed that the split closure is a polyhedron. In this paper, we show that the split closure can be obtained using only intersection cuts. We give two different proofs of this result, one geometric and one algebraic. Furthermore, the result is used to provide a new proof of the fact that the split closure is a polyhedron. Finally, we extend the result to more general two-term disjunctions.
Supported by NSF grant DMI-0098427 and ONR grant N00014-97-1-0196.

Contact Information Kent Andersen
Email: kha@andrew.cmu.edu

Contact Information Gérard Cornuéjols
Email: gc0v@andrew.cmu.edu

Contact Information Yanjun Li
Email: yanjun@andrew.cmu.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)