Time table of all LIRMM seminars

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)

A $q$-colorful graph $(G, f)$ is a graph $G$ together with a vertex-coloring function $f: V(G) \to \{1, \ldots, q\}$. Such graphs naturally capture a wide range of algorithmic problems on graphs involving distinguished sets of terminals. The concept of graph minors extends in a natural way to colorful graphs. However, to understand the complexity landscape of related problems, especially in the presence of terminals, a structural theory of colorful minors is essential. In this talk, we present three structural theorems concerning the exclusion of specific colorful graphs as minors. These are:

1. the rainbow clique — a clique in which each vertex is assigned all colors,

2. the rainbow grid — a grid in which every vertex carries all colors, and

3. segregated grids — all grids with all colors appearing segregated and in sequence on the outer face.

Our results yield a complete answer to the question of when the Erdős–Pósa property holds for colorful minors, for any possible number of colors. Beyond this, they lead to new meta-algorithmic results for graph problems with terminal constraints—problems that fall outside the reach of existing algorithmic frameworks.

Joint work with Evangelos Protopapas and Sebastian Wiederrecht