Né à Cluj, en Roumanie, en 1922 dans une famille juive d’origine hongroise, Egon Balas s’implique dans des activités clandestines pendant la Seconde Guerre mondiale, est capturé par les Allemands, torturé, puis réussit à s’échapper. Après la guerre, il est nommé diplomate à Londres et occupe des postes de responsabilité dans la Roumanie communiste qui se construit. Mais, de nouveau, c’est la prison, pour des idées non conformes, des interrogatoires répétés par la redoutable Securitate, l’isolement cellulaire pendant plus de deux ans, puis la libération et l’expulsion du Parti communiste. C’est seulement à l’âge de 37 ans qu’il commence sa carrière de mathématicien. On peut lire cette épopée fascinante dans son récit autobiographique La Liberté et rien d’autre, publié en français chez L’Harmattan en 2003.
À sa sortie de prison, Egon Balas se retrouve affecté à l’institut des Eaux et Forêts de Bucarest, où l’on planifie l’exploitation forestière en Roumanie. Pour développer les outils logistiques appropriés, il doit étudier les mathématiques et la recherche opérationnelle en autodidacte, dans les livres qu’il peut se procurer. Peter Hammer (1936‒2006), qui deviendra lui aussi très connu dans le domaine de la recherche opérationnelle, travaille à cet institut à la même époque. Pour planifier le transport du bois, Balas et Hammer créent des outils nouveaux reposant sur la théorie des flots dans les réseaux et sur la programmation linéaire (Hammer publie alors sous le nom d’Ivanescu).
Un pionnier de l’optimisation en nombres entiers
En 1962, Egon Balas se trouve confronté à un problème compliqué. Dans une zone de la forêt, il faut construire tout un réseau de routes d’accès pour atteindre des parcelles reculées. Il s’agit de décider quelles parcelles exploiter et quelles routes d’accès construire. Ces décisions sont étroitement liées. Cela implique des conclusions logiques : si la portion A de route est construite, il faut alors aussi construire la portion B pour qu’il soit possible d’atteindre A. Egon Balas formule le problème sous forme de programme linéaire en variables binaires (0, 1). Par exemple, si xA = 1 représente la construction de la portion A et xB = 1 représente la construction de la portion B, la contrainte xA ≤ xB pour des variables xA, xB prenant les valeurs 0 ou 1 représente l’implication logique mentionnée plus haut. Pour exprimer la condition « il faut construire au moins l’une des portions A, B ou C » par le biais d’une contrainte linéaire en variables 0 et 1, on écrirait de même xA + xB + xC ≥ 1.
