TITLE:   Generalized intersection cuts and a new cut generating paradigm

SPEAKER:  Egon Balas

ABSTRACT:

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)



Bio:

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.