A team dedicated to combinatorial optimization
Planning deliveries, anticipating maintenance operations, optimizing the use of resources...: behind the organization of many economic activities lie complex problems to which the researchers of the EDGE team, the latest addition to the Inria centre at the university of Bordeaux, will dedicate their work in operations research and combinatorial optimization.
EDGE will bring together half a dozen scientists (five permanent researchers and one research engineer) from the CNRS, the University of Bordeaux and Inria. Built as a continuation of the RealOpt team, it will be led by François Clautiaux, professor of mathematics at the University of Bordeaux. The research themes of this new team? They are described by its acronym ("Extended formulations and Decomposition for Generic Optimisation Problems").
We have been working for about ten years on the development of mathematical models and the design of algorithms for activity planning or decision support. One of the specificities of our research is to propose "generic" methods, potentially applicable to many situations, or to answer very diverse operational questions.
Collaborations with the industrial sector
Which route should be designed for the delivery trucks? What schedules should be adopted in order to offer the best service to rail passengers? How to optimize the cutting of materials to limit waste? How to make the most of a telecommunications network to integrate a new technology? So many questions in the logistics, energy, transport and production sectors, that EDGE researchers will contribute to elucidate through fundamental research or through collaborations with experts from the industries concerned (RTE, Saint-Gobain, La Poste, SNCF, Orange...).
"Our approach to these questions is generic in the sense that we develop an abstract model, which allows us to identify common features (we speak of 'structures') between the various problems and then develop efficient algorithms to solve them," explains Ruslan Sadykov, a research fellow at Inria and an expert in mathematical methods in optimization.
Multiple parameters to take into account
Many conceptual and operational difficulties oppose the efficiency of the algorithms, due to the large number of parameters to be taken into account and the complexity of the systems involved. In the case of deliveries, for example, a theoretical question is that of the optimal logistical route, sometimes involving a multitude of interdependent problems, such as the availability of delivery personnel, the characteristics of vehicles, the state of the road network, etc. "We are working, for example, on so-called decomposition methods, which can be used to determine the optimal route for a given delivery.
"For example, we are working on so-called decomposition methods, which consist in dealing with optimization on smaller sets (on smaller domains or smaller time intervals), while ensuring that the best possible decision is made for the 'complete' set, which is generally inaccessible to even the most efficient algorithms," explains Ruslan Sadykov.
Integrating hazards into mathematical models
In addition to these intrinsic difficulties, new challenges have arisen, such as the need to account for hazards in modeling. "Operations research produces tools for managers, investors, etc. who must make strategic decisions in an uncertain context," explains Boris Detienne, a lecturer at the university of Bordeaux and a specialist in mathematical approaches robust to hazards.
For example, shutting down a nuclear power plant for maintenance is one of the most complex operations, particularly because of the strong safety and cost constraints. Prepared several years in advance, this shutdown is thought out in great detail, but must also be adaptable to the conditions in which it will be carried out, as many factors are obviously unpredictable (such as the level of electricity demand, the possibility of equipment failure, weather conditions, etc.).
"We are developing tools capable of proposing 'agile' decisions, preserving options that take into account the random variability of new data, without calling into question the major principles of the overall strategy," explains Boris Detienne. This can be done, among other things, by modeling the hazards themselves, which is integrated into the evolution model of the system studied, or by developing criteria for evaluating the decisions proposed by methods aiming for an 'optimal policy' (as opposed to optimizing each decision of which it is made up)."
Planning: maintaining a global strategy while managing the unexpected
EDGE's ambition is to extend the work undertaken via RealOpt over the past decade. "We are going to work on the robustness of our approaches, in order to extend their potential field of application, summarizes François Clautiaux. We will also develop new methods: for optimization in an uncertain context, for example, we will look at 'anchoring' techniques for planning solutions". The goal? To devise optimization techniques that achieve a compromise between stability (preserving a global strategy) and adaptability (dealing with unpredictable events).
"This compromise is relevant for the energy production/distribution sector, for example. If it is relevant to propose several possible options to a decision-maker in case of unforeseen events, it is a contrario necessary to preserve a line of conduct, both for psychological and legal reasons (a series of decisions appearing erratic could be considered as speculation in the eyes of the legislator).
Concrete applications in industry
There will certainly be no shortage of scientific challenges and the team will also be recruiting new talent, post-doctoral or PhD students under a CIFRE agreement. This formula is very well adapted to collaborative research with the industrial world, and is in line with EDGE's work philosophy.
Although the team's research is fundamental in nature, it is not confined to a purely theoretical sphere. "From the most abstract aspects (conceptualization of mathematical models) to the most applied (implementation of numerical methods), we deploy a global approach to combinatorial optimization problems, which culminates in concrete applications. The collaboration with the industrial world, which constantly pushes us to refine our approaches and proposes new subjects, is for us most stimulating: without this applicative dimension, our laboratory work would remain purely speculative...", concludes François Clautiaux.
- « Des horaires de train à la découpe de verre », François Clautiaux, professor at the Bordeaux Institute of Mathematics (IMB) - university of Bordeaux/Inria RealOpt team, DataAquitaine, 16/02/202.
- « Pricing dynamique et supply chain des containers d’algorithmes », Benoît Rottembourg, Inria, DataAquitaine, 28/02/2021.
- « L'IA, booster de l'industrie ? [We are Leonard (Vinci)] », with Maël Chiapino of DCBrain, Lorène Allano, Jean-Baptiste Léger of Predict and Barthélémy Longueville of Vallourec.