Tutorials
 |
Ruslan Sadykovreceived his Ph.D. degree in 2006 at CORE, Université Catholique de Louvain in Belgium. He was a postdoctoral researcher in Ecole Polytechnique in Paris before joining the ReAlOpt team at Inria Bordeaux — Sud-Ouest as a research fellow in 2008. He was a visiting researcher at Universidade Federal Fluminense, Niteroi, Brazil during one year in 2015-2016. His research interests are in decomposition approaches for solving combinatorial optimization problems with main applications in vehicle routing, scheduling, cutting and packing.
Topic: Modern Branch-and-Cut-and-Price for Vehicle Routing Problems
The Vehicle Routing Problem(VRP) was introduced 60 years ago by Dantzig and Ramser and until now it remains one of the most widely studied problems in combinatorial optimization.
During the last 12 years the combination of cut and column generation has been the dominant approach for solving exactly most classic variants of this problem.
Modern branch-and-cut-and-price algorithms incorporate several techniques proposed by different authors. Each of them is essential for achieving state-of-the-art performance.
In this tutorial I will review these techniques after introducing the basic branch-and-price algorithm.
Computational results for several problem variants will reveal that many instances of a practical size can now be solved exactly in a very reasonable time.
|
| | |
 |
Sandra Ulrich Ngueveu received her Ph.D. degree in 2009 at UTT, Université de Technologie de Troyes in France. She joined Toulouse INP and the ROC research team of the LAAS-CNRS as an associate professor in 2010. Her main research interests are in energy optimization and in combinatorial optimization problems in graphs (in particular vehicle routing). She recently focused on the integration of the physical characteristics of energy sources in combinatorial optimization problems with applications to smart grids, hybrid electric vehicles, production planning. This line of research resulted into a more general framework based on the piecewise linear bounding of nonlinear univariate functions to solve certain classes of non linear optimization problems (3rd Robert Faure prize 2018).
Topic: Linearization techniques for MINLP: recent developments, challenges and limits
Various optimization problems result from the introduction of nonlinear terms into combinatorial optimization problems.
In the context of network design optimization for example, taking into account congestion effects or flow dependent economy of scales may result into mixed integer nonlinear problems neither convex nor concave.
We take a fresh look at state-of-the-art linearization and approximation techniques. We show in particular how to ensure an a priori guarantee on the quality/feasibility of the solution, a reduction of the size of the converted problem and a minimization of the computing time.
This tutorial will be illustrated with two cases studies: network design with congestion and energy optimization with non-linear demand/cost functions.
|
|
