Generalized intersection cuts and a new cut generating paradigm

Event Details
  • Date/Time:
    • Tuesday October 12, 2010 - Wednesday October 13, 2010
      11:00 am - 11:59 am
  • Location: ISyE Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Generalized intersection cuts and a new cut generating paradigm

Full Summary: No summary paragraph submitted.

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.


Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No categories were selected.
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Sep 24, 2010 - 4:45am
  • Last Updated: Oct 7, 2016 - 9:52pm