EGON BALAS

1922–2019

Elected in 2006

“For contributions to integer programming and its applications to the scheduling and planning of industrial facilities.”

BY GÉRARD CORNUÉJOLS

EGON BALAS’ life reads like an adventure tale. Born June 7, 1922, in Cluj, Romania, into a Jewish Hungarian family, he wanted to study physics but was blocked by anti-Semitic laws. Determined to fight Nazism, he joined the underground Hungarian Communist Party, distributing leaflets and helping to organize a strike. He was arrested by fascist Hungarian authorities in 1944, tortured, and thought he would be killed. Sentenced to 14 years of hard labor, he escaped during transport to Germany and made his way home, where he learned that all of his immediate family had been killed along with most of the 18,000 Jews who had lived in Cluj before the war. In 1948 he married Edith Lovi, herself a Holocaust survivor who had returned home to Romania after being released from Auschwitz at the end of the war. They were married for 70 years.

After the war and still in the Communist Party, Balas taught himself economics and changed his birth name from Blatt, a common Jewish surname, to Balas in order to serve in the Romanian government as economics director in the Ministry of Foreign Affairs. During a power struggle in 1952 he was arrested by party leaders, put in solitary confinement for more than 2 years, and subjected to interrogations and torture. Upon his release he was expelled from the Communist party.

In 1959 Balas started a career in mathematics at age 37. He had joined the Forestry Institute in Bucharest, which planned and scheduled timber harvesting in Romania. To develop appropriate logistics tools, he became an autodidact, learning mathematics and operations research from books he could get his hands on. Peter Hammer, who was to become a prominent operations researcher himself, was also working at the Forestry Institute at the time. Together they developed tools for transportation planning based on network flow theory and linear programming. They published a dozen papers together (Hammer was using the name Ivanescu at the time), mostly in Romanian.

In 1962 Egon confronted an interesting variation on the wood harvesting problem: In one area of the forest, a network of roads had to be built in order to access various plots. Decisions about which plots to harvest and where to build roads were intricately connected and required logic: If road segment A were built, then road segment B would also have to be built to reach A. Egon formulated the problem as a linear program in 0,1 variables, recognizing the versatility of this model for a wide range of applications.

There was no computer code to solve 0,1 programs at the time, so he designed his own algorithm, simple enough that instances with about 30 binary variables could be solved by hand. The algorithm performed an implicit enumeration of the solution set, relied on a series of logical tests that explored the implications of fixing certain variables to 0 or 1, and the only operations needed were additions and comparisons. Balas’ algorithm can be viewed as a precursor of constraint propagation in constraint programming.

The work was presented to the research community in the West at the International Symposium in Mathematical Programming in London in 1964. The Romanian government would not allow Egon to travel to England to present his paper, so his talk was read by a colleague at the conference. This was one of the many constraints that led to Balas’ disillusionment with communist Romania.

The same year a short version of his paper was published in Comptes Rendus de l’Académie des Sciences, Paris. The full-length

paper was published in 1965.¹ It was extremely influential in the development of integer programming, establishing implicit enumeration and branch-and-bound as a simple and powerful solution method. In fact, it was identified in the early 1980s as the most cited paper in Operations Research (citation classic in Current Contents 1982).

By the early 1960s, the oppressive conditions and lack of freedom in Romania had become intolerable and Egon applied to emigrate. His application was denied several times, with increasing hardship on the family. Finally, he and his wife and two daughters were granted permission to emigrate in 1966. By then Balas had achieved some visibility in the West thanks to his work on the additive algorithm. He first went to Rome, where he spent 6 months as a research fellow at the International Computation Center, headed by Claude Berge. During this period he also managed to earn two doctorates, one in economics from the University of Brussels and the other in mathematics from the University of Paris.

The next year, in 1967, Egon was offered a professorship at Carnegie Mellon University. Bill Cooper, one of the founders of the Graduate School of Industrial Administration, was key in this brilliant recruitment decision. He was very familiar with Balas’ recent research accomplishments as he had been associate editor of Operations Research in charge of handling his paper on the additive algorithm. Egon was forever grateful to Carnegie Mellon for the stability that this position provided to his family.

His most significant contribution is undoubtedly his extensive work on disjunctive programming, starting with intersection cuts.² These ideas were novel and the operations research community was slow to accept them.

Cutting planes had been introduced by Dantzig, Fulkerson, and Johnson (1954) and Gomory (1958). But by the late 1960s

___________________

¹ Balas E. 1965. An additive algorithm for solving linear programs with zero-one variables. Operations Research 13:517–46.

² Balas E. 1971. Intersection cuts: A new type of cutting planes for integer programming. Operations Research 19:19–39.

and throughout the 1970s and 1980s, the general sentiment regarding the practicality of general cutting planes had become rather negative, in great part due to the success of branch-and-bound algorithms such as the additive algorithm.

Balas understood that enumeration was inherently exponential in complexity and that it could tackle only small or medium-size instances. He felt that the real potential was in convexifying the feasible set, potentially reducing an integer program to a simpler linear program. He also found that theory was lacking.

Using tools of convex analysis, he showed how to derive rich families of cutting planes from any feasible basis of a linear relaxation and any convex set S whose interior contains the basic solution but no feasible integer point. These cuts are Balas’ intersection cuts. When the convex set is the region between two parallel hyperplanes, one recovers Gomory’s mixed integer cut as a special case. Egon observed that intersection cuts derived from polyhedral sets S can be understood using an alternate point of view: If the polyhedron S is defined by linear inequalities, then the requirement that no feasible point is in the interior of S can be described through a disjunction of the reverse inequalities. The feasible region can then be regarded as a union of polyhedra.

