Publications

2022

• Computing Transience Bounds of Emergency Call Centers: a Hierarchical Timed Petri Net Approach
  
  • Allamigeon Xavier
  • Boyet Marin
  • Gaubert Stéphane
  , 2022, LNCS-13288, pp.90-112. A fundamental issue in the analysis of emergency call centers is to estimate the time needed to return to a congestion-free regime after an unusual event with a massive arrival of calls. Call centers can generally be represented by timed Petri nets with a hierarchical structure, in which several layers describe the successive steps of treatments of calls. We study a continuous approximation of the Petri net dynamics (with infinitesimal tokens). Then, we show that a counter function, measuring the deviation to the stationary regime, coincides with the value function of a semi-Markov decision problem. Then, we establish a finite time convergence result, exploiting the hierarchical structure of the Petri net. We obtain an explicit bound for the transience time, as a function of the initial marking and sojourn times. This is based on methods from the theory of stochastic shortest paths and non-linear Perron--Frobenius theory. We illustrate the bound on a case study of a medical emergency call center. (10.1007/978-3-031-06653-5_5)
  DOI : 10.1007/978-3-031-06653-5_5
• Monotonicity in mean field games and dynamics of the spectrum of large random matrices
  
  • Bertucci Charles
  , 2022.
• Heterogeneous Treatment Effects Estimation: When Machine Learning meets multiple treatments regime
  
  • Acharki Naoufal
  • Bertoncello Antoine
  • Garnier Josselin
  • Lugo Ramiro
  , 2022.
• Novel Variational Approaches to Inference and Learning
  
  • Thin Achille
  , 2022. This thesis addresses the problem of high dimensional inference.We propose different methods for estimating normalizing constants and sampling complex distributions.In a first part, we develop several Markov chain Monte Carlo methods.On the one hand, we develop a new approach for non-reversible kernels. On the other hand, we propose two massively parallelizable methods combining local and global properties of Markov chain Monte Carlo methods, in particular based on a new normalization constant estimator.We apply these methods to the approximate inference of the posterior distribution of deep Bayesian neural networks, in a case where the state space is very high dimensional.In a second part, we propose two generative models, based on a new form of normalising flows combined with Markov chains, or new variational inference methods, by building in particular a new variational autoencoder.These methods allow in particular to combine variational inference and Monte Carlo by Markov chains.
• A Confidence-based Aerospace Design Approach Robust to Structural Turbulence Closure Uncertainty
  
  • Gori Giulio
  • Le Maitre Olivier
  • Congedo Pietro Marco
  Computers and Fluids, Elsevier, 2022, 246, pp.105614. We propose a confidence-based design approach robust to turbulence closures model-form uncertainty in Reynolds-Averaged Navier-Stokes computational models. The Eigenspace Perturbation Method is employed to compute turbulence closure uncertainty estimates of the performance targeted by the optimizer. The magnitude of the uncertainty estimates is exploited to establish an indicator parameter associated to the credibility of numerical prediction. The proposed approach restricts the optimum search only to design space regions for which the credibility indicator suggests trustworthy RANS model predictions. In this way, we improve the efficiency of the design process, potentially avoiding designs for which the computational model is unreliable. The reference test case consists in a two-dimensional single element airfoil resembling a morphing wing section in a high-lift configuration. Results show that the prediction credibility constraint has a non negligible impact on the definition of the optimal design. (10.1016/j.compfluid.2022.105614)
  DOI : 10.1016/j.compfluid.2022.105614
• Probabilistic population genetics models for expanding populations
  
  • Louvet Apolline
  , 2022. This thesis focuses on the construction and study of stochastic population genetics models for expanding populations. We build different models using a concept from the theory of interacting particles systems, where empty sites are represented as occupied by particles with a specific type. These "ghost individuals" allow us to artificially keep population sizes constant, and build dual processes encoding genealogies. In our models, ghost individuals can reproduce as well in order to account for stochastic fluctuations in population sizes, but with a very strong selective disadvantage against "real" individuals.We first apply the concept of ghost individuals to a measure-valued process describing the reproduction dynamics of a population living in a continuous space. We construct the limit of the process when "selection" against ghost individuals becomes infinitely strong. The limiting process seems to be a space continuous equivalent of the Eden growth model. We study the expansion dynamics of real individuals in the limiting process, and show that the growth of the region they occupy is linear in time.We then focus on a variant of the spatially-structured Wright-Fisher model with a seed bank component and featuring frequent local extinction events. This was motivated by a question of ecological interest: understanding plant dynamics in urban tree bases. In a preliminary study on a real dataset, we show that it is necessary to account for the potential presence of a seed bank in order to answer this question. We use our variant of the Wright-Fisher model to show the existence of a critical patch extinction probability depending on seed bank parameters, above which a population expansion is not possible. We study the limit of the process under a strong selection regime, and show that it corresponds to an occupancy-based model. This limiting process belongs to a family of models widely used in metapopulation ecology.
