Xavier Allamigeon: a passion for mathematics rewarded by an Inria Prize

“I’m happy and fortunate to be able to work as a researcher. It’s a demanding job, and it can be difficult, but it also involves a lot of human interaction and intellectual discovery” explained a modest Xavier Allamigeon, as he got ready to receive his Inria – French Academy of Sciences Young Researcher Prize. This award is in recognition of the major contribution he has made to computer science and mathematics through his research.

For this brilliant researcher, a member of the Inria project team Tropical (a joint undertaking with the Centre for Applied Mathematics at École Polytechnique (jointly with CNRS)), which specialises in tropical geometry, the award caps off a decade’s commitment to original and pivotal research into IT and applied mathematics.

Xavier Allamigeon developed an interest in these disciplines from a young age: “I've always been passionate about maths and IT, sciences which I discovered at a young age. It was my teachers who introduced me to programming. It was only natural for me to go on to study science, but I never imagined I would become a researcher!” It was while on a placement at the Max Planck Institute in Germany during his time studying at École Polytechnique that he discovered the world of research.

That was my Eureka moment. It was then that I understood that scientific problems encouraged creativity, exploration and collaboration, which motivated me to continue along this path.

The young researcher took his first steps into the world of research through a CIFRE PhD at Airbus (then known as EADS), focusing on verification problems in computer programs. Half computing and half mathematics, this scientific subject involves using theoretical tools to demonstrate that computer programmes, some of which are highly complex, do in fact perform the functions they were designed for. Formal verification is crucial when it comes to the security of embedded systems (such as planes, rockets and submarines), for example, as well as for automated systems (in sectors such as energy, banking and medicine).

Following his PhD and research picked up on by his peers, Xavier Allamigeon joined Inria in 2010. He was drawn towards original mathematical tools from tropical geometry, named after the Hungarian-born Brazilian mathematician Imre Simon, who laid the foundations of the discipline. “Classical algebra, which you are taught in mathematics, deals with addition and multiplication, while tropical algebra is centred around other operations”, explains the researcher. “Addition is replaced by determining a maximum value (for example, in tropical algebra, 2+3 is 3 – the highest value between 2 and 3 – as opposed to 5), while multiplication becomes addition (the result of 2× 3 is then 5, as opposed to 6). This changes how you reason, building a new conceptual framework that is geared towards demonstrating theoretical results for use in optimisation.”

Mathematical optimisation can be used to tackle a range of concrete problems in various different sectors, from transport and energy production to the distribution of goods, manufacturing process management and complex systems. It generally requires finding the minimum value of a function depending on an extremely high number of parameters. The aim is to devise algorithms and digital methods which are “strongly polynomial”, meaning that they are effective even in situations where the parameters change at very short notice. This is no mean feat. Indeed, the American mathematician Stephen Smale included it on his list of 18 major mathematical problems of the 21st  century.

“We used tools from tropical geometry to demonstrate that certain methods ran into a brick wall when it came to solving several optimisation problems, despite these methods being considered the most effective.” This was a major theoretical breakthrough, helping to develop a better understanding of those conditions in which optimisation algorithms are most effective, in addition to developing new resolution methods which are more general, more versatile and more robust. These theoretical results attracted interest from fields other than mathematics, including game theory, which involves optimisation problems with multiple agents, and which has implications for the social sciences, economics and politics.

Beyond the theoretical sphere, Xavier Allamigeon's scientific contributions have also led to some highly concrete applications. One example of this is the modelling work that Tropical has carried out on emergency call centres since 2014, in partnership with Paris police and the Paris fire brigade. “The emergency services were looking for mathematicians to identify the strengths and weaknesses of the new system for handling calls made to the police and fire service, and so they turned to us”, explains Xavier Allamigeon. “Employing a formal framework taken from tropical geometry, we modelled the processes in place, before identifying the conditions in which a system might become congested or saturated. We also established criteria for effectively gauging the sizes of the teams that would need to be put together.” 

Allamigeon and his colleagues went one step further in applying their research in 2020 when, at the height of the pandemic, Assistance Publique – Hôpitaux de Paris (the Paris Hospital Trust) called on their expertise. The aim was to determine staff numbers for ambulance call centres in order to meet the unprecedented level of demand as a result of the epidemic, in addition to using call data to anticipate any changes in the greater Paris region. Completed as part of a long-term collaboration and with added pressure as a result of the health crisis, this project required a significant amount of software development, which Xavier Allamigeon also played a pivotal role in.

Off the back of these theoretical and practical results, the researcher started working as a teacher at École Polytechnique in order to pass on his expertise.  Here he is able to draw upon a level of experience he has patiently accumulated over the course of a career that has never been dull. “At its best, scientific research is filled with the joys of discovery, but it also has its fair share of doubts and more difficult moments. At such times, working as part of a team with my colleagues and my PhD students plays a pivotal role. This prize is also in recognition of that collective dynamic”, says Xavier Allamigeon, before concluding, “I see this prize as motivation to continue my research, combining difficult theoretical problems with concrete applications.”

• Workshop: Tropical geometry and the geometry of linear programming, Hausdorff Research Institute for Mathematics (HIM), 20-24/9/2021.
• Determining optimal strategies using tropical algebra, by Stéphane Gaubert, Inria researcher and lecturer at the École Polytechnique’s Centre of Applied Mathematics, École Polytechnique 28/6/2016.