This new viewpoint gave rise to important generalizations. It motivated Balas to introduce disjunctive programming, defined as optimization over a union of polyhedra. He proved two fundamental results on disjunctive programs that have far-reaching consequences for the solution of linear 0,1 programs.

First, there is a compact representation of the convex hull of the union of polyhedra in a higher-dimensional space. Projecting back onto the original space gives a full description of the convex hull, so one can compute a deepest disjunctive cut by solving a linear program. The number of variables and constraints in the higher-dimensional representation only grows linearly in the number of polyhedra, which makes this a practical tool when the number of disjunctions is not too large.

Second, for a large class of disjunctive programs, called facial, the convexification process can be performed sequentially.

For example, 0,1 programs are facial disjunctive programs: If there are n 0,1 variables, the convex hull of the solution set can be obtained in n steps, imposing the 0,1 conditions one at a time. This distinguishes 0,1 programs from more general integer linear programs. These theorems were proved in a technical report in 1974.³ Unfortunately, the significance of the results was not recognized by the referees at the time and the paper was rejected for publication. Twenty-four years later the importance of Balas’ pioneering work had finally become clear, and the technical report was eventually published as an invited paper in 1998.

In the spring of 1988 László Lovász gave a beautiful talk at the Mathematisches Forschungsinstitut Oberwolfach about his work with Lex Schrijver on cones of matrices. Sebastian Ceria, who was just starting his PhD at Carnegie Mellon, and I decided to investigate what would happen if one performed the Lovász-Schrijver operation sequentially, one variable at a time, with the idea of making it more practical for implementation. We were very excited to realize that, as in the full Lovász-Schrijver procedure, our simplified lift-and-project procedure still generated the convex hull in n steps for a problem with n 0,1 variables. When we showed this result to Egon, his reaction was immediate: “There is nothing new under the sun. This is the sequential convexification theorem!” He was right, of course; there was a nice connection between our streamlined version of the Lovász-Schrijver procedure and disjunctive programming.

This connection was very fruitful, providing a perfect framework for cut generation. Sebastian, Egon, and I had much fun collaborating on this project.⁴ We developed the mixed-integer program optimizer, which incorporated lift-and-project cuts

___________________

³ Balas E. 1974. Disjunctive programming: Properties of the convex hull of feasible points. Management Sciences Research Report No. 348, Carnegie Mellon University, July 1974. Published in 1998 as an invited paper in Discrete Applied Mathematics 89:3–44.

⁴ Balas E, Ceria S, Cornuéjols G. 1993. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58:295–324.

in a branch-and-cut framework. The success of lift-and-project cuts motivated us to try other general-purpose cuts, such as the Gomory mixed-integer cuts. These cuts had a bad reputation, with repeated claims in the literature that they perform poorly in practice. So we were very surprised to discover that they worked very well.⁵ The sentiment about general cutting planes changed overnight in the integer programming community. By the late 1990s, all commercial solvers for mixed-integer linear programs were using a battery of general-purpose cuts, resulting in significant improvement in the size of instances that could be solved optimally.

Egon Balas’ research contributions span a broad range of topics. On the subject of disjunctive cuts, additional aspects include monoidal cut strengthening,⁶ the efficient generation of the cuts,⁷ and other directions such as generalized intersection cuts. At age 96, Balas wrote his first (and only) textbook, Disjunctive Programming (Springer, 2018), presenting the advances in this area over nearly 5 decades.

Egon also made noteworthy research contributions to the knapsack and set-covering problems and in the area of scheduling: machine scheduling via disjunctive graphs, the shifting bottleneck procedure for job shop scheduling (with Joe Adams and Dan Zawack), choosing the overall size of the US strategic petroleum reserve, the prize-collecting traveling salesman problem, and an application for scheduling rolling mills in the steel industry (with Red Martin), among others.

His contributions were recognized through numerous prizes and honors. He received the US Senior Scientist Award of the Alexander von Humboldt Foundation (1980), John von Neumann Theory Prize of INFORMS (1995), EURO Gold Medal of the European Association of Operational Research

___________________

⁵ Balas E, Ceria S, Cornuéjols G, Natraj N. 1996. Gomory cuts revisited. Operations Research Letters 19:1–9.

⁶ Balas E, Jeroslow RG. 1980. Strengthening cuts for mixed integer programs. European Journal of Operations Research 4:224–34.

⁷ Balas E, Perregaard M. 2003. A precise correspondence between lift- and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Mathematical Programming B 94:221–45.

Societies (2001), and Harold Larnder Prize of the Canadian Operations Research Society. In addition he was elected an INFORMS fellow (2002) and external member of the Hungarian Academy of Sciences (2004), inducted into the IFORS Hall of Fame (2006), and elected a member of the NAE (2006), a corresponding member of the Academy of Sciences of Bologna, Italy (2011), and a SIAM fellow (2016). He received honorary doctorates from Miguel Hernández University of Elche, Spain (2002), University of Waterloo, Canada (2005), and University of Liège, Belgium (2008).

Urged by his wife, Edith, Balas wrote a well-received memoir, Will to Freedom: A Perilous Journey Through Fascism and Communism, published in 2000 by Syracuse University Press and available in six languages.

Egon died March 18, 2019. He is survived by Edith, professor emerita of art history in the College of Humanities and Social Sciences at Carnegie Mellon University; daughters Anna Balas and Vera Balas Koutsoyannis; three grandchildren; and four great-grandchildren.

Egon Balas was a good friend and colleague (as well as a great tennis partner—he was still a formidable player in December 2018, a few months before his death).