Generalized intersection cuts and a new cut generating paradigm

Primary tabs

TITLE:   Generalized intersection cuts and a new cut generating paradigm

SPEAKER:  Egon Balas


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)

Egon Balas is University Professor of Industrial Administration and Applied Mathematics, as well as the Thomas Lord Professor of Operations Research, at Carnegie Mellon University. He has a doctorate in Economic Science from the University of Brussels and a doctorate in Mathematics from the University of Paris.

Professor Balas's research interests are in mathematical programming, primarily integer and combinatorial optimization. He has played a leading role in the developmant of enumerative and cutting plane techniques for 0-1 programming, and is mainly known as the developer of the approach called disjunctive programming or lift-and-project. He has also developed scheduling algorithms and software. Dr. Balas has served or is serving on the editorial boards of Operations Research, Discrete Applied Mathematics, the Journal of Combinatorial Optimization, Computational Optimization and Applications, the European Journal of Operational Research, Annals of Operations Research etc. In 1980 Dr. Balas received the US Senior Scientist Award of the Alexander von Humboldt Foundation; in 1995 he received the John von Neumann Theory Prize of INFORMS; and in 2001 he was the first American to be awarded the EURO Gold Medal of the European Association of Operational Research Societies.



  • Workflow Status: Published
  • Created By: Anita Race
  • Created: 09/24/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No categories were selected.


No keywords were submitted.

Target Audience