Development and applications of a Frank-Wolfe algorithms
2022-06-03 -Mathieu Besançon Zuse Institut Berlin (ZIB)
A discussion of probability functions
2022-05- 12 -Wim van Ackooij, research expert at EDF R&D
In this talk we will discuss some recent insights in the study of probability functions. We will explore a particular setting that allows us not only to obtain naturally a reduction in sample variance, but that is also favorable for the derivation of theoretical insights. The latter can comprise results regarding convexity, but also differentiability. We will discuss several results of the latter type and show how they can be put to work numerically.
On the solution of separable nonlinear programs to arbitrary numerical precision
2022-03-22 Sandra Ulrich Ngueveu (LAAS CNRS Toulouse)
We consider the problem of minimizing the sum of a series of univariate (possibly non-convex) functions on a polyhedral domain. We introduce an iterative method with optimality guarantees to approximate this problem to an arbitrary numerical precision. It solves a series of piecewise linear approximations of the problem in a way that the tractability of the resulting MIPs is not compromised along the process. A key in its success is the reliance on precision-driven tightening mechanisms rather than domain-driven tightenings. Our method also uses a refinement algorithm known as LinA that is proven to provide a minimal-sized piecewise linear approximation for a given target precision. The convergence of the method in a finite number of iterations is assured under very mild assumptions, and no NLP nor MINLP solver/oracle is required to ever be invoked to do so. We also show that in the worst case, our method performs O(log(n)) iterations, where n is the maximum number of iterations required by other adaptive partitioning based algorithms from the literature to achieve the desired precision. By keeping the scope of the updates local, the computational burden is only slightly increased from iteration to iteration. As a consequence, our method presents very nice scalability properties and is little sensitive to the desired precision. We illustrate its efficiency in approximating the non-linear variants of three problems: the transportation problem, the capacitated facility location problem, and the multi-commodity network design problem.
Tutorial on Constraint Programming
2022-03-31 –Hugues Wattez (LIX)
Introduction à l’Informatique Quantique
Simon Perdrix (INRIA-LORIA) 2022-03-10
Journée Indistrielle du DIX & LIX
Ce tutoriel sera l’occasion d’une introduction à l’informatique quantique, de la présentation des postulats de la mécanique quantique décrits avec un point de vue d’informaticien, aux premiers algorithmes quantiques, en passant par le modèle des circuits quantiques. On évoquera également quelques enjeux actuels de la recherche en informatique quantique.
Autonomous electric vehicles for passenger transport and last mile deliveries in cities
2022-02-03 –Jakob Puchinger (IRT SystemX/CentraleSupélec)
Connected autonomous vehicles for urban mobility and freight delivery have not been deployed at a large scale yet, contrary to many prediction from a few years ago. What where the promises and fears? How will increasing robotisation and connectedness shape our cities? What about the people living in the cities? After discussing this context, some of the research at the Anthropolis chair will be presented ranging including simulation and optimization based approaches for shared autonomous vehicle services and robot deliveries.
To Quadratic Outer Approximation for Convex MINLP and Beyond
2021-01-27 – Luca Mencarelli (UMA, ENSTA Paris)
In this seminar we consider convex Mixed Integer Nonlinear Programming (MINLP), i.e., mixed integer optimization problems with convex objective function and constraints. In the first part of talk we introduce a Quadratic Outer Approximation framework for convex MINLP and we discuss several strategies to determine convex quadratic underestimations of convex functions. Then, we present a QP/NLP-based Branch-and-Bound scheme obtained by generalizing the LP/NLP-based Branch-and-Bound introduced by Quesada and Grossmann in their 1992 seminal paper. Preliminary promising computational results will be presented and discussed.
Constrained smoothing and
out-of-range prediction using P-splines
2021-01-13 – VANESA GUERRERO LOZANO (Carlos III University of Madrid)
In an era when the decision-making process is often based on the analysis of complex and evolving data, it is crucial to have systems which allow to incorporate human knowledge and provide valuable support to the decider. In this work, statistical modelling and mathematical optimization paradigms merge to address the problem of estimating smooth curves and hypersurfaces which verify structural properties, both in the observed domain in which data have been gathered and outwards. We assume that the smooth curve (resp. hypersurface) to be estimated is defined through a reduced-rank basis (B−splines) and fitted via a penalized splines approach (P−splines). In order to incorporate requirements about the sign, monotonicity and curvature in the fitting procedure, a conic optimization model is stated and solved which, for the first time, successfully conveys out-of-range constrained forecasting.
This approach is successfully applied to simulated and demographic data, as well as to data arising in the context of the COVID-19 pandemic. If a smooth curve is fitted using an unconstrained approach, misleading results might be depicted. That is the case of, for instance, curves depicting a negative number of infected people in certain time periods. Furthermore, forecasting the evolution of the pandemic under a different set of constrained scenarios, such as having an estimated growth rate, is also possible using the approach developed in this work.
On deterministic global optimization
2021-12-09 – Frédéric Messine (LAAS CNRS Toulouse)
Proteins Three-Dimensional Structure Characterization by Distance Geometry
2021-10-28 – Wagner Alan Aparecedo Rocha (Universidade Estadual de Campinas, Brazil)
To find a protein 3D structure considering a set of close Euclidean distances between its atoms is an NP-difficult problem known in the literature as the Molecular Distance Geometry Problem (MDGP). Assuming that the set of distances is given by a Nuclear Magnetic Resonance (NMR) experiment, it is possible to model the MDGP with a simple, weighted, and undirected graph. In this seminar, we will show how we solved the MDGP using a combinatorial approach based on an exploration order of graph vertices associated with the NMR information.
Random projections applied to mathematical programming
2021-09-30 – Leo Liberti (LIX-CNRS)
Towards sustainable cities: an economic approach of greener housing and mobility
2021-11-25 – Edouard Civel (LIX)
Piecewise models for Sequential Convex MINLP technique
2021-06-16 – Renan Spencer Trindade (LIX)
Hypergraph Partitioning for Compiling Pseudo-Boolean Formulae
2021-05-19 – Romain Wallon (LIX & CRIL)
Numerous problems in artificial intelligence can be expressed as conjunctions of constraints over Boolean variables (taking either the value 0 (false) or 1 (true), often represented with formulae in conjunctive normal form (CNF). On such representations, so-called modern SAT solvers are very efficient in practice. However, these solvers are limited by the weakness of the resolution proof system they use internally. A possible workaround is to replace this proof system by the cutting planes proof system, which also allows to deal with pseudo-Boolean constraints (authorizing the use of coefficients in the constraints). However, this is often not enough to offer time guarantees on the resolution of the considered problems, which are NP-complete. When such guarantees are needed (e.g., for applications involving interactions with users), one may compile the input problem into a different language, in which the wanted operations can be applied efficiently (ideally, in polynomial time). In this context, it is often convenient to consider graph or hypergraph representations of the input problem, which provide information about its structure. For instance, current compilers exploit the partitioning of these graphs to decide in which order variables should be assigned. In this presentation, we will present different (hyper)graph representations of CNF formulae, and study how their partitioning may allow to find smaller compiled form for these problems. We will also present how this technique may be extended to allow the compilation of pseudo-Boolean formulae.
Mathematical Programming for UAM tactical deconfliction
2021-05-05 – Mercedes Pelegrin (LIX)
Urban Air Mobility (UAM) will exploit the third dimension to smooth ground traffic in
densely populated areas. On-line automated air traffic management will be key to ensure safety and optimize airspace capacity. Airspace conflict management consists of three layers : strategic deconfliction, which takes place before departure, tactical deconfliction to maintain separation provision during flight, and collision avoidance to avoid imminent conflicts. This work addresses the problem of tactical deconfliction in UAM, considering different sources of unexpected traffic disruptions:
— Scenario 1 : Some trips missed their departure and/or an in-flight trip suffered a drift.
— Scenario 2 : A new operation must be accommodated with high priority.
— Scenario 3 : A non-collaborative intruder is expected to cross the UAM network.
We propose a mathematical programming model that generalizes the problem of tactical deconfliction for the three scenarios. The UAM network is modeled with a graph, while vehicle separation is modeled with linear constraints defined on this graph. Different objectives are considered, including time deviation from the nominal schedule, delays of priority trips, and maximum delays at destination. A restriction of the resulting mixed integer program where schedules of trips that are not directly affected by the disruptions are fixed is also considered. This is contemplated as a local model, where only the pairs of trips containing a disrupted or unexpected flight can receive adjustments. We test our model on three synthetically generated topologies of the UAM network representing different underlying urban configurations. Maximum traffic congestion is simulated. We explore the benefits of using global deconfliction over a local approach. The different objective functions will be also compared, analyzing implications concerning solution fairness.
Distance geometry for word embeddings and applications
2021-04-09 – Sammy Khalife (LIX)
Reformulating particular bilevel programs with quadratic lower level
2021-03-24 – Martina Cerulli (LIX)
We focus on a particular class of bilevel programs with a quadratic lower level, which can be obtained reformulating semi-infinite problems with an infinite number of quadratically parametrized constraints. We propose a new approach to solve this class of bilevel programs, based on the dual of the lower level problem and which can lead to a convex or a semidefinite programming problem depending on the parametrization of the lower level with respect to the upper level variables. This approach is compared with is a tailored cutting-plane algorithm, of which we discuss the convergence. We test these two methods on several instances of two applications: the constrained quadratic regression and a zero-sum game with cubic payoff.
Dantzig Wolfe Reformulation for Non-Linear Problems
2021-03-10 – Emiliano Traversi (LPN-CNRS)
Solving the SDP relaxation of the Alternative-Current Optimal Power Flow Problem: State-of-the-art and an ongoing work
2021-02-03 – Antoine Oustry (LIX)
The Alternative-Current Optimal Power Flow (AC-OPF) problem is a major topic in power systems optimization, that essentially focuses on taking into account the transmission network’s characteristics. This is why this problem is of interest for Transmission System Operators (TSO) like « Réseau de transport d’électricité » (Rte) in France. The AC-OPF is a very challenging non-convex problem, written in complex numbers, and solving it to global optimality is still impossible for instances of realistic size. The Semidefinite programming (SDP) relaxation of the AC-OPF is known to give good lower bounds, that may be used to evaluate the optimality gap of a heuristically found solution, or possibly to implement a spatial branch-and-bound algorithm. In this talk, we will describe the state-of-the-art methods to solve the SDP relaxation, which are all based on a SDP completion theorem for matrices with a chordal sparsity pattern. We will also present a method under development, which is quite independent of the methods that we will have presented before. This method consists in solving the SDP dual of the AC-OPF, « natively » expressed in complex variables, with a bundle algorithm.
Algorithmic configuration by learning and optimization
2021-01-20 – Gabriele Iommazzo (LIX)
In this seminar, I will present the main research topics that my supervisors and I have been working on during my Ph.D., and which lie at the intersection of Machine Learning (ML) and Mathematical Programming (MP). The main contributions tackle the Algorithm Configuration Problem (ACP) and the Distance Geometry Problem (DGP). The ACP is the problem of configuring a target algorithm with the parameter setting providing optimal algorithmic performance, for solving a given input. We propose two novel approaches to the ACP, both based on a two-fold process combining ML and MP techniques, and employ them to configure the IBM ILOG CPLEX optimization solver. The DGP consists in finding a realization of a simple, undirected, weighted graph, in a Euclidean space of given dimension, where the edges are realized as straight segments of length
equal to the edge weights. A customary approach to the DGP is to solve a MP to determine the position of the vertices in the given Euclidean space. We propose a new MP formulation where, instead, we consider the cycles of the graph, and we decide the length of the segments modelling the edges of each cycle.