• A refined Weissman estimator for extreme quantiles
  
  • Allouche Michaël
  • El Methni Jonathan
  • Girard Stéphane
  , 2022.
• EV-GAN: Simulation of extreme events with ReLU neural networks
  
  • Allouche Michaël
  • Girard Stéphane
  • Gobet Emmanuel
  , 2022.
• Removing algorithmic discrimination (with minimal individual error)
  
  • El-Mhamdi El-Mahdi
  • Guerraoui Rachid
  • Hoang Lê Nguyen
  • Maurer Alexandre
  Theoretical Computer Science, Elsevier, 2022, 923, pp.47-55. (10.1016/j.tcs.2022.04.051)
  DOI : 10.1016/j.tcs.2022.04.051
• Acoustic passive cloaking using thin outer resonators
  
  • Chesnel Lucas
  • Heleine Jérémy
  • Nazarov Sergei A
  Zeitschrift für Angewandte Mathematik und Physik = Journal of Applied mathematics and physics = Journal de mathématiques et de physique appliquées, Springer Verlag, 2022, 73 (3). We consider the propagation of acoustic waves in a 2D waveguide unbounded in one direction and containing a compact obstacle. The wavenumber is fixed so that only one mode can propagate. The goal of this work is to propose a method to cloak the obstacle. More precisely, we add to the geometry thin outer resonators of width ε and we explain how to choose their positions as well as their lengths to get a transmission coefficient approximately equal to one as if there were no obstacle. In the process we also investigate several related problems. In particular, we explain how to get zero transmission and how to design phase shifters. The approach is based on asymptotic analysis in presence of thin resonators. An essential point is that we work around resonance lengths of the resonators. This allows us to obtain effects of order one with geometrical perturbations of width ε. Various numerical experiments illustrate the theory. (10.1007/s00033-022-01736-6)
  DOI : 10.1007/s00033-022-01736-6
• Global Linear Convergence of Evolution Strategies on More Than Smooth Strongly Convex Functions
  
  • Akimoto Youhei
  • Auger Anne
  • Glasmachers Tobias
  • Morinaga Daiki
  SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2022. Evolution strategies (ESs) are zero-order stochastic black-box optimization heuristics invariant to monotonic transformations of the objective function. They evolve a multivariate normal distribution, from which candidate solutions are generated. Among different variants, CMA-ES is nowadays recognized as one of the state-of-the-art zero-order optimizers for difficult problems. Albeit ample empirical evidence that ESs with a step-size control mechanism converge linearly, theoretical guarantees of linear convergence of ESs have been established only on limited classes of functions. In particular, theoretical results on convex functions are missing, where zero-order and also first order optimization methods are often analyzed. In this paper, we establish almost sure linear convergence and a bound on the expected hitting time of an ES, namely the (1 + 1)-ES with (generalized) one-fifth success rule and an abstract covariance matrix adaptation with bounded condition number, on a broad class of functions. The analysis holds for monotonic transformations of positively homogeneous functions and of quadratically bounded functions, the latter of which particularly includes monotonic transformation of strongly convex functions with Lipschitz continuous gradient. As far as the authors know, this is the first work that proves linear convergence of ES on such a broad class of functions.
