PGMO Seminars 2016
December 13, 2016
- Jose A. Montoya "The technician routing problem with conventional and electric vehicles"
This presentation introduces the technician routing problem with conventional and electric vehicles (TRP- CEV), which is inspired by the technician routing problem of ENEDIS. This problem consists in routing a set of technicians to serve a set of customers, using a fleet composed by electric vehicles (EVs) and conventional vehicles (CVs). It considers several real-life constraints such as: time windows of the requests, working schedules and lunch breaks of the technicians, skills incompatibility between technicians and request, incompatibility between charging stations and EVs, autonomy of the EVs, nonlinear charging function, and a limited number of vehicles for each type. Decisions that must be taken simultaneously are the vehicle-to-technician assignment, the route construction, and the battery charging program.
To solve the TRP-CEV we propose a parallel matheuristic (PMa). This approach decomposes the TRP- CEV into a set of VRP-TW and eVRP-TW with lunch break (one for each couple technician-vehicle), and solves each sub-problem in parallel using a greedy randomized adaptive search procedure (GRASP). Later, PMa uses a set covering model to assemble a TRP-CEV solution. We built a set of real instances based on the ENEDIS operation. The aim of these instances is to evaluate the performance of the PMa, and to analyse the features of the solutions under the light of some important metrics for ENEDIS. Finally, we analyze the solutions delivered by PMa for the TRP-CEV aiming to provide some insight about the behaviour of costs, emissions, and visits to CSs for different compositions of the fleet.
October 19, 2016
- Miguel F. Anjos "Smart Grids and Optimization: A Winning Combination"
A smart grid is the combination of a traditional electrical power system with information and energy both flowing back and forth between
suppliers and consumers.
This new paradigm introduces major challenges such as the integration of intermittent generation and storage, and the
need for electricity consumers to play an active role in the operations of the system.
We will summarize the opportunities provided by smart grid to the optimization community, and illustrate one such opportunity through some recent research on optimal aggregation of energy resources (joint work with F. Gilbert, P. Marcotte, and G. Savard).
June 9, 2016
- Jean-Pierre Dussault (Sherbrooke University) "Unconstrained optimization of differentiable functions"
Méthodes de régularisation pour l'optimisation sans contrainte de fonctions différentiables
Any local minimizer of a differentiable function satisfies the necessary optimality conditions stating that its gradient vector vanishes and its hessian matrix is semi-definite positive (SDP).
Therefore, computing a local minimizer amounts to solving the system of equations described by its vanishing gradient.
Since we search a local minimum, we may resort to an iterative descent algorithm which guarantees that from any starting point, cluster points will have vanishing gradients and SDP hessian matrices.
This desirable global convergence property distinguishes optimization problems from general system of equations. When studying the convergence properties of descent algorithms, in classical numerical analysis, we predict the efficiency of a given algorithm by its asymptotic convergence order/rate.
Another theoretical tool to predict efficiency is its worst case complexity behavior.o One important descent algorithm is the so called trust region (TR) scheme. Recently, a closely related algorithm, Adaptive Regularization using Cubics (ARC) attracted much interest.
Its principle, introduced by Nesterov and Polyak was embedded in a practical ARC by Cartis, Gould and Toint. ARC has the best known worst case complexity. In this talk, we will first review basic notions of asymptotic convergence order and worst case complexity to classify many algorithms.
ARC possesses the best known theoretical properties with respect to efficiency. We will then concentrate on TR and ARC algorithms. We review trust region and ARC algorithm families and introduce a new variant, ARCq.
Our unified presentation aims at stating in a simple way the properties of the different variants.
Finally, we discuss implementation issues of ARCq to show how its theoretical efficiency predictions lead to a practical efficient computing tool.
May 31, 2016
- Yuriy Zinchenko (University of Calgary) "CVaR bounds with partial dependence information"
Attaining full knowledge of the dependence amongst a group of observed random variables represents a very difficult task, as is illustrated by many practical situations. Instead, it is more feasible to assume that we have reliable models for individual random variables with some partial knowledge of the dependence. In contrast, many decision-making problems require to assess the aggregate risk level associated with a sum of random variables. In turn, the latter implicitly necessitates us to determine the most and least favorable plausible dependence models amongst the variables. We propose a numerical method to evaluate the lower and upper bounds on Conditional Value at Risk (CVaR) –a widely known risk measure in mathematical finance– for a sum of random variables. We assume that the marginal distributions of the variables are known, and the dependence uncertainty is described via lower-orthant stochastic ordering. Our method is based on convex optimization. More precisely, the method follows a CVaR characterization proposed by Rockafellar and Uryasev, and is hinged on recognizing partial convexity of some special bi-linear program. For portfolios with two risks, it is known that CVaR ordering coincides with the lower-orthant stochastic ordering of the underlying bi-variate distributions. Yet, no similar result has been established or disproved for higher dimensions. As a bi-product of our analysis, using elementary linear programming techniques, we show that no such extensions are possible.
May 26, 2016
- Ider Tseveendorj (UVSQ) "Piecewise Convex Maximization Problems: Optimality Conditions and Algorithms"
During the last decade we have been focusing on tools for solving problems of maximizing nonconvex functions that can be defined by the pointwise minimum of convex functions.
Such piecewise convex functions seem to us as a natural extension of the piecewise affine approximation from convex analysis.
In this presentation, we provide a brief overview of optimality conditions, methods and some attempts to solve this difficult nonconvex optimization problem.
May 26, 2016
- Carola Doerr (UPMC) "Spotlight on the Analysis of Evolutionary Algorithms"
Evolutionary algorithms (EAs) form a powerful class of optimization techniques for both industrial and academic applications. A large research community exist that studies EAs from a scientific angle. In this talk, we show that EAs and other randomized search heuristics are also interesting from a mathematical point of view. We provide an example showing how running time analysis and complexity theory have inspired the development of a novel algorithm which provably outperforms existing techniques in evolutionary computation. Our example also affirmatively answers one of the main open questions in EA theory, namely the usefulness of crossover (i.e., the recombination of two or more search points) on simple fitness landscapes.
The talk is based on joint work with Benjamin Doerr (Ecole Polytechnique, France), Franziska Ebel (Saarland University, Germany), Timo Koetzing (HPI Potsdam, Germany), and Johannes Lengler (ETH Zuerich, Switzerland).
April 26, 2016
- Robert Basset (UC Davis) "Duality Between Epi-spline Estimation and Control"
We examine the problem of estimating the state of a particle which evolves according to a stochastic dynamical system, based only on observing noisy measurements of that system. In particular, we examine the case where the noise terms can be described by a density modeled by an exponential epi-spline. This framework generalizes many classical estimation problems, among the most important of which is when the noise terms are Gaussian and the loss is Mean-squared error. We develop optimality conditions for this class of problems and discuss the duality connection between this framework and optimal control. By appealing to algorithms in optimal control, we open up a new class of computational tools--those from optimal control--for application to estimation problems.
March 3, 2016
- Stéphane Canu (INSA Rouen) "Mixed integer programming for sparse and non convex machine learning"
Many problems in machine learning can be recast as mixed 0-1 integer programs (MIP). This the case of classification, clustering, variable selection, outlier detection, 3d image reconstruction, low rank matrix factorisation. Despite the computational complexity of integer optimization, hardware improvements combined with algorithmic advances and better formulation
makes it possible to consider this kind of approach for solving moderate size machine learning problems. We will introduce MIP and discussed their theoretical and practical interests. In particular, we will see how to do regression and SVM with both variable selection and outlier detection in this framework. Practical implementations issues will be also discussed and illustrated on both synthetic and real datase
- José Alejandro Montoya (University of Angers) "Contributions to the electric vehicle routing problems"
Electric vehicles (EVs) are one of the most promising technologies to reduce petroleum dependency and greenhouse gas emissions. This has led to an increase in the use of EVs in freight and passenger transportation. However, EVs have less autonomy than combustion vehicles, due to the limited capacity of the batteries. In a typical distribution operation EVs have to visit charging stations (CSs) to complete their routes. This situation gives birth to a new family of vehicle routing problems (VRPs), the so-called electric VRPs (eVRPs). In this project, we address three studies related with eVRPs. In the first study, we focus on the green vehicle routing problem (Green VRP). This is the first eVRP in the literature that considers the possibility of recharging an EV at a CS along the route. To tackle the Green VRP, we propose a simple, yet effective, two-phase heuristic. To test our approach, we performed experiments on a set of 52 instances from the literature. The results show that our heuristic is competitive with state-of-the-art methods. In the second study, we introduce the electric vehicle routing problem with partial charging and nonlinear charging functions (eVRP-PNL). In contrast to most existing eVRPs, the eVRP-PNL considers realistic assumptions about the charging process like nonlinear charging functions and partial charging. Using a computational experiment, we show that disallowing partial charging and neglecting the nonlinear nature of the charging functions leads to solutions that may be infeasible or overly expensive. Finally, in the third study, we propose an iterated local search (ILS) to tackle large-scale eVRP-PNL instances. This ILS relies heavily on solving a subproblem that we defined as the fixed-route vehicle-charging problem with nonlinear charging function. To test our approach, we perform experiments on a set of 120 randomly generated instances. The results show that our ILS is an effective approach to tackle large-scale eVRP-PNL instances.
January 26, 2016
- Didier Aussel (Université de Perpignan, France) "Two applications of Bilevel problems: industrial eco-parks and about the (correct) reformulation of bilevel problems involved in electricity market models"