|
|
|
Vidéos des présentations : plénières et tutorielsConférences plénièresChristine Solnon : Faut-il tenir compte des conditions de circulation quand on optimise des tournées de véhicules en ville ?Les approches classiques pour l’optimisation de tournées de véhicules supposent que les temps de trajet sont constants quelle que soit l’heure de départ. Cette hypothèse n’est pas réaliste en milieu urbain où les conditions de circulation sont très fluctuantes, et les problèmes de tournées « time-dependent » intègrent cet aspect en considérant des fonctions de temps de trajet qui dépendent de l’heure de départ. Dans cet exposé, nous présenterons des approches récentes pour la résolution de ces problèmes « time-dependent », puis nous étudierons l’intérêt pratique de ces travaux sur des données provenant de la Métropole de Lyon. Nous étudierons notamment l’impact du nombre de capteurs utilisés pour mesurer les conditions de circulation ainsi que de la fréquence de ces mesures sur la qualité des solutions calculées pour différents problèmes de tournées de véhicules.
Stefan Nickel : The Day After Optimal: Operations Research for Modern LogisticsOperations Researchers support decision makers by developing adequate mathematical optimization models and providing suitable solution procedures. In this talk we discuss what “adequate” could mean when decisions have to be made in uncertain environments. Therefore, we may ask several questions concerning “optimality” under causal and temporal uncertainty: What is an optimal solution? When is it optimal? For how long is it optimal? How should the design of a supply chain be changed when conditions and requirements ask for new structures? We discuss new approaches to advanced planning concepts in order to give an optimal transformation from an initial solution over multiple periods to a desired one rather than just specifying an optimal snapshot solution. Time and uncertainty are the factors triggering the whole discussion. Several flaws often found when dealing with these factors result in so-called “time traps”. In the context of operational supply chain planning and control, we look at the impact of recent developments such as the integration of simulation/optimization or the consideration of machine learning, and we show how online optimization can help to cope with these challenges. Moreover, we take a look at how the increased availability of data and forecasts affects models and decisions on a strategic level and find that with new opportunities also new challenges and stumbling blocks occur.
Denis Trystram : Le numérique face au réchauffement climatique : opportunité ou handicap ?Le monde actuel fait face à un extraordinaire défi sans précédent pour limiter le réchauffement climatique. Il est communément établi que les activités humaines sont à l’origine de ce réchauffement. La révolution du numérique a largement participé à l’avènement de ce que l’on appelle l’ère de l’anthropocène. Le secteur du numérique, et en particulier la Recherche Opérationnelle, porte en son sein une tension entre d’une part la capacité à modéliser les systèmes complexes, à les analyser et à proposer des améliorations et d’autre part l’impact direct et indirect de calculs volumineux qui participent aux émissions de gaz à effet de serre. L’objectif principal de cette présentation est d’introduire, données à l’appui, le problème général de la part du secteur du numérique dans les émissions de CO2, source principale du réchauffement. Je discuterai les différentes positions des chercheurs de la communauté face à cette question, en m’appuyant sur plusieurs exemples de pratiques vertueuses ou non. Je conclurai par quelques recommandations plus personnelles.
TutorielsRuslan Sadykov : The power of non-robust cuts in branch-cut-and-price algorithmsMixed Integer Programming (MIP) solvers have reached a remarkable efficiency for a wide range of optimization problems in recent years. There are however some classes of problems which “resist”. Among others, these are classes of vehicle routing, scheduling, network design problems. For many of them, there are no known compact MIP formulations with a strong linear relaxation after adding generic or even problem-specific cutting planes. Extended formulations with an exponential number of variables solved by branch-cut-and-price (BCP) algorithms may come to the rescue in this case. BCP algorithms are however competitive with modern MIP solvers only if the extended formulation has much stronger linear relaxation than known compact formulations. Non-robust cuts, i.e. cuts expressed in the space of extended variables, often help us to obtain such relaxation and help BCP algorithms to achieve state-of-the-art efficiency. In this tutorial, we will review some families of known non-robust cutting planes. We will also discuss issues which may arise while using non-robust cuts, including their impact on the solution time of the pricing problem, implementation difficulties, and generality/efficiency trade-off. Some recommendations on how to overcome these issues will be given.
Ayse N. Arslan : Decision rules for multi-stage adjustable robust optimizationMulti-stage adjustable robust optimization, as a subclass of multi-stage optimization under uncertainty problems, constitutes a class of problems that are very difficult to solve in practice. Although, the exact solution of these problems under certain special cases may be possible, for the general case, there are no known exact solution algorithms. Instead, approximate solution methods have been developed, either restricting the functional form or the feasibility space of recourse actions, these are generally referred to as “decision rules“. In this talk, we will present a review of existing decision rule approximations including affine and extended affine decision rules, uncertainty set partitioning schemes and finite-adaptability. We will discuss the reformulations and solution algorithms that result from these approximations. We will point out existing challenges in practical use of these decision rules, and point out current and future research directions. When possible we will point out the connections to multi-stage stochastic programming literature.
Federico Della Croce : The Longest Processing Time rule for identical parallel machines revisitedWe consider the P||Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines to minimize makespan. We revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969. LPT requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We provide new insights into LPT and discuss the approximation ratio of a modification of LPT that improves Graham’s bound. We use linear programming to analyze the approximation ratio of our approach. This performance analysis can be seen as a valid alternative to formal proofs based on analytical derivation. Also, we derive from the proposed approach an O(n log n) time complexity heuristic called SLACK. The heuristic splits the sorted job set in tuples of m consecutive jobs (1,...,m; m+1,...,2m; etc.) and sorts the tuples in non-increasing order of the difference (SLACK) between largest and smallest job in the tuple. Given this new ordering of the jobset, list scheduling is applied. This approach strongly outperforms LPT on benchmark literature instances and is competitive with more involved approaches such as COMBINE and LDM.
Panayotis Mertikopoulos : Online learning in multi-agent systems: Regret, equilibrium, and the road aheadFrom auctions to traffic planning and the training of adversarial neural nets, the goal of multi-agent learning is always the same: to make more informed decisions that lead to better rewards over time. But who benefits in the end? Each agent unilaterally? All agents concurrently? Both / None of the above? This tutorial is intended to explore these questions by providing an introduction to online optimization and learning from a multi-agent, game-theoretic viewpoint. We will cover the basics of learning in finite games (focusing on the multiplicative/exponential weights algorithm and its properties), and the mainstay algorithms for online optimization in continuous games (online gradient descent, follow the regularizer leader, etc.). We will also discuss the impact of the information available to the players, as well as a range of concrete applications to machine learning and operations research.
Bertrand Simon : Learning-Augmented Online AlgorithmsGuaranteed classical online algorithms are often designed in order to minimize the competitive ratio, i.e., the performance in the worst case, so usually do not perform well on easy inputs. An orthogonal approach has been developed in the last decade thanks to the progress in machine learning, which allows to predict key parameters of the instance. Its downside is that no guarantee can be given on the prediction quality, for instance if the training set does not represent the current instance. This statement is at the origin of the recently emerging field of learning-augmented algorithms. In this framework, an online algorithm has access to a predictor, which can give relevant information about the future instance, though without any guarantee on the quality. The objective is then to design an algorithm which performs well when the predictor turns out to be accurate, while being robust to imprecise predictions. This tutorial will introduce this new domain, present some recent works and discuss current research questions.
Christophe Lecoutre : About Modeling and Solving Combinatorial Constrained Problems (in Python)In this talk, we will start by introducing PyCSP3, which is a Python library that allows us to easily write models of combinatorial constrained problems. We will show how PyCSP3 can be useful to learn more about Constraint Programming (CP), notably by letting the user play with 60 Jupyter notebooks available at pycsp.org (concerning popular constraints, classical models and incremental solving). Then, we will focus on new advanced forms of constraints, combining intensional and extensional representations. These hybrid constraints are promising both for simplifying models and efficiently solving problem instances. Finally, we will discuss several hybrid forms of solving techniques, developed from connex domains: complete operations research approaches, local search and SAT.
Adam Ouorou : Méthodes d'optimisation convexe non différentiableNous passons en revue les id ées de base qui sous-tendent la vaste famille des algorithmes de minimisation des fonctions convexes non différentiables. Les méthodes les plus simples reposent sur la construction des modèles de la fonction à minimiser. Mais le manque de continuité d’information de premier ordre fait que ces modèles ne sont pas fiables même proche d’un optimum. Ceci motive l’introduction de différents moyens de stabilisation. Les méthodes basées sur les ensembles dits de localisation sont présentées de même que leurs améliorations par la stabilisation. Nous terminons par les approches exploitant les techniques d’accélération proposées par Nesterov pour les méthodes de gradient.
Jean-Bernard Lasserre : The Christoffel-Darboux Kernel for Data AnalysisIf the Christoffel-Darboux (CD) kernel is well-known in theory of approximation and orthogonal polynomials, its striking properties seem to have been largely ignored in the context of data analysis (one main reason being that in data analysis one is faced with measures supported on finitely many points (the data set)). In this talk, we briefly introduce the (CD) kernel, some of its properties, and claim that it can become a simple and easy to use tool in the context of data analysis, e.g. to help solve some problems like outlier detection, manifold learning and density estimation
|
| Personnes connectées : 3 | Vie privée |
|
