2021-06-16 – Renan Spencer Trindade
2021-05-19 – Romain Wallon
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.
2021-05-05 – Mercedes Pelegrin
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.
2021-04-09 – Sammy Khalife
2021-03-24 – Martina Cerulli
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.
2021-03-10 – Emiliano Traversi
2021-02-03 – Antoine Oustry
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.
2021-01-20 – Gabriele Iommazzo
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.