Egon Balas

Egon Balas (June 7, 1922 in Cluj, Romania – March 18, 2019) was an applied mathematician and a professor of industrial administration and applied mathematics at Carnegie Mellon University. He was the Thomas Lord Professor of Operations Research at Carnegie Mellon's Tepper School of Business and did fundamental work in developing integer and disjunctive programming.

Balas was born in Cluj (Romania) in a Hungarian Jewish family. His original name was Blatt, which was first changed to the Hungarian Balázs and then later to the Romanian Balaş. He was married to art historian Edith Balas, a survivor of Auschwitz, with whom he had two daughters. He was imprisoned by the Communist authorities for several years after the war.

He left Romania in 1966 and accepted an appointment with Carnegie Mellon University in 1967. Balas obtained a "Diploma Licentiate" in economics (Bolyai University, 1949) and Ph.D.s in economics (University of Brussels, 1967) and mathematics (University of Paris, 1968). His mathematics PhD thesis was titled Minimax et dualité en programmation discrète and was written under the direction of Robert Fortet.

Balas's first major contribution to integer programming was the additive algorithm for zero-one programs, published in 1965. It is an implicit-enumeration procedure that uses logical consequences of fixing binary variables to avoid examining all possible assignments. The method became an influential early approach to branch and bound; a National Academy of Engineering memorial later noted that the paper was, by the early 1980s, the most cited paper published in Operations Research.

Balas subsequently developed disjunctive programming, which treats optimization problems whose feasible region can be represented as a union of polyhedra,

A central question is then to characterize the convex hull . Balas showed that this convex hull admits a compact representation in a higher-dimensional space, from which inequalities in the original variables can be obtained by projection. This viewpoint generalized his earlier intersection cuts and later provided the basis for lift-and-project cuts used in branch and cut methods for mixed-integer optimization. The principal convex-hull results had originally appeared in a 1974 Carnegie Mellon technical report before being published as an invited paper in 1998.

• E. Balas, A. Saxena: Optimizing Over the Split Closure, Mathematical Programming 113, 2 (2008), 219–240.
• E. Balas, M. Perregaard: A Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0-1 Programming, Mathematical Programming B (94), 2003; 221–245.
• E. Balas, S. Ceria, G. Cornuéjols: Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework, Management Science 42, 1996; 1229–1246.
• E. Balas: The Prize Collecting Traveling Salesman Problem: II Polyhedral Results, Networks 25, 1995; 199–216.
• E. Balas, S. Ceria, G. Cornuéjols: A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs, Mathematical Programming 58, 1993; 295–324.
• E. Balas: The Prize Collecting Traveling Salesman Problem I, Networks 19, 1989; 621–636.
• E. Balas, J. Adams, D. Zawack: The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Science 34, 1988; 391–401.
• E. Balas, V. Chvátal, J. Nesetril: On The Maximum-Weight Clique Problem, Mathematics of Operations Research 12, 1987; 522–536.
• E. Balas: Disjunctive Programming, Annals of Discrete Mathematics 5, 1979; 3–51.
• E. Balas: An Additive Algorithm for Solving Linear Programs with Zero-One Variables, Operations Research 13 (4), 1965; 517–549.

• National Academy of Engineering, 2006
• IFORS Hall of Fame, 2006
• Honorary Doctorate in Mathematics, University of Waterloo, 2005
• Hungarian Academy of Science, external member, 2004
• INFORMS Fellow, 2002
• Honorary Doctorate in Mathematics, Miguel Hernandez University, Elche, Spain, 2002
• EURO Gold Medal, 2001
• John von Neumann Theory Prize, INFORMS, 1995
• Senior U.S. Scientist Award of the von Humboldt Foundation, 1980–1981