Title of Presentation: Convexification Through Lifting and Projection

CORS/Optimization Days 2006

Montréal, Canada

Wednesday, May 10, 2006

Abstract:

The last 15 years have brought a qualitative jump in the state of the art in integer and combinatorial optimization. Convexification techniques based on the concept of lift-and-project, rooted in disjunctive programming, played a key role in this development. We will examine this role and compare lift-and-project cuts to others, both theoretically and from a practical point of view. As a recent application, we will discuss a technique for approximating the integer hull by the elementary split closure. It turns out that optimizing over this closure bridges on the average about 4/5 of the integrality gap of mixed integer test instances.

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.

Dr. Balas’ research interests are in mathematical programming, primarily integer and combinatorial optimization. He has played a leading role in the development of enumerative and cutting plane techniques for 0-1 programming. In the mid-sixties he wrote a pioneering paper on implicit enumeration, which later became a Citation Classic as the most frequently cited paper in Operations Research between 1954 and 1982. In the seventies he developed a new approach to cutting plane theory, known as disjunctive programming. One of its basic results is that certain disjunctive sets, like sets of 0-1 vectors, can be convexified sequentially. Another result is a compact description of the convex hull by a system of linear inequalities in a higher dimensional space. In the 80’s Balas followed this up with the approach called projection and lifting, or extended formulation, which has been successfully used by many researchers to describe combinatorial objects otherwise hard to characterize. In the 90’s Balas and his coworkers developed the cutting plane approach known as lift-and-project, an outgrowth of disjunctive programming, which has played a crucial role in the change of the state of the art in Integer Programming that occurred during that decade. On the practical side, Balas has also developed various scheduling algorithms and software.

Dr. Balas has taught a variety of courses at different levels, and has acted as thesis advisor to 26 doctoral students. He has served or is serving on the editorial boards of numerous professional journals and is involved in a variety of other professional activities.

In 1980 Balas received the US Senior Scientist Award of the Alexander von Humboldt Foundation. In 1995 he was awarded the John von Neumann Theory Prize of INFORMS, and in 2001 he received the EURO Gold Medal of the European Association of Operational Research Societies. In 2002 Balas became a Fellow of INFORMS, in 2004 he was elected an external member of the Hungarian Academy of Sciences, and in 2006 he became a member of the National Academy of Engineering. Balas has an honorary doctorate from the University of Elche, Spain (2002) and an honoray doctorate in Mathematics from the University of Waterloo (2005).

Egon Balas has published over 200 articles and studies in the professional literature. He is also the author of Will to Freedom: A Perilous Journey Through Fascism and Communism. Syracuse University Press, 2000, a memoir of his life before migrating to the US. This book has subsequently been published in Romanian, Hungarian, French and Italian.