• Computer-assisted proofs for some nonlinear diffusion problems
  
  • Breden Maxime
  Communications in Nonlinear Science and Numerical Simulation, Elsevier, 2022, 109. In the last three decades, powerful computer-assisted techniques have been developed in order to validate a posteriori numerical solutions of semilinear elliptic problems of the form ∆u+f (u, ∇u) = 0. By studying a well chosen fixed point problem defined around the numerical solution, these techniques make it possible to prove the existence of a solution in an explicit (and usually small) neighborhood the numerical solution. In this work, we develop a similar approach for a broader class of systems, including nonlinear diffusion terms of the form ∆Φ(u). In particular, this enables us to obtain new results about steady states of a cross-diffusion system from population dynamics: the (non-triangular) SKT model. We also revisit the idea of automatic differentiation in the context of computer-assisted proof, and propose an alternative approach based on differential-algebraic equations. (10.1016/j.cnsns.2022.106292)
  DOI : 10.1016/j.cnsns.2022.106292
• Using Well-Understood Single-Objective Functions in Multiobjective Black-Box Optimization Test Suites
  
  • Brockhoff Dimo
  • Auger Anne
  • Hansen Nikolaus
  • Tušar Tea
  Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2022, 30 (2), pp.165-193. Several test function suites are being used for numerical benchmarking of multiobjective optimization algorithms. While they have some desirable properties, like well-understood Pareto sets and Pareto fronts of various shapes, most of the currently used functions possess characteristics that are arguably under-represented in real-world problems. They mainly stem from the easier construction of such functions and result in improbable properties such as separability, optima located exactly at the boundary constraints, and the existence of variables that solely control the distance between a solution and the Pareto front. Here, we propose an alternative way to constructing multiobjective problems—by combining existing single-objective problems from the literature. We describe in particular the bbob-biobj test suite with 55 bi-objective functions in continuous domain, and its extended version with 92 bi-objective functions (bbob-biobj-ext). Both test suites have been implemented in the COCO platform for black-box optimization benchmarking. Finally, we recommend a general procedure for creating test suites for an arbitrary number of objectives. Besides providing the formal function definitions and presenting their (known) properties, this paper also aims at giving the rationale behind our approach in terms of groups of functions with similar properties, objective space normalization, and problem instances. The latter allows us to easily compare the performance of deterministic and stochastic solvers, which is an often overlooked issue in benchmarking. (10.1162/evco_a_00298)
  DOI : 10.1162/evco_a_00298
• Topology optimization of structures undergoing brittle fracture
  
  • Desai Jeet
  • Allaire Grégoire
  • Jouve François
  Journal of Computational Physics, Elsevier, 2022, 458. In the framework of the level-set method we propose a topology optimization algorithm for linear elastic structures which can exhibit fractures. In the spirit of Grith theory, brittle fracture is modeled by the Francfort-Marigo energy model, with its Ambrosio-Tortorelli regularization, which can also be viewed as a gradient damage model. This quasi-static and irreversible gradient damage model is approximated using penalization to make it amenable to shape-dierentiation. The shape derivative is determined using the adjoint method. The shape optimization is implemented numerically using a level-set method with body-tted remeshing, which captures shapes exactly while allowing for topology changes. The eciency of the proposed method is demonstrated numerically on 2D and 3D test cases. The method is shown to be ecient in conceiving crack-free structures. (10.1016/j.jcp.2022.111048)
  DOI : 10.1016/j.jcp.2022.111048
• Dilute Bose gas with three-body interaction: recent results and open questions
  
  • Nam Phan Thành
  • Ricaud Julien
  • Triay Arnaud
  Journal of Mathematical Physics, American Institute of Physics (AIP), 2022, 63 (6), pp.061103. We review our recent study on the ground state energy of dilute Bose gases with three-body interactions. The main feature of our results is the emergence of the 3D energy-critical Schrödinger equation to describe the ground state energy of a Bose--Einstein condensate, where the nonlinearity strength is determined by a zero scattering problem. Several open questions will also be discussed. (10.1063/5.0089775)
  DOI : 10.1063/5.0089775
• Background-enhanced collapse instability of optical speckle beams in nonlocal nonlinear media
  
  • Xu Gang
  • Garnier Josselin
  • Fusaro Adrien
  • Picozzi Antonio
  Physica D: Nonlinear Phenomena, Elsevier, 2022, 434, pp.133230. (10.1016/j.physd.2022.133230)
  DOI : 10.1016/j.physd.2022.133230
