News

Lift-and-Project with iterative disjunctive modularization

ARGOMENTI: International Area

Giovedì 29 maggio 2008, dalle ore 15:00 alle ore 16.00 presso la Sala riunioni DEI/G (terzo piano sede storica) Dipartimento di Ingegneria dell'Informazione, via Gradenigo 6/A, Padova

Il Prof. Egon Balas della Carnegie Mellon University di Pittsburgh terrà un seminario dal titolo "Lift-and-Project with iterative disjunctive modularization".

-Abstract
Standard lift-and-project cuts are derived from a disjunction by solving a cut generating linear program (CGLP) to optimize the multipliers associated with the inequalities on the two sides of the disjunction. These cuts are then strengthened by optimally modularizing the cut coefficients of the integer-constrained variables. Clearly, the result is not an overall optimum.
Simultaneous optimization under both aspects is a hard nonlinear integer programming problem.
We approximate this overall optimum in the context of generating lift-and-project cuts from the LP simplex tableau by applying disjunctive modularization to the source row for the cut after each pivot. Computational experience will be presented.

- Biographical sketch
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 central 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 of the journal Operations Research between 1954 and 1982. In the 70's he developed a theory for optimization over unions of polyhedra, known as disjunctive programming. In the 80's he followed this up with the approach known as extended formulation, or lifting, and projection, 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. Balas also contributed theory and algorithms for various combinatorial optimization problems, like set packing and covering, traveling salesman and its generalizations, knapsack, three dimensional assignment, vertex separator, etc. On the practical side, he has 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; in 2006 he was inducted into the National Academy of Engineering and into the IFORS (International Federation of Operational Research Societies) Hall of Fame. Balas has honorary doctorates in Mathematics from the University of Elche, Spain (2002), the University of Waterloo, Canada (2005), and the University of Liege, Belgium (2008). Egon Balas has published over 200 articles and studies in the professional literature. He is the author of Will to Freedom: A Perilous Journey Through Fascism and Communism. Syracuse University Press, 2000 (paperback edition in February 2008), a memoir of his life before migrating to the US, also published in Romanian, Hungarian, French and Italian.

Prof. Matteo Fischetti (DEI, University of Padova)