Life of Egon Balas

Shuvomoy Das Gupta

April 25, 2020

Recently, I finished reading a fantastic autobiography: Will to Freedom by Egon Balas. It is quite long, and I read it in small chunks as I am a very slow reader. I am so glad that I finished the book.

Egon Balas (1922-2019) is a giant in the field of integer programming. He contributed to many branches of integer programming: constraint propagation, lift and project method, extended formulation, and so on. For his contributions to mathematical programming, in 1995, he was awarded the John von Neumann Theory Prize–-the highest honor in the field of operations research. But after reading his biography, I think perhaps such accolades tell us very little about a man and his journey. What a dramatic life he had!

Egon Balas was born and raised in Romania. As a young adult, he was very much interested in physics, literature, and, not very surprisingly, girls. However, when he was introduced to Marxism by a friend, his life took a turn; he came to firmly believe that Marxism has the answers to solve all the problems he was facing as a young Jewish man: oppression, antisemitism, and racism.

He became an underground communist during the onset of World War II. He wanted to fight Nazi forces, but unfortunately, he was captured by Hungarian military officers, who were working for the Germans. He was tortured severely during his imprisonment but was fortunate to escape when the war came to an end. He, along with another prisoner, escaped, hid in a hospital, and gained freedom. When he returned to his hometown, he found out that all his family members–-his parents and younger brother–-had died in cattle cars, while they were being sent to Auschwitz. He lost almost all his relatives in the Holocaust.

After the war was over, he worked as an economist for the Romanian government. At one point, he became the head of economic affairs at Romania's foreign ministry. During this time, he started having disagreements with the ruling party. As a free thinker, he often spoke his mind about the fact that the economic models developed by his department were not representative of reality. As a punishment for not parroting the party line regarding how great the Romanian economic system was, he was imprisoned again. This time he was kept in solitary confinement for more than two years. To stay sane during this long period, he recreated entire concerts in his head, and played chess on a chess set made out of toilet paper and breadcrumbs. To keep his intellect sharp, every morning, he would hold study sessions, where he tried to recall everything that he had learned so far in a systematic manner.

After two years and three months, he was released from solitary confinement, without any explanation. After he was released, he started working as an economic researcher, and he began investigating how to improve the socialist economic system of Romania, which offended the ruling party again. To the party members, the system was already perfect, and someone showing the audacity to improve an already flawless system must be an enemy of the people. So, he lost both his job and the party membership in the spring of 1959.

At the age of thirty-seven, without a job, and a family to provide for, Balas made the most remarkable decision in his life. He decided to teach himself mathematical optimization and become a mathematician, as that was the only job that he could apply for in Romania, now that his career as an economist was over. Keep in mind that, up to that point, he did not have any former mathematical training beyond high school math. At that moment, who could predict that this guy would end up becoming one of the biggest names in mathematical optimization, winning the biggest prize in the field? About his decision to learn mathematics, he writes:

Of course, I realized that if I wanted to change fields and become an expert, a researcher, in linear programming and optimization theory, as opposed to an interested reader of the literature, I would have to do a lot of hard learning; but I was keenly interested and strongly motivated. I figured that if I put together a systematic study plan and applied myself to it for several hours a day, in a year or so I would be able to attack a specific research topic and obtain some results. I set this as my goal. This sounds nice in retrospect, but when I made this decision, it would have seemed outright crazy to anyone to whom I would have confided it (which I did not). I was without a job, freshly kicked out onto the street.

In the fall of 1959, Balas found a job in the timber industry of Romania. During this time, he started learning mathematical optimization entirely on his own. He began by reviewing calculus, but when he came across Dantzig's works, Balas realized that he needed to learn linear algebra first. So, he began studying linear algebra and went through several books on this topic.

By 1962, Balas became reasonably proficient in mathematical optimization to attack research problems and started publishing in local journals. That year he made the intention of becoming an applied mathematician public. Knowing this, Grigore Moisil–-a famous mathematician in Romania–-said to Balas: "Look, you have proven to me beyond any reasonable doubt that you have considerable mathematical talent, and you have learned an enormous amount in these two years. But you are forty, and you can't be so foolish as to base your career on what you have learned in the last two years!"

Balas was quite shaken by this encounter and started doubting himself. Regarding this period, he writes:

This sentence—"You can't be so foolish as to" do exactly the thing I wanted to do—stuck in my mind (and heart?) forever. It haunted me as I pursued precisely the foolish path that Moisil had warned me against. The reason his words had such a strong impact on me was the respect I had for Moisil and his wisdom. Was I indeed committing a foolish, fatal error? This conversation gave me more psychological trouble than all the abuse I had received from the minions of the apparatus. I tried to allay my renewed doubts with the adage, "You don't really have a choice, my fellow."

Around this time (1962), simplex had become a mature method, but integer programming as a field was in its infancy. Balas became very interested in integer programming due to its application in timber industry. Over the next three years, he developed an additive algorithm for solving integer programming problems, which later led to constraint propagation methods in constraint programming. His paper on this algorithm titled "An Additive Algorithm for Solving Linear Programs with Zero­One Variables" published in Operations Research was one of the most frequently cited operations research paper of his era.

In the summer of 1966, he was able to leave Romania with his family. He went to Italy first, and then to Canada, where he had a short stint as an academic at the University of Toronto. In the spring of 1967, he and his family got his immigration visas to the US. He first moved to Stanford, where he worked with George Dantzig for a few months. In the fall of 1967, he joined Carnegie Mellon University as a Professor. Over the next five decades, he made many significant contributions in the field of integer programming such as disjunctive cuts, lift and project, extended formulation, knapsack and set-covering problems, machine scheduling, job shop scheduling and what not!

Egon Balas passed away on March 18, 2019. He was 96. He is survived by his wife, two daughters, three grandchildren, and four great-grandchildren.

Let me end this blog with an excerpt from the final chapter of Will to Freedom, which I find very meaningful and inspiring in the context of my own life:

How did the events of my earlier life affect my subsequent career? I have, of course, no way of knowing what kind of a man I would have been without those experiences. They certainly toughened me: made me stronger and more resilient, less likely to be deterred by difficulties or discouraged by setbacks. After all, I could always make the comparison between a current unpleasantness, mishap, or defeat, and the terrible events of my past, to make me feel that what was happening now was nothing in comparison with what I had been through before.

My past experiences also made me a better judge of people—having had the opportunity to observe human nature under extreme circumstances is an asset hard to match in this respect. They definitely influenced my system of values.

...When it comes to evaluating people, I try to put their accomplishments in perspective: What obstacles did they have to overcome? In choosing my friends, I put a high price on character, independence of mind, and courage. As the popular saying has it, "A friend in need is a friend indeed," and I sometimes try to imagine how this or that person might behave if I came under attack for some reason.