PGMO DAYS
10:00 
PGMO Prize Ceremony, by François Clautiaux (ROADEF), Filippo Santambrogio (SMAIMODE), and

10:15 
Tristan Garrec, PGMO PhD Prize lecture 
10:45 
Mathurin Massias, PGMO PhD Prize lecture 
11:15 
Break 
11:20 
Online interactive poster session 
12:50 
End of meeting 
Analysis of a twostage probabilistic programming model  Room Claude Berge
We present a simple twostage probabilistic programming problem. Structural properties of the underlying probability function are briefly discused. Finally a global solution to the problem is explicitly identified.
René Henrion (Weierstrass Institute Berlin), Wim van Ackooij (EDF R&D)
: https://www.youtube.com/watch?v=310MKVqdp9Y&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=1
Presentation and other relevant documents :
http://www.wiasberlin.de/preprint/2783/wias_preprints_2783.pdf
Distributed Optimization with Flexible Communications  Room JeanJacques Moreau
In distributed optimization for largescale learning, a major performance limitation comes from the communications between the different entities. When computations are performed by workers on local data while a coordinator machine coordinates their updates to minimize a global loss, we present an asynchronous optimization algorithm that efficiently reduces the communications between the coordinator and workers. This reduction comes from a random sparsification of the local updates. We show that this algorithm converges linearly in the strongly convex case and also identifies optimal strongly sparse solutions. We further exploit this identification to propose an automatic dimension reduction, aptly sparsifying all exchanges between coordinator and workers.
Franck Iutzeler (Univ. Grenoble Alpes)
: https://www.youtube.com/watch?v=NQiakepGXjo&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=3
Presentation and other relevant documents :
https://arxiv.org/abs/1812.03871
Optimal Control Techniques for SampledData Control Systems with Medical Applications  Room JeanJacques Moreau
In biomechanics, recent mathematical models allow one to predict
the muscular force response to functional electrical stimulations. The main
concern of the present paper is to deal with the computation of optimized
electrical pulses trains (for example in view of maximizing the final force response). Using the fact that functional electrical stimulations are modeled as
Dirac pulses, our problem is rewritten as an optimal control
problem where the control is a piecewise constant function with a finite number of discontinuities. We propose direct and indirect schemes and a finer study consisting in analyzing the mathematical properties of the control problem.
Toufik Bakir (UBFC), Piernicola Bettiol (LMBA), Bernard Bonnard (UBFC & INRIA), Loic Bourdin (xLIM) and Jérémy Rouot (ISEN)
: not available
Presentation and other relevant documents :
Multivariate degradation with dynamic covariates and imperfect maintenance  Room JeanJacques Moreau
The project is centered on the degradation and predictive maintenance strategy of the steam generators of nuclear power plants. These heat exchangers are affected by clogging, which may induce safety and performance issues. Three different degradation indicators can be punctually measured in order to assess the clogging level, which depends on design and operation conditions that are heterogeneous over the different steam generators. The degradation phenomenon can be prevented by different types of maintenance actions (chemical cleaning processes).
The aim of the study is to be able to assess and predict the evolution of the degradation in order to develop an efficient predictive maintenance strategy. To that aim, we have developed a general framework for modelling multivariate degradation processes with dynamic covariates and imperfect maintenance.
Olivier Gaudoin (Université Grenoble Alpes)
:https://www.youtube.com/watch?v=btyuyTr8Z6k&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=2
Presentation and other relevant documents :
Interactive Methods and Preference Elicitation for Solving Hard MultiObjective Combinatorial Optimization Problems  Room Claude Berge
In this project, we consider multiobjective problems where the decision maker's preferences are represented by a nonlinear aggregation function whose parameters are initially not known. More precisely, we focus on rankdependent aggregators such as ordered weighted averages (OWA) and Choquet integrals which are nonlinear scalarizing functions that assign weights to ranks rather than to objectives in the aggregation process, so as to control the importance attached to the bottom performance or to any other order statistics; for instance, an OWA operator with decreasing weights helps promoting balanced solutions while ensuring overall efficiency. In this setting, we propose new interactive heuristic methods consisting in combining regretbased preference elicitation and heuristic search so as to quickly focus the search on the most promising solutions. For OWA operators and Choquet integrals, the proposed methods run in polynomial time and are guaranteed to generate no more than a polynomial number of queries. We perform numerical tests comparing our methods to different interactive solving methods in order to show the practical efficiency of our approach in terms of number of queries, computation time and gap to optimality.
Thibaut Lust (Sorbonne University)
:https://www.youtube.com/watch?v=31sYmY3WJC8&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=4
Presentation and other relevant documents :
Optimal Resource Allocation in Microorganisms under Changing Environment  Room Claude Berge
Photosynthetic microorganisms are known to adjust their photosynthetic capacity according to light intensity. This socalled photoacclimation process may correspond at equilibrium to the optimal behavior in order to maximize growth. But its dynamics under varying condition remains less understood. To tackle this problem, we propose here a resource allocation model, at coarsegrained, to represent microalgae growth and photoacclimation. Using the Pontryagin maximum principle and numerical simulations, we determine the optimal strategy of resource allocation in order to optimize microalgal growth rate over a time horizon. We show that, after a transient, the optimal trajectory approaches the optimal steady state, a behavior known as the turnpike property. Then, the model is fitted with experimental data, resulting in a bilevel optimization problem which is solved numerically. The fitted trajectory represents well a Dunaliella tertiolecta culture facing a light downshift. Finally, we compute the optimal trajectory under day/night cycle and show that the synthesis of the photosynthetic apparatus starts a few hours before dawn. This anticipatory behavior has actually been observed both in the laboratory and in the field. This shows the algal predictive capacity and the interest of our method which predicts this phenomenon.
Terence Bayen (University of Avignon)
:https://www.youtube.com/watch?v=gfvs0FFvxm0&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=5
Presentation and other relevant documents :
Planning energy investment under uncertainty  Room Marcel Boiteux
We consider stochastic programming models for energy optimization problems with investment decisions of the hereandnow type and generation variables of recourse. The resulting problem is coupled both along scenarios and along power plants. To achieve decomposition, we combine the Progressive Hedging algorithm to deal with scenario separability, and an inexact bundle method to hablde separability for different power plants in each scenario subproblem. By suitably combining these approaches, we obtain two primaldual methods to compute an approximate solution to the original problem.
Felipe Atenas (Unicamp), Welington de Oliveira (MINES ParisTech, PSL – Research University, CMA – Centre de Mathematiques Appliquées), Claudia Sagastizábal (Unicamp) and Wim van Ackooij (EDF R&D)
:https://www.youtube.com/watch?v=OGiO643mW2c&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=6
Presentation and other relevant documents :
Hyperbolic polynomials : algorithms and implementations  Room JeanJacques Moreau
A real univariate polynomial is hyperbolic whenever all its roots are real or, in other words, if it equals the characteristic polynomial of a real symmetric matrix.
This property can be extended to the multivariate case via the classical algebraic tool of symmetric determinantal representations. By the way, not every multivariate hyperbolic polynomial admits such a representation/certificate. Hyperbolic Programming (HP) is the natural convex optimization problem asking to minimize a linear function over the hyperbolicity cone of a multivariate hyperbolic polynomial. HP generalizes Linear (LP) and Semidefinite Programming (SDP), central problems in mathematics and its applications. The goal of this project is to contribute to the following two research directions:
(1) the development of symbolicnumerical algorithms and implementations for the general HP problem, and
(2) efficient computation of hyperbolicity certificates such as symmetric determinantal representations.
The two questions above are highly related since when a polynomial has a symmetric determinantal representation or, more generally, when its hyperbolicity cone is a section of the cone of positive semidefinite matrices, then the associated HP problem reduces to a SDP problem.
Simone Naldi (Université de Limoges)
:https://www.youtube.com/watch?v=znSJixtBxCw&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=7
Presentation and other relevant documents :
https://msp.org/pjm/2019/3031/p08.xhtml
Longterm Unit Commitment Problem with Optimal Zone Configuration: a Case Study in Martinique  Room Marcel Boiteux
Island regions are not interconnected with the mainland and the isolation of these regions has brought challenges to the electric power systems. For instance, the power grids in island regions are more fragile to the rapid variance of the electricity consumption or production than the continental grid. Meanwhile, more intermittent renewable energy, such as wind and solar, has been connected to the power grid. Some of the overseas territories of France are island territories in the Atlantic, Pacific and Indian Oceans.
In this work, we propose a longterm unit commitment (UC) model with simplified network (zone) constraints to apply in these areas.
One of the main purposes of this work is to examine whether a better zonal configuration could help to increase the performance of the longterm UC model. Also, by applying this longterm UC model, we can create a robust generation plan for these territories and would be able to test, for instance, whether a larger amount of renewable energy could be introduced in these areas and whether the performance of the system could be improving by constructing a new transmission line.
Hong Cai, Loïc Quéval, Martin Hennebel (CentraleSupélec, University ParisSaclay)
:https://www.youtube.com/watch?v=vfxN3Ru2K5M&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=8
Presentation and other relevant documents :
Sequential Learning over Implicit Feedback for Robust LargeScale Recommender Systems  Room JeanJacques Moreau
In this work, we propose a theoretically founded sequential strategy for training largescale Recommender Systems (RS) over implicit feedback mainly in the form of clicks. The proposed approach consists in minimizing pairwise ranking loss over blocks of consecutive items constituted by a sequence of nonclicked items followed by a clicked one for each user. Parameter updates are discarded if for a given user the number of sequential blocks is below or above some given thresholds estimated over the distribution of the number of blocks in the training set. This is to prevent from updating the parameters for an abnormally high number of clicks over some targeted items, mainly due to bots; or very few user interactions. Both scenarios affect the decision of RS and imply a shift over the distribution of items that are shown to the users. We provide a proof of convergence of the algorithm to the minimizer of the ranking loss, in the case where the latter is convex. Furthermore, experimental results on five largescale collections demonstrate the efficiency of the proposed algorithm concerning the stateoftheart approaches, both regarding different ranking measures and computation time.
Aleksandra Burahnikova, Yury Maximov (Skoltech Institut) and MassihReza Amini (University Grenoble Alpes)
:https://www.youtube.com/watch?v=f86wvGP21IY&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=9
Presentation and other relevant documents :
Maintenance planning for hydropower plants  Room Marcel Boiteux
Presentation of a project on optimization of the maintenance planning of hydropower production systems.
Louise Fournon (ENPC)
:https://www.youtube.com/watch?v=NgW9LcGTuI&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=10
Presentation and other relevant documents :
First and second order necessary conditions in optimal control of evolution systems  Room JeanJacques Moreau
We provide second order necessary optimality conditions for a class of infinite dimensional optimal control problems under functional pure state constraints together with end point constraints. Using tools of second order variational analysis, we derive necessary optimality conditions in the form of a maximum principle and a second order variational inequality. These results can be applied to optimal control models involving PDEs.
Marco Mazzola (IMJPRG, Sorbonne Université), Hélène Frankowska (CNRS, IMJPRG, Sorbonne Université) and Elsa Maria Marchini (Politecnico di Milano)
:https://www.youtube.com/watch?v=6pSdu2q0OnE&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=11
Presentation and other relevant documents :
New approaches of bidding and contract problems: use of nonself Nash games and Radner equilibrium concept  Room Marcel Boiteux
This is the presentation for our PGMOIROE project 201935 entitled "New approaches of bidding and contract problems: use of nonself Nash games and Radner equilibrium concept
Didier Aussel (University of Perpignan), Wim van Ackooij (EDF R&D), Juan Pablo (Federal University of Rio de Janeiro), Claudia Sagastizabal (University of Campinas, Sao Paulo) and Olivier Beaude (EDF R&D)
:https://www.youtube.com/watch?v=5lqDO20m1fc&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=12
Presentation and other relevant documents :
Regret Bounds for KernelBased Reinforcement Learning  Room JeanJacques Moreau
We consider the explorationexploitation dilemma in finitehorizon reinforcement learning problems whose stateaction space is endowed with a metric. We introduce KernelUCBVI, a modelbased optimistic algorithm that leverages the smoothness of the MDP and a nonparametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. Unlike existing approaches with regret guarantees, it does not use any kind of partitioning of the stateaction space. For problems with $K$ episodes and horizon $H$, we provide a regret bound of $\widetilde{O}\left( H^3 K^{\frac{2d}{2d+1}}\right)$, where $d$ is the covering dimension of the joint stateaction space. We empirically validate KernelUCBVI in continuous MDPs with sparse rewards.
Omar Darwiche Domingues, Pierre Menard (INRIA), Matteo Pirotta (Facebook), Emilie Kaufmann (CNRS & ULille (CRIStAL), Inria Lille) and Michal Valko (DeepMind Paris)
Presentation and other relevant documents :
Online learning for minmax discrete problems  Room Claude Berge
We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative results showing that getting a vanishing (or even vanishing approximate) regret is computational hard. We provide a general reduction showing that many (minmax) polynomial time solvable problems not only do not have a vanishing regret, but also no vanishing approximation αregret, for some α (unless NP=BPP). Then, we focus on a particular minmax problem, the minmax version of the vertex cover problem which is solvable in polynomial time in the offline case. The previous reduction proves that there is no (2−ϵ)regret online algorithm, unless Unique Game is in BPP; we prove a matching upper bound providing an online algorithm based on the online gradient descent method. Then, we turn our attention to online learning algorithms that are based on an offline optimization oracle that, given a set of instances of the problem, is able to compute the optimum static solution. We show that for different nonlinear discrete optimization problems, it is strongly NPhard to solve the offline optimization oracle, even for problems that can be solved in polynomial time in the static case (e.g. minmax vertex cover, minmax perfect matching, etc.). On the positive side, we present an online algorithm with vanishing regret that is based on the follow the perturbed leader algorithm for a generalized knapsack problem.
Evripidis Bampis (LIP6 UPMC), Dimitris Christou (NTUA), Bruno Escoffier (Sorbonne Université) and Kim Thang Nguyen (IBISC, University ParisSaclay)
:https://www.youtube.com/watch?v=LDfceKEc65c&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=14
Presentation and other relevant documents :
https://arxiv.org/abs/1907.05944
The polyhedral structure of multistage stochastic linear problem with general cost distribution  Room Claude Berge
By studying the intrinsic polyhedral structure of multistage stochastic linear problems (MSLP), we show that a MSLP with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree. More precisely, we show that the expected costtogo function, at a given stage, is affine on each cell of a chamber complex i.e., on the common refinement of the complexes obtained by projecting the faces of a polyhedron. This chamber complex is independent of the cost distribution. Furthermore, we examine several important special cases of random cost distributions, exponential on a polyhedral cone, or uniform on a polytope, and obtain an explicit description of the supporting hyperplanes of the costtogo function, in terms of certain valuations attached to the cones of a normal fan. This leads to fixed parameter tractability results, showing that MSLP can be solved in polynomial time when the number of stages together with certain characteristic dimensions are fixed.
Mael Forcier (ENPC), Stéphane Gaubert (INRIA) and Vincent Leclere (ENPC)
:https://www.youtube.com/watch?v=fSKwPITRcm8&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=15
Presentation and other relevant documents :
https://hal.archivesouvertes.fr/hal02929361/
Online Search with a Hint  Room Claude Berge
Outline of our project and results so far.
Spyros Angelopoulos (CNRS and Sorbonne University)
:https://www.youtube.com/watch?v=n62ngR06QJ4&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=16
Presentation and other relevant documents :
Integrated Optimal pricing and location of electric vehicle charging stations  Room Marcel Boiteux
We propose a bilevel optimization model to determine optimal pricing, sizing, and location of Electric Vehicle (EV) charging stations by taking into account the behavior of EV users. This is done by adopting a recent approach called preferencelist or rankbased method which characterizes users by a set of distinct ordered sets of predefined preferences or products. In the upperlevel of the bilevel model, the service provider is in charge of making decisions on the price, size, and location of the charging stations to maximize its profit. In the lower level, EV users select their first available charging stations from their preference list. We present two methods, i.e., KKTbased method and cutting plane method to solve the problem. The cutting plane method is used for solving only small problem instances in order to validate the solution obtained using the KKTbased method. The bilevel model and the optimization methods are demonstrated by performing several numerical experiments on a randomly generated set of problem instances.
Alemseged Weldeyesus (University of Edinburgh), Ikram Bouras, Luce Brotcorne (INRIA Lille) and Miguel F Anjos (University of Edinburgh)
:https://www.youtube.com/watch?v=EyLIefRiel0&feature=youtu.be
Presentation and other relevant documents :
Modelling and Solving Energy Problems with SMS++  Room Marcel Boiteux
The optimization of energy systems is a complex task which involves the
modelling of sophisticated multilevel nonlinear stochastic problems and the
development of algorithms to solve them. On the one hand, modelling these
problems is not a simple task as they present a convoluted nested structure
that must capture phenomena at time resolutions spanning from minutes to
decades. Moreover, certain versatility is desirable to consider
characteristics of different systems. On the other hand, efficiently
implementing algorithms to solve them is particularly challenging, especially
if modelling flexibility is required and distributed computation is used to
exploit HPC systems, which is necessary to tackle realworld instances. In
order to facilitate the implementation and maintenance of such models and
general and adaptable algorithms for solving them, the innovative, opensource
Structured Modelling System++ (SMS++) is being developed. In this talk, we
will present an overview of the SMS++ system, including recent improvements
concerning the handling of uncertainty and how we deal with complex longterm
optimization problems.
Antonio Frangioni and Rafael Lobato (Università di Pisa)
:https://www.youtube.com/watch?v=Y5OdaukXgLI&list=PLukFMCj2tI3eH0s3reFnplsLtF69CZfL&index=18
Presentation and other relevant documents :
L'argumentation autour du véhicule électrique dans les corpus des grands débats nationaux  Room Marcel Boiteux
It is today a fact that the web is a privileged medium for governments around the world to consult citizens on political and societal topics and analyze the corresponding submitted data. Using Natural Language Processing (NLP) software to create synthetic views from this data which is abundant and heterogeneous remains a nontrivial challenge. In this project, we leverage data collected by the French government and civil groups in 2019: the Great National Debate (Grand Débat National), the True Debat (Vrai Débat) and Listen the France (Entendre la France). Our aim was to detect opinions expressed in those online debates on the specific topic of the electric vehicle, and extract arguments. To this end, we proceed with manual annotation of data, from which we trained and evaluated Machine Learning tools: a classifier for Opinion Mining (Bayes and SVM) and a Named Entity Recognizer (Rasa NLU) to detect claims and arguments.
Damien Nouvel and Johanna Cordova (INaLCO)
Presentation and other relevant documents :
http://helium.lab.parisdescartes.fr:2261/debats/projet.html
Complexity Results for Common Due Date Scheduling Problems with Interval Data and Minmax Regret Criterion  Room Claude Berge
We consider the problem of scheduling independent jobs with a common due date on a single machine with the objective of maximizing the number of early jobs. The processing times are uncertain and take any value from a certain job dependent interval. For measuring the quality of an algorithm for that problem with imprecise data we use the concept of minimizing the maximum regret. We present complexity results and some dominance properties.
Imed Kacem and Hans Kellerer
: not available
Presentation and other relevant documents :