• Piecewise affine dynamical systems applied to the performance evaluation of emergency call centers
  
  • Boyet Marin
  , 2022. We develop mathematical methods for the performance analysis and dimensioning of emergency call centers.We use tools from the field of discrete-event dynamical systems, in particular the formalism of timed Petri nets with preselection and priority rules, to describe the handling of emergency calls by dedicated platforms. These models are characterized by piecewise affine and recursive dynamical equations which are a subclass of controlled switched systems. We show that the continuous relaxation (or fluid) approximation of these dynamics is asymptotically precise under the application of a scaling factor.We establish formal correspondence results between the dynamical analysis of monotonic timed Petri nets and the study of the value function of semi-Markov decision processes with discount factors as well as terminal and stopping costs. We obtain in this way several characterizations of the throughput vector of Petri nets, which indicate the handling rate of the organization that is modeled. We deduce practical staffing recommendations for emergency call centers.We compute analytical upper bounds on the time needed for a class of monotonic and hierarchical timed Petri nets to absorb a perturbation affecting an input by exhibiting a correspondence with stochastic shortest path problems. In the context of emergency call centers, this indicates how quickly an extra peak of calls can be treated. We also study the congestion phases of non-monotonic organizations, that is to say when priority rules come into play, and compute the minimum staffing of more complex call center layouts.In addition, we focus on tropical posynomial systems, which are an algebraical abstraction and static counterpart of our dynamical systems. We show that the resolution of these equations features geometric problems of independent interest, involving separation properties of several convex bodies.We challenge our theoretical contributions on two real-life case studies carried out in collaboration with emergency call centers in this Paris area: the four SAMU of AP-HP for medical needs and the PFAU for rescue and police requests.Our comparison is based on numerical simulations that reproduce call center operations with as few simplifications as possible.The arrival processes, service times and patience levels of callers are randomly generated on the basis of histograms derived from the data analysis of millions of calls. We show that our analytical formulas that neglect abandonment phenomena yield good polyhedral approximations of the real throughput. We also evaluate the accuracy of queueing theory estimates which are frequently applied to the sizing problem of call centers.The simulation approach allows us to compare the single-tier and the two-tier architectures of emergency call centers. We show that the latter causes fewer losses of urgent calls than the former provided that the first-level instruction is quick. The two-tier layout is also more resilient to burst of calls. We finally quantify the benefit of merging or bringing together several pools of agents.
• Optimization of the Steklov-Lamé eigenvalues with respect to the domain
  
  • Antunes Pedro
  • Bogosel Beniamin
  , 2022. This work deals with theoretical and numerical aspects related to the behavior of the Steklov-Lamé eigenvalues on variable domains. After establishing the eigenstructure for the disk, we prove that for a certain class of Lamé parameters, the disk maximizes the first non-zero eigenvalue under area or perimeter constraints in dimension two. Upper bounds for these eigenvalues can be found in terms of the scalar Steklov eigenvalues, involving various geometric quantities. We prove that the Steklov-Lamé eigenvalues are upper semicontinuous for the complementary Hausdorff convergence of ε-cone domains and, as a consequence, there exist shapes maximizing these eigenvalues under convexity and volume constraints. A numerical method based on fundamental solutions is proposed for computing the Steklov-Lamé eigenvalues, allowing to study numerically the shapes maximizing the first ten non-zero eigenvalues.
• Wind power predictions from nowcasts to 4-hour forecasts: a learning approach with variable selection
  
  • Bouche Dimitri
  • Flamary Rémi
  • d'Alché-Buc Florence
  • Plougonven Riwal
  • Clausel Marianne
  • Badosa Jordi
  • Drobinski Philippe
  , 2022. We study the prediction of short term wind speed and wind power (every 10 minutes up to 4 hours ahead). Accurate forecasts for those quantities are crucial to mitigate the negative effects of wind farms' intermittent production on energy systems and markets. For those time scales, outputs of numerical weather prediction models are usually overlooked even though they should provide valuable information on higher scales dynamics. In this work, we combine those outputs with local observations using machine learning. So as to make the results usable for practitioners, we focus on simple and well known methods which can handle a high volume of data. We study first variable selection through two simple techniques, a linear one and a nonlinear one. Then we exploit those results to forecast wind speed and wind power still with an emphasis on linear models versus nonlinear ones. For the wind power prediction, we also compare the indirect approach (wind speed predictions passed through a power curve) and the indirect one (directly predict wind power).
