PROJETS COLLABORATIFS MATHS-IA
Subsidized projects
2020
- Understanding and Developing Evolutionary Algorithms via Mathematical Runtime Analyses
Appel à projet PRMO 2020
Budget : 10 KE
Coordinateur : Benjamin DOERR
- Zero-sum games, Learning and Optimization procedures
Appel à projet PRMO 2020
Budget : 4 KE
Coordinateur : Joon KOWN
2019
- Learning, Online and with USERs (LOUSER)
Appel PRMO 2019
Budget : 7KE
Coordinateur : V. PERCHET
- ALgebraic Methods in gAmes and optimization
Appel PRMO 2019
Budget : 8KE
Coordinateurs : E. TSIGARIDAS et X. ALLAMIGEON
- Efficacité énergétique en Planification de production : modèles et algos d’Optimisation
Appel PRMO 2019
Budget : 7 KE
Coordinateurs : AKBALIK et C. GICQUEL
2018
- Scalable stochastic variance reduced gradient methods (SCAVARG)
Appel PGMO 2018.
Budget : 8 kE
Coordinateur : Robert M. Gower (Associate Professor, Telecom-Paristech)
Participants : Dr. Robert M. Gower (Maître de conférence/ Project leader), Télécom ParisTech, Nidham Gazagnadou (PhD student), Télécom ParisTech Martin Jaggi (Tenure-track assistant professor at EPFL)
Résumé: Large scale optimization problems in Machine Learning, most notably the empirical risk minimization problem, has put pressure on the optimization community to design new highly scalable and incremental methods. This pressure has led to the revival of a rather old method from the 1950's, the stochastic gradient descent (SGD) method. SGD and its variants are now widely used in training deep neural, support vector machines and more. Though highly scalable, for SGD to work well the user needs to determine a sequence of decreasing stepsizes for the method to converge. This project proposes the development of new stochastic variance reduced methods that can be applied to huge scale problems, such as deep nets, but are also grounded theoretically, thus give a solid foundation on which to advance the field.
- Generating Specialized Biased Experts for Electricity and Pollution Forecasting using Online Mixture
Appel PGMO 2018.
Budget : 9 kE
Coordinateur : Jairo Cugliari (Maître de Conférences, Université Lumière Lyon 2
Participants : Mathias Bourel (Profesor Adjunto), LPE, IESTA, Universidad de la Republica, Uruguay ; Jairo Cugliari (MCF), ERIC EA 3083, Université de Lyon, Lumière 2, Lyon ; Jean-Michel Poggi (PR), LMO, Univ Paris Saclay, Univ Paris Descartes ; Yannig Goude, EDF R&D.
Résumé : Ensemble methods is a popular strategy for prediction task by letting the practitioner combine individual predictions of different experts. In time series where the combination has to be done in an online setting, aggregation of experts (base learners that are combined) has been shown to produce good forecasting performance and a lot of algorithms have been proposed. However, the literature on designing the experts is surprisingly small as one of the keys of this approach is to reduce the bias of the mixture forecast. Our propose in this project is to shed light on online mixture techniques by producing specialized biased experts. The project is focused on two practical applications : electricity load and air pollution forecast. A one day workshop will be organized around the topic of Online Forecasting.
- Spectral bounds for graph partitioning
Appel PGMO 2018.
Budget : 4 kE
Coordinateur : José Neto (Asssitant Professor, Samovar, Télécom SudParis
Participants : Miguel F. Anjos (Professor, NSERC-Hydro-Québec-Schneider Electric Industrial Research Chair), GERAD & Ecole Polytechnique de Montréal
Résumé: Let G = (V;E) be an undirected simple graph having node set V = {1, 2,… n}, edge set E, and let w denote a weight function on the edges. Let k denote a positive integer and m = (m1, m2, …, mk) denote a vector of k positive integers summing up to n. We consider the problem denoted by P_{k,m} which consists in determining a partition of V into k subsets S1, S2,…, Sk of sizes m1, m2,…, mk, respectively, so as to maximize the sum of the weights of the edges having both endpoints in the same subset of the partition. This is a well-known NP-hard problem with many applications. This project aims at developing new eigenvalue-based methods for computing bounds on the optimum of P_{k,m}. We shall investigate new formulas involving the spectrum of the weight matrix (given by the function w). They involve parameters that are difficult to compute. Semidefinite programming based approaches will be developed to evaluate the new bounds for large instances and compare them with other works from the literature.
- Extraction de descripteurs génériques synthétisant les informations contenues dans les courbes de consommation électrique d'un parc de bâtiments comparables à partir d'une analyse en composantes principales fonctionnelle
Appel PGMO 2018.
Budget : 5 kE
Coordinateur : François ROUEFF (Professor, Telecom ParisTech)
Participants : Alexandre GIRARD, Ingénieur-chercheur en Traitement du Signal et des Images, EDF R&D, Chatou ; Jean-Marc JICQUEL, Ingénieur-chercheur en Thermique du Bâtiment, EDF R&D, Les Renardières.
Résumé: One important goal for an electricity provider is to be able to give pertinent advises about the electric consumption management by the customer. The available data for this purpose are the electric load curves which have to be processed to extract the pertinent information. A lot of descriptors in the past have already been developed based on one given load curve. In the case of a set of comparable buildings, supplementary information can be extracted by using recent theoretical advances in sources unmixing for functional data to decline them to load curves. The objective precisely here is to extract parsimonious descriptors allowing for example to compare the thermal performances of the buildings in order to give indications to the customer on the priority renovations.
- Analysis of Evolutionary Algorithms : Beyond Expected Optimization Times
Appel PGMO 2018.
Budget : 7 kE
Coordinateur : Carola DOERR (chargée de recherché CNRS, Sorbonne Université)
Participant : Denis Antipov, PhD student, ITMO University, St. Petersburg, Russia and LIX, Ecole Polytechnique, France ; Thomas Back, Professor, Leiden University, The Netherlands ; Benjamin Doerr, Professor, LIX, Ecole Polytechnique, France ; Carola Doerr, CNRS researcher, LIP6, Sorbonne Université, France ; Timo Kotzing, Senior researcher, HPI Potsdam, Germany ; Johannes Lengler, Researcher, ETH Zurich, Switzerland; Pietro S. Oliveto, Senior Lecturer, University of She_eld, UK; Markus Wagner, Senior Lecturer, The University of Adelaide, Australia ; Carsten Witt, associate professor, Technical University of Denmark; Jing Yang, PhD student, LIX, Ecole Polytechnique, France
Résumé : Theory of evolutionary algorithms aims at contributing to a more efficient use of these general purpose optimization techniques through a better mathematical understanding of their underlying working principles. The predominant performance measure in this research area is the expected optimization time, which counts the average number of function evaluations that an evolutionary algorithm performs until it evaluates for the first time an optimal solution candidate. Expected optimization time is a very coarse measure, which reduces the whole optimization process to a single number, thus losing a lot of information that can be useful for the design of efficient problem solvers. We therefore suggest to establish more fine-grained performance indicators. More specifically, our project aims at a systematic analysis of fixed-target runtimes and distributional guarantees.
2017
- Cloud dataset augmentation through texture synthesis
Appel PGMO Call 2017.
Budget : 6 kE
Coordinateur : Erwan Le Pennec (CMAP)
Participant : Michel Prenat (Thalès Optronique)
Résumé : L'obtention d'un très grand volume de données réelles s'avèrent compliqué dans certains cadres, par exemple celui de la détection de cible dans des nuages. Cette limitation rend plus difficile l'utilisation de méthodes d'apprentissage automatique qu'elles soient « profondes » ou non. L'objectif de ce projet est de proposer et de valider des techniques d'augmentation de la taille des bases de données de nuages par analyse et resynthèse de textures. Un travail préliminaire sur la synthèse par des modèles statistiques a déjà été effectué, il s'agit maintenant de proposer des modèles génératifs de type réseaux profonds et de comparer ces deux méthodologies en terme de gain pour l'apprentissage.
- Shortest Path Problem variants for the Hydro Unit Commitment Problem
Projet LMH-IROE - Call 2017
Budget : 5 KE
Coordinateur : d'Ambrosio
- Varational and PDE methods in Mean Field Games
Projet LMH-PRMO - Call 2017
Budget : 8 KE
Coordinateur : Santambrogio
- Anomaly Detection based on Functional Physical Data for Predictive Maintenance of Aircraft Fleet
Appel PGMO 2017.
Budget : 7 kE
Coordinateur : Stephan Clémençon (LTCI)
Participants : Anne Sabourin (Telecom ParisTech), Florence D'Alché-Buc (Telecom ParisTech), Vincent Feuillard (Airbus)
Résumé : The research activity prolongates the baseline developed in [1], where a statistical method for identifying groups of components of a heavy-tailed multivariate r.v., which may take simultaneously very large values (assimilated as a certain type of anomaly). The latter relies on the concept of angular measure in multivariate extreme value theory, which characterizes the dependence structure of the components in the extremes. More precisely, we have exploit this approach further, by means of a mixture model that permits to describe the distribution of extremal observations and where the anomaly type is viewed as a latent variable. In particular, the model enables to assign to any such point X a posterior probability for each anomaly type, defining implicitly a similarity measure between anomalies. A procedure based on the EM algorithm has also been proposed here to infer the parameters of the mixture model from a (truncated) training dataset and the corresponding posterior similarity measure estimates permit to obtain an informative planar representation of anomalies using standard graph-mining tools. The relevance and usefulness of the 2-d visual display thus designed has been shown on real datasets, in the aeronautics application domain, provided by Airbus. The source code is open source, available on a Git repository. The first results obtained are presented by Chiapino, Clémençon, Sabourin & Feuillard (2018).
- Self-Adjusting Parameter Choices in Heuristic Optimization
Appel PGMO 2017.
Budget : 7 kE
Coordinateur : Carola Doerr (LIP6)
Coordinateur pour Paris-Saclay : Benjamin Doerr (LIX)
Participants : Timo Kötzing (HPI Potsdam), Johannes Lengler (ETH Zurich), Régis Makhmara (doctorant, LIX), Pietro S. Oliveto (University of She_eld), Carsten Witt (Technical University of Denmark), Jing Yang (doctorant, LIX)
Résumé : Heuristic Search is the predominant technique to solve large-scale optimization problems as well as problems that do not allow direct access to the underlying target function (e.g., due to privacy concerns). Many optimization heuristics are parametrized. Their performance often crucially depends on the quality of the specified parameter values. It is thus one of the key challenges in optimization research to identify parameter values that are particularly suitable for a given class of problems. It is today widely acknowledged that optimal parameter values change quite drastically during the optimization process; e.g., to allow for more exploration in the beginning, and a more focused search later on. The goal of our project is to use recent advances in the analysis of heuristic search to rigorously analyze and to design parameter update rules that are able to identify and to track best-possible parameter choices “on the go”.
- Le e-bison futé du véhicule électrique
Appel PGMO 2017.
Budget : 7 kE
Coordinateur : Dominique Quadri (LRI)
Participants : MARTIN Steven (LRI), HAYEL Yezekael et JIMENEZ Tania (LIA), BEAUDE Olivier et JEANDIN A. (EDF R&D)
Résumé : Le projet e-Bison futé du véhicule électrique s'inscrit dans une problématique de gestion des trajets longues distances pour des Véhicules Electriques (VE) en situation dite dégradée localement, c'est-à-dire dans un contexte de surcharge locale du réseau de distribution. En e_et, la recharge rapide est certes la plus pratique pour l'utilisateur du VE mais elle provoque une demande de puissance que le réseau électrique pourrait difficilement supporter (localement) dans l'hypothèse d'une adoption massive de VEs et ce, surtout sur des portions du réseau électrique qui ne sont pas forcément équipées pour recevoir un tel appel. Ce projet vise à développer des outils de gestion de recharge et de proposition de mesures incitatives pour lisser la consommation électrique dans le temps (moment de la pause de recharge) et dans l'espace (station de recharge choisir), via une modélisation et une méthodologie mêlant théorie des jeux et programmation mathématique (programmation mathématique sous contrainte d'équilibre).
- Efficacité énergétique en Planification de production : modèles algorithmiques et optimisation combinatoire
Appel PGMO 2017.
Budget : 6 kE
Coordinateur : Bernard Penz (Institut Polytechnique de Grenoble)
Coordinateur pour Paris-Saclay : Céline Gicquel (LRI)
Participants : Ayse Akbalik (LGIPM, Université de Lorraine), Christophe Rapine (LGIPM, Université de Lorraine)
Résumé : Dans ce projet, nous recherchons comment l'efficacité énergétique d'un système de production de biens peut être améliorée en agissant sur la planification de production à moyen terme et le stockage de l'énergie. Nous étudions comment moduler la production dans le temps afin de tirer parti de la fluctuation des prix de l'électricité, favoriser l'utilisation des énergies renouvelables et exploiter la flexibilité offerte par le stockage sur site de l'énergie, ceci sans détériorer la performance économique du système de production. Nous nous intéressons spécifiquement au problème du dimensionnement de lots (PDL, ou Lot-Sizing) mono-produit, qui est un modèle de planification très étudié dans la littérature. Notre but est d'étudier d'un point de vue théorique cette problématique, à travers les outils de la Recherche Opérationnelle et de l'Optimisation Combinatoire, afin de développer des méthodes de planification efficaces.
- Algorithms for Expensive Simulation-Based Optimization Problems
Appel PGMO 2017.
Budget : 7 kE
Coordinateur : Dimo Brocko_ (INRIA Saclay, CMAP)
Participants : Anne Auger (INRIA Saclay, CMAP), Nikolhaus Hansen (INRIA Saclay), David Gaudrie (doctorant, EMSE), Rodolphe Le Riche (EMSE), Victor Picheny (INRA Toulouse), Sébastien Da Veiga (Safran Tech), Tea Tusar (postdoc, Josef Stefan Institute, SL), Tobias Glasmachers (RU Bochum), Günter Rudolph (TU Dortmund)
Résumé : Numerical optimization problems occur frequently in all areas of a modern society. Solving them, often requires computationally expensive numerical simulations, e.g. when a simulation model has to be calibrated with real-world data. A fundamental difficulty when approaching (such expensive) problems is the choice of the appropriate optimization algorithm. To recommend the best and filter out the worst algorithms, one typically relies on numerical benchmarking. Tedious and time-consuming, numerical benchmarking is best done automatically with software frameworks such as the Comparing Continuous Optimizers platform (COCO, github.com/numbbo/coco/). The goal of the AESOP project is to bring together researchers with backgrounds in expensive optimization and benchmarking in order to benchmark existing and design new optimization algorithms for expensive simulation-based optimization with the help of the COCO platform.
- Optimisation et Comparaison Stochastique
Appel PGMO 2017.
Budget : 6 kE
Coordinateur : Jean-Michel Fourneau (lab. DAVID, UVSQ)
Participants : Nihal Pekergin (LACL, UPEC), Yann Strozecki (lab. DAVID, UVSQ), David Auger (lab. DAVID, UVSQ), Thierry Mautor (lab. DAVID, Univ. Cergy), Pierre Coucheney (lab. DAVID, UVSQ), Farah Ait Salaht (ENSAI & LIP6)
Résumé : Le projet a pour but de concevoir des algorithmes d'encadrement pour des problèmes d'optimisation sur des graphes où les contraintes sont des variables aléatoires (par exemple, calculer le flot max dans un réseau dont les capacités sont aléatoires). On suppose que les variables aléatoires sont discrètes. On examine en priorité des problèmes qui sont polynomiaux dans le cas déterministe et difficiles dans le cas aléatoire. On se propose d'utiliser des techniques de comparaison stochastique pour réduire le support de ces variables aléatoires. En effet la taille de ce support a une influence directe sur la complexité de l'algorithme de résolution. Pendant cette première période, nous nous sommes concentrés sur quelques ordres stochastiques de variabilité : l'ordre convexe, l'ordre convexe croissant, l'ordre concave et l'ordre concave croissant. Ce choix est justifié par le fait que ces ordres sont associés aux fonctions convexes ou concaves telles les opérateurs Max et Min qui sont au coeur des problèmes d'optimisation sur les réseaux stochastiques que nous voulons étudier.
- On-line algorithms with random order
Appel PGMO 2017.
Budget : 8 kE
Coordinateur : Claire Mathieu (CNRS)
Coordinateur pour Paris-Saclay : Thang Nguyen (Université d'Évry, detached at CNRS)
Participants : Christoph Dürr (CNRS, UPMC), Chien-Chung Huang (CNRS, ENS), Abhinav Srivastav (postdoc, ENS and Paris-Dauphine).
Résumé : In the online model of computation, the input is not given all at once but is revealed gradually over time, in a sequential manner. The algorithm must maintain at all times a solution for the input seen so far, and its decisions are usually irrevocable. This setting can be interpreted as a game played between an on-line algorithm and an adversary generating the input sequence. Motivated by the observation that the input items often come from diverse uncoordinated and unsynchronized sources, the random order model assumes that the adversary chooses an arbitrary instance, but its elements are presented to the algorithm in uniform random order. Under this paradigm, we will study three categories of online problems that have recently been de_ned or have seen recent major progress : Bigtable compaction policies, truthful mechanisms for combinatorial auctions, and scheduling problems.
2016
- BAndits with Structure and Sparsity
Appel PGMO 2016.
Budget : 10 kE
Coordinateur : Vianney Perchet (ENSAE)
Participants : Vianney Perchet (ENSAE), A. Bismuth (doctorant, ENSAE), R. Degenne (doctorant, ENSAE), Joon Kwon (Post-doc, CMAP, Polytechnique)
Résumé : The project "BAndits with Structure and Sparsity - BASS" has started in 2016 and focuses on studying online learning problem where some inherent structure on the rewards, feedbacks or actions set are considered to model more precisely real life problems. The first principal objective of that project is the theoretical study of these models, and the construction & analysis of algorithms.
- Parameter Optimization via Drift Analysis
Appel PGMO 2016.
Budget : 10 kE
Coordinateur : Carola Doerr (LIP6, Univ. Pierre et Marie Curie)
Participants : Benjamin Doerr, (Professor, LIX, Ecole Polytechnique), Carola Doerr (CNRS CR2 researcher, CNRS and LIP6, UPMC), Timo Kötzing (Senior researcher, HPI Potsdam, Germany), Johannes Lengler (Researcher, ETH Zurich, Switzerland), Jing Yang (PhD student, LIX, Ecole Polytechnique).
Résumé : One driving question in the study of randomized search heuristics (RSH, an important class of black-box optimization algorithms) is the investigation of optimal parameter settings such as the size of the memory, the right trade-off between exploration and exploitation, etc. Mathematical investigations shed light on which parameter settings are most suitable in di_erent optimization contexts and have inspired the design of new algorithms. Such analyses benefit from very precise estimates for the behavior of typical RSH. Due to the randomized nature of RSH such estimates are hard to obtain by classical methods. Recently developed drift theorems form the most important technique in today's theory of RSH. The goal of our project is to develop drift methods that are particularly suitable for the analysis of very precise estimates of the optimization times of RSH and for the analysis of RSH with dynamic parameters that change during the optimization process.
- From monotone operators to smoothed duality gap
Appel PGMO 2016.
Budget : 10 kE
Coordinateur : Olivier Fercoq (Assistant Professor, LTCI, Telecom ParisTech)
Participants : Pascal Bianchi (Professor, Télécom ParisTech), Volkan Cevher (Professor, EPFL, Switzerland), Quoc Tran-Dinh (Assistant professor, University of North Carolina).
Résumé : The monotone operators theory has been very successful in the design of optimization algorithms. However, this theory does not give a simple answer to the question of convergence speed and also, some very famous methods do not rely on monotone operators. The smoothed duality gap technique has been recently introduced in order to tackle these issues and has led to the development of a new primal-dual algorithm with a guaranteed convergence speed. Basing on this concept, we are going to give an alternative analysis of existing primal-dual methods in order to treat better the convergence speed, even in the case of functions with unbounded domains. This is important in order to give guarantees for problems with constraints that are split by Lagrangian duality. Then, we will introduce new methods, with a special focus on stochastic algorithms with constraint splitting.
- Stochastic Optimization for Planning Remanufacturing Activities in Reverse Supply Chains
Appel PGMO 2016.
Budget : 7 kE
Coordinateur : Céline Gicquel (LRI, Univ. Paris-Sud)
Participants : Céline Gicquel (LRI - UPSUD), Sa_a Kedad Sidhoum (LIP6 - UPMC), Dominique Quadri (LRI - UPSUD), Quan Dong Vu (stagiaire, 6 mois en 2016, LRI - UPSUD), Franco Quezada (intern, 5 months in 2017, LRI - UPSUD)
Résumé : One possible way of mitigating the environmental impact of industrial products in terms of waste generation and natural resource consumption is by remanufacturing them once they have reached their end of life. Remanufacturing consists in replacing components or reprocessing damaged parts from used products in order to bring them to a like-new condition. The present project deals with mathematical optimization problems linked with the mid-term and short term planning of remanufacturing activities in reverse supply chains. One of the main related challenges is the high level of uncertainty in the input data needed to make these planning decisions. This is mainly due to a lack of control by the company on the flows of used products brought back by customers at collection points. The main novelty of our proposal lies in the fact that we will seek to explicitly take into account in our models the uncertainties in the problem input data. We intend to achieve this by developing new stochastic programming based approaches. This should enable us to provide practitioners with the prototype of an efficient decision-aid tool to manage their remanufacturing activities as well as with some general useful insights on the uncertainty management in remanufacturing planning. One possible way of mitigating the environmental impact of industrial products in terms of waste generation and natural resource consumption is by remanufacturing them once they have reached their end of life. Remanufacturing consists in replacing components or reprocessing damaged parts from used products in order to bring them to a like-new condition. The present project deals with mathematical optimization problems linked with the mid-term and short term planning of remanufacturing activities. One of the main related challenges is the high level of uncertainty in the input data needed to make these planning decisions. Our main objective is to develop models and solution algorithms for planning remanufacturing activities under uncertainty.
- Méthodes tropicales pour l'analyse de performance de systèmes temporisés, application au dimensionnement d'un centre d'appel EDF
Appel PGMO 2016.
Budget : 15 kE
Coordinateur : Xavier Allamigeon (INRIA Saclay)
Participants : Xavier Allamigeon (Chargé de recherche, Ecole Polytechnique), Marianne Akian (Directrice de recherche, Ecole Polytechnique), Pascale Bendotti (Chercheuse, EDF R& D), Agnès Bialecki (Chercheuse, EDF R&D), Stéphane Gaubert (Directeur de recherche, Ecole Polytechnique), Ricardo D. Katz (Chercheur, CONICET, CIFASIS, Argentine), Vianney Boeuf (Etudiant en thèse, Ecole Polytechnique), Mateusz Skomra (Etudiant en thèse, Ecole Polytechnique), Stagiaire de M2 à recruter.
Résumé : This project aims at analyzing and optimizing the performance of a commercial call center of EDF, by using and developing techniques coming from tropical geometry. The project consists of a part focused on the application to EDF call center, and a more theoretical part on the mathematical and algorithmic issues raised by this application in tropical real algebraic geometry.