Ongoing and past curiosity-driven research projects
Computational Optimal Transport
Our group works on Computational Optimal Transport using Network Flow models and algorithms. We have developed a custom Parallel Network Simplex algorithm, which is competitive with state-of-the-art entropic regularized solvers.
Optimal Transport on grid graphs. We have proposed in the literature two very efficient models for solving Balanced Optimal Transport problems on regular grids.
Optimal Transport via Discrete Fourier Transforms. We have introduced a new Fourier-based metric mathematically equivalent to the Wasserstein distances of orders 1 and 2. This new metric can be used as a discrepancy function in Machine Learning tasks.
Computation of Wasserstein Barycenters. We have developed an efficient primal heuristic for the computation of Wasserstein Barycenters of order 2, and we have designed a Linear Programming model which can compute Wasserstein Barycenters of order 1 with a given numerical accuracy.
Optimal Transport for cells classification. We applied Optimal Transport to the biological framework of classifying cells between normal and malignant in patients affected by Acute Myeloid Leukemia. Specifically, starting from gene expression data, we have introduced a new measure of dissimilarity working well in classifying cells. In particular, our measure is competitive with other scores commonly used in the literature, such as Euclidean Distance and Pearson dissimilarity score.
The research group has strong expertise in developing branch-and-price and branch-and-cut algorithms for the solution of NP-hard combinatorial problems.
Currently, we are actively working on two research topis:
Generation of Hard-To-Solve instances for Combinatorial Problems. This project mostly focuses on generating hard-to-solve instances for combinatorial problems such as Travelling Salesman Problem, which is symmetric or asymmetric. In the literature, small instances of combinatorial problems are poorly available, and when provided, they can be solved in less than one second. We aim to propose new small instances that can be studied by hand.
Total Coloring and Total Matching Problems. The aim of this project is to propose exact approaches to tackle the Total Coloring Problem and the Total Matching Problem. Inspired by the high amount of literature on the Vertex coloring Problem and the Stable Set Problem, we address these two problems from a polyhedral point of view. Specifically, given a graph, the Total Coloring (TCP) asks for the minimum number of colors such that incident elements receive different colors. The Total Matching Problem (TMP) asks for a total matching of maximum size, where a total matching is a subset of vertices and edges that are pairwise independent. Both the problems are NP-hard and generalize the well-known Vertex and Edge Coloring problem, and, the stable set and matching problem.
The management of health services is characterized by decision problems with high computational complexity and aspects of uncertainty. We design new mathematical models and algorithms for different problems arising in healthcare management with the aim of providing decision support to decision-makers. Hybrid methods involving optimization, simulation, and data science methodologies are developed to consider the inherent stochasticity of these problems and to find the better trade-off between patient-centered and facility-centered objectives. Two main lines of research can be identified:
Scheduling: operating room planning and scheduling, online resource allocation in an emergency department, radiotherapy scheduling, online patient scheduling in a radiology department, and multi-phase job scheduling in a medical 3D printing laboratory.
Vehicle routing: team orienteering problems for ambulance routing in post-disaster management and home COVID-19 test collection.
Interpretable Machine Learning
The research group is working on the development of Machine Learning models and algorithms based on interpretable mathematical models that can provide explainable outcomes. Currently, we are developing exact Mixed Integer Programming models for classifying time series.
One of the main EU policy priorities under the European Green Deal is to achieve climate neutrality by 2050. Transport is a key player in that task, as it is a major energy consumer and contributes significantly to greenhouse gas emissions. Rail and buses, in particular, can represent a more sustainable mode of transport. To monitor the performance of public transport in the EU and to be able to inform the relevant policy decisions on the topic, we use comprehensive data to compute performance and accessibility-to-opportunities measures associated with different types of public transport.
Underneath these measures are hidden different Operations Research challenges. One example is the computation of accessibility measures across Europe, which is related to a schedule-based, time-dependent, all-pairs scheduling problem on very large multimodal networks.
Robust Optimal Power Flow
Development of models and algorithms regarding the Optimal Power Flow problem in a stochastic setting that arises from Renewable Energy Sources.
Past European Research Projects
Spatial-KWD, Eurostat 2020
The goal of this project was to design and implement an open-source library for the computation of exact and approximate Kantorovich-Wasserstein distances between pairs of very large-scale spatial maps. The exact method is intended for the validation on small to medium size instances of the results obtained via an approximate method (with bound guarantees) that should scale to larger-size instances.
The core of the algorithm is based on a recent efficient implementation of the Network Simplex on sparse graphs. The core algorithm includes additional features, such as the possibility of dealing with non-convex input maps, the computation of distances between unbalanced maps, and a key incremental sub-procedure that can be used to estimate the spatial density within a focused sub-area.
FastPath, EU-JRC 2017
The goal of this project was to design and implement a time-dependent shortest-path solver that
Exploits the specific structure of road networks
Takes into account the time variability in arcs traversal (e.g., due to traffic conditions in peak hours)
Scales smoothly with the size of the road network, which can have millions of nodes and arcs.
The project's main outcome was a detailed technical specification of the proposed time-dependent shortest path solver, along with corresponding source code developed in ANSI standard C/C++17 and an MS-Window solver, callable from the command line.
Technical report and software library developed in C++ delivered to EU-JRC