Joint ACO/OR Colloquium - Generalized intersection cuts and a new cut generating paradigm

Series: 
Other Talks
Tuesday, October 12, 2010 - 11:00
1 hour (actually 50 minutes)
Location: 
Executive classroom - Main Building
,  
Carnegie Mellon University

Hosted by Renato DC Monteiro, ISyE.

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron  C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate deeper cuts in a non-recursive fashion. (This talk is based on joint work with Francois Margot.)