Development and applications of a Frank-Wolfe algorithms

2022-06-03 -Mathieu Besançon Zuse Institut Berlin (ZIB)

Frank-Wolfe algorithms are first-order methods that support structured convex constraints, over which linear optimization can be performed efficiently.
We present FrankWolfe.jl, a library for flexible and high-performance Frank-Wolfe algorithms. In particular, we will detail design choices that allow warm starts, scaling to large problems and some use cases leveraging those features.

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.