Egon Balas, Carnegie Mellon University

Event Details
  • Date/Time:
    • Tuesday October 12, 2010
      11:00 am - 12:00 pm
  • Location: Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

Renato Monteiro, ISyE
Contact Renato Monteiro
404-894-2300

Summaries

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

Full Summary: 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.

Speaker

Egon Balas
University Professor of Industrial Administration and Applied Mathematics
The Thomas Lord Professor of Operations Research
Carnegie Mellon University

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.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Mike Alberghini
  • Workflow Status: Published
  • Created On: Dec 20, 2012 - 10:38am
  • Last Updated: Oct 7, 2016 - 10:01pm