• Second-order uniformly asymptotic-preserving space-time-ImEx schemes for hyperbolic balance laws with stiff relaxation
  
  • Reboul Louis
  • Pichard Teddy
  • Massot Marc
  , 2022. We consider hyperbolic systems of conservation laws with relaxation source terms leading to a diffusive asymptotic limit under a parabolic scaling. We introduce a new class of secondorder in time and space numerical schemes, which are uniformly asymptotic preserving schemes. The proposed Implicit-Explicit (ImEx) approach, does not follow the usual path relying on the method of lines, either with multi-step methods or Runge-Kutta methods, or semi-discretized in time equations, but is inspired from the Lax-Wendroff approach with the proper level of implicit treatment of the source term. As a result, it yields a very compact stencil in space and time and we are able to rigorously show that both the second-order accuracy and the stability conditions are independent of the fast scales in the asymptotic regime, including the study of boundary conditions. We provide an original derivation of l 2 and l ∞ stability conditions of the scheme that do not deteriorate the second order accuracy without relying on a limiter of any type in the linear case, in particular for shock solutions, and extend such results to the nonlinear case, showing the novelty of the method. The prototype system for the linear case is the hyperbolic heat equation, whereas barotropic Euler equations of gas dynamics with friction are the one for the nonlinear case. The method is also able to yield very accurate steady solutions in the nonlinear case when the relaxation coefficient in the source term depends on space. A thorough numerical assessment of the proposed strategy is provided by investigating smooth solutions, solutions with shocks and solutions leading to a steady state with space dependent relaxation coefficient.
• Formalizing the Face Lattice of Polyhedra
  
  • Allamigeon Xavier
  • Katz Ricardo
  • Strub Pierre-Yves
  Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022, 18 (2). Faces play a central role in the combinatorial and computational aspects of polyhedra. In this paper, we present the first formalization of faces of polyhedra in the proof assistant Coq. This builds on the formalization of a library providing the basic constructions and operations over polyhedra, including projections, convex hulls and images under linear maps. Moreover, we design a special mechanism which automatically introduces an appropriate representation of a polyhedron or a face, depending on the context of the proof. We demonstrate the usability of this approach by establishing some of the most important combinatorial properties of faces, namely that they constitute a family of graded atomistic and coatomistic lattices closed under interval sublattices. We also prove a theorem due to Balinski on the $d$-connectedness of the adjacency graph of polytopes of dimension $d$. (10.46298/lmcs-18(2:10)2022)
  DOI : 10.46298/lmcs-18(2:10)2022
• RobustMeans.jl
  
  • Métivier David
  , 2022. Implement some Robust Mean Estimators
• Optimisation de forme de poutres et plaques viscoélastiques en vibration libre
  
  • Joubert Antoni
  • Allaire Grégoire
  • Amstutz Samuel
  • Diani Julie
  , 2022.
• Precise 3D reactor core calculation using Spherical Harmonics and Discontinuous Galerkin Finite Element Methods
  
  • Assogba Kenneth
  • Bourhrara Lahbib
  • Zmijarevic Igor
  • Allaire Grégoire
  , 2022, 3189, pp.1224-1233. We study the use of PN method in angle and Discontinuous Galerkin in space to solve 3D neutron transport problem. PN method consists in developing the angular flux on truncated spherical harmonics basis. In this paper, we couple this method with the discontinuous finite elements in space to obtain a complete discretisation of the multigroup neutron transport equation. To investigate its precision, the method was applied to Takeda and C5G7 benchmark problems. These calculations point out that the proposed PN-DG method is capable of producing accurate solutions in small computational time, and that it is able to handle complex 3D geometries. (10.13182/PHYSOR22-37354)
  DOI : 10.13182/PHYSOR22-37354
• Sliding Window Strategy for Convolutional Spike Sorting with Lasso
  
  • Dragoni Laurent
  • Flamary Rémi
  • Lounici Karim
  • Reynaud-Bouret Patricia
  Acta Applicandae Mathematicae, Springer Verlag, 2022, 179 (1), pp.7. (10.1007/s10440-022-00494-x)
  DOI : 10.1007/s10440-022-00494-x