In the last 15 years the state of the art in mixed integer programming (MIP) has undergone a radical change. Known in the period 1960-1990 as a universal modeling tool which could be used to more or less accurately represent a variety of optimization problems from practically all areas of human activity, MIP was also known as a class of problems unsolvable in practice beyond prohibitively small instance sizes. The change occurred during the early 90's, and as a result today's leading commercial MIP codes are able to handle routinely most of the problems submitted to them. The jump in efficiency is due to a number of factors, like faster computers, faster and more reliable linear programming codes, etc.; but to a considerable extent, it is due to better cutting plane techniques and clever combinations of cutting planes with branch and bound. Ideas originating in the disjunctive programming approach during the 70's have led to the development of lift-and-project, a method for generating and analyzing cutting planes through a higher dimensional representation. This in turn has led to a reinterpretation and revival of the classical cutting planes of the early 60's. Starting with the late 90's, the leading commercial MIP codes contain cutting plane modules. First these were limited to the classical cuts, easiest to implement; but in 2003 one of these codes had its standard cut generating module replaced by a new one that produces lift-and-project cuts in the space of the original variables, leading to a further improvement in performance.

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. Professor 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, 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 numerous professional journals. 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. In 2004 he was elected an outside member of the Hungarian Academy of Sciences. Professor Balas has published over 200 articles and scientific studies in the professional literature. He is also the author of the memoir Will to Freedom: A Perilous Journey Through Fascism and Communism. Syracuse University Press, 2000, also available in Hungarian, Romanian, French and Italian versions.