It is with enthusiasm and almost relief that researchers in theoretical computer science evoke the work of Sophie Huiberts and her thesis supervisor, Daniel Dadush. Within the Centrum voor wiskunde en informatica, a national research center in computer science and mathematics in the Netherlands, these two computer scientists have unraveled the mysteries of the simplex algorithm. If this name is unknown to the general public, it is nevertheless an integral part of our daily lives. Because this computer program solves, in practice, a large number of very concrete problems. “It can be used anywhere, from planning baseball tournaments, to managing flight plans for airplanes, to military logistics or garbage collection », lists Sophie Huiberts, now a postdoctoral fellow at Columbia University, in the United States.

However, until recently, a halo of mystery surrounded this algorithm: it was impossible to predict how long it would take to solve the problems submitted to it. Daniel Spielman, professor of computer science at Yale University, USA, explains: “We knew he would give the answer, but would it be after a few minutes? A week? Impossible to say with certainty. But, in practice, in almost all situations, he responded very quickly. However, we could not find an explanation for this, it was very frustrating! »

complex behavior

How to conceive that computer programs adopt behaviors that experts do not understand? Do algorithms therefore have a life of their own, an autonomous operation? Perhaps, according to Columbia University computer science professor Tim Roughgarden: ” I believe that [les processus algorithmiques] are discovered and not invented, that they are part of the universe in which we live. But even considering algorithms as a human creation, it’s no surprise that they can turn out to be more complex than initially expected. » Consequence: there is a whole field of research whose objective is to develop mathematical models capable of explaining the real behavior of algorithms. Just like physicists try to model black holes, or biologists try to model genetic processes.

It is therefore in this perspective that during her thesis, defended in May, Sophie Huiberts looked into the simplex algorithm, in line with Daniel Spielman, who had undertaken work on this subject in 2001. Invented by American mathematician George Dantzig (1914-2005) in 1947, this algorithm is a method for solving “linear optimization problems”. “Imagine that you are a penniless student having to go buy foodillustrates Daniel Spielman. You may wonder what products to buy and in what quantities in order to meet your recommended daily allowances. [AJR] while spending as little money as possible. Well, that’s a classic linear optimization problem. »

You have 48.32% of this article left to read. The following is for subscribers only.

Source: Le Monde