Monday 9 June
9
|
Tuesday 10 June
10
-
11 h 00 min – 12 h 00 min
Patxi Flambard, «A semi-infinite constraint generation algorithm for two-stage robust optimization problems»
11 h 00 min – 12 h 00 min Patxi Flambard, «A semi-infinite constraint generation algorithm for two-stage robust optimization problems» E3.24 In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG). Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or constraints and variables. The decomposition algorithms then solve and reinforce a relaxation of the aforementioned reformulation through the iterations which require the solution of bilinear separation problems. Here, we present an alternative approach reposing on a novel reformulation of the problem with an exponential number of semi-infinite constraints. We present a nested decomposition algorithm to deal with the exponential and semi-infinite natures of our formulation separately. We argue that our algorithm will lead to a reduced number of bilinear separation problems solved while providing a high quality relaxation. We perform a detailed numerical study that showcases the superior performance of our proposed approach compared to the state-of-the-art and evaluates the contribution of different algorithmic components.
|
Wednesday 11 June
11
|
Thursday 12 June
12
|
Friday 13 June
13
-
13 h 30 min – 14 h 30 min
Jordan Moutet, «Ancestral Sequences Reconstruction: Algorithms to reconstruct past indels by the deletion-only parsimony problem»
13 h 30 min – 14 h 30 min Jordan Moutet, «Ancestral Sequences Reconstruction: Algorithms to reconstruct past indels by the deletion-only parsimony problem» Saint Priest - Bat. 5 - Salle 02.022 Ancestral sequence reconstruction is an important task in bioinformatics, with applications ranging from protein engineering to the study of genome evolution. When sequences can only undergo substitutions, optimal reconstructions can be efficiently computed using well-known algorithms. However, accounting for indels in ancestral reconstructions is much harder. First, for biologically-relevant problem formulations, no polynomial-time exact algorithms are available. Second, multiple reconstructions are often equally parsimonious or likely, making it crucial to correctly display uncertainty in the results.
Here, we consider a parsimony approach where only deletions are allowed, while addressing the aforementioned limitations. First, we describe an exact algorithm to obtain all the optimal solutions. The algorithm runs in polynomial time if only one solution is sought. Second, we show that all possible optimal reconstructions for a fixed node can be represented using a graph computable in polynomial time.
|
Saturday 14 June
14
|
Sunday 15 June
15
|
Monday 23 June
23
|
Tuesday 24 June
24
-
11 h 00 min – 12 h 00 min
Felipe Albuquerque, «The Capacitated p-Median Problem with Territorial Coverage Constraints»
11 h 00 min – 12 h 00 min Felipe Albuquerque, «The Capacitated p-Median Problem with Territorial Coverage Constraints» E3.24 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.
|
Wednesday 25 June
25
|
Thursday 26 June
26
-
9 h 30 min – 10 h 30 min
Ugo Giocanti, «Maximal order of planar graphs of small diameter»
9 h 30 min – 10 h 30 min Ugo Giocanti, «Maximal order of planar graphs of small diameter» E.3.23 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
-
11 h 00 min
Matteo Mennesson, «Placement de chaînes de cellules atomiques sur les puces FPGA»
11 h 00 min – 11 h 00 min Matteo Mennesson, «Placement de chaînes de cellules atomiques sur les puces FPGA» E3.24 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.
|
Friday 27 June
27
-
14 h 00 min – 16 h 00 min
Christelle Urtado, «AdaptiveMlOps»
14 h 00 min – 16 h 00 min Christelle Urtado, «AdaptiveMlOps» E3.23 - Bât. 4 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.
|
Saturday 28 June
28
|
Sunday 29 June
29
|