Time table of all LIRMM seminars

In spatial planning, efficiently locating and allocating services presents challenges across various contexts. This research focuses on the capacitated p-median problem (CpMP), which aims to select p facilities from a set of potential locations and assign customers to minimize allocation costs while respecting capacity constraints. To better align with real-world scenarios, we extend the CpMP by introducing territorial coverage constraints, ensuring solutions effectively cover geographical partitions. We propose a matheuristic that combines heuristic and exact methods to solve this extended problem. A case study in the PACA region of France illustrates the practical application and performance of our method for solving the CpMP with Territorial Coverage Constraints.

The degree diameter problem asks for the maximum number of vertices
n∆,D in a graph of maximum degree ∆ and diameter D. While in general,
the best general upper bound one can hope for n∆,D is O(∆^D), Hell and
Seyffarth (1993) proved that for planar graphs of diameter at most 2, we
have n ≤ \lfloor 3∆/2 \rfloor + 1, and provided constructions attaining this bounds. More generally, Fellows, Hell and Seyffarth (1993) proved that every planar graph
of diameter D has O(∆^(\lfloor D/2 \rfloor)) vertices, and that this bound is asymptotically tight. When D is even, Tischenko (2012) proved an explicit optimal upper bound on the number of vertices of a planar graph with diameter D and
maximum degree ∆ (when ∆ is large enough).
On the other hand, when D = 3, the best general known bounds for planar
graphs are due to Fellows, Hell and Seyffarth (1993) who proved that every
planar graph of diameter at most 3 satisfies n ≤ 8∆ + 12 and constructed
planar graphs of diameter 3 with \lfloor 9∆/2 \rfloor – 3 vertices, and the question of
finding better upper bounds is still open.
We will see in this talk that the lower bound provided by Fellows, Hell
and Seyffarth is asymptotically tight, namely that every planar graph with
diameter at most 3 has at most 9
2 ∆+O(1) vertices. Our proof mostly consists
to a reduction to a special instance of the fractional matching problem in
planar graphs, that we solve optimally.

Joint work with Antoine Dailly, Sasha Darmon, Claire Hilaire and Petru
Valicov

Les FPGA sont des circuits intégrés reprogrammables réalisant des fonctions électroniques. Le placement de chaînes de cellules atomiques consiste à assigner des chaînes de blocs logiques indissociables à des sites de placement sur la puce, dans le but de minimiser le temps de trajet des signaux entrant et sortant de ces cellules atomiques. Ce problème est difficile car on trouve un nombre limité de sites de placement possibles, les chaînes possèdent des tailles variées, et il faut tenir compte des temps de trajet des signaux qui passeront par les chaînes placées.

Dans cette présentation, nous présenterons tout d’abord les puces FPGA, le problème de placement de chaînes de cellules atomiques, suivi de différents résultats de complexité sur celui-ci, ainsi que les méthodes de résolution exactes et heuristiques utilisées.

By extending DevOps principles to Data Sciences and Machine Learning, MLOps provides tools for the training, deployment and operation of AI models as ordinary software components that compose software architectures. A key issue of these processes is the continuous training of AI models to adapt them to observable changes in their input data coming from the production context (data and concept drifts). A no-code / low code solution seems adapted to the various user profiles that contribute to AI model development (data scientist, AI specialist or software engineer). Its design faces the challenges induced by the variety of components of MLOps processes. This project will study how domain engineering concepts (feature models, software product lines) could be used to reference commonalities in MLOps processes and document best practices for their use. The domain knowledge gathered and formalized this way will then be used to guide and assist the design of new MLOps pipelines. The approach will then be tooled by a Model Driven Engineering approach that will define a Domain Specific Language (DSL) that is altogether:
i) generic and extensible to cover the diversity of pipeline elements and target environments,
ii) abstract to be ready-to-use by non-expert users,
iii) yet allowing parameterization and fine-tuning by expert users,
iv)pivotal to obtain descriptions that will then be transformed into Platform-as-Code or Infrastructure as-Code environments used for deployment.

The project will focus on automatic and dynamic (re)-deployment of pipeline constituents that are hosted by multiple providers in order to optimize the efficiency, cost and environmental footprint of their operation.

We investigate the short-term production planning of green hydrogen obtained by water electrolysis using electricity from a wind power source and a connection to the national electricity grid. Electricity consumption on the grid has to be declared a day before production and cannot be adjusted afterwards, while the future availability of the wind power source is uncertain. This production problem can be viewed as a two-stage stochastic lot-sizing model, and a consistent framework is introduced to solve it efficiently. First, the innovative use of a variational auto-encoder to estimate the conditional uncertainty of wind power and generate scenarios is studied. Next, a time-efficient Benders decomposition approach is proposed, in which the special features of our problem are exploited to speed up its solving. Finally, a new application of an adaptive partition-based approach and a stabilization method further improve the solution time of the decomposition scheme. A realistic simulation demonstrates the advantages of the framework presented.

(Joint work with Céline Gicquel and Victor Spitzer)

Two-stage robust optimization with integer recourse is a notoriously difficult class of problems, yet modelling many important applications. In this we talk, we discuss how to heuristically solve these problems, solving the adversarial problem and the outer minimization problem through local search algorithms. We focus on the case where all decision variables as well as the uncertainty are discrete sets. We compare numerically our algorithms with the recent exact algorithm recently proposed in the literature.

TBA