Seminar title: Computational Research 101
Date: May 17th, 2023 -16:15, Aula C8 (Engineering building) or Zoom
Abstract: Computational research is a key ingredient in many fields. However, researchers often lack formal training in experimental design and, in particular, in software engineering. In this talk we will review basic principles and best practices, covering experimental setup, data analysis and writing maintainable code.
Seminar title: Learning with combinatorial optimization layers and applications to dynamic vehicle routing
Date: April 19th, 2023 -16:15, Aula C8 (Engineering building) or Zoom
Abstract: Combinatorial optimization (CO) layers in machine learning (ML) pipelines are a powerful tool to tackle data-driven decision tasks, but they come with two main challenges. First, the solution of a CO problem often behaves as a piecewise constant function of its objective parameters. Given that ML pipelines are typically trained using stochastic gradient descent, the absence of slope information is very detrimental. Second, standard ML losses do not work well in combinatorial settings. A growing body of research addresses these challenges through diverse methods. Unfortunately, the lack of well-maintained implementations slows down the adoption of CO layers. Building upon previous works, we introduce a probabilistic perspective on CO layers, which lends itself naturally to approximate differentiation and the construction of structured losses. We recover many approaches from the literature as special cases, and we also derive new ones. Based on this unifying perspective, we present InferOpt.jl, an open-source Julia package that 1) allows turning any CO oracle with a linear objective into a differentiable layer, and 2) defines adequate losses to train pipelines containing such layers. Our library works with arbitrary optimization algorithms, and it is fully compatible with Julia's ML ecosystem. In the second part of the talk, we focus on the dynamic vehicle routing problem of the 2022 EURO-NeurIPS challenge (1). Using a CO layer in a deep learning pipeline enabled to win the challenge. We focus on the structure of the pipeline used as a policy, and on the algorithm used to train it, which are natural applications of the probabilistic perspective introduced during the first part of the talk.
Seminar title: A genetic approach to Event-Interval Sequence Interpretable Classification
Date: March 28th, 2023 -11:30, Zoom
Abstract: Sequences of event-intervals appear in several application domains including sign language, sensor networks, medicine, human motion databases, and linguistics. Such sequences comprise events that occur at time intervals and are time stamped at their start and end time. In this talk, we propose and study a genetic approach to perform supervised classification of event-interval sequences. Our method combines machine learning techniques with evolutionary dynamics to provide interpretable outcomes.
Martina Fischetti and Juan Nicolás Ibáñez
European Commission’s Joint Research Centre (EC-JRC)
Seminar title: Routing over large (public and private) transport networks across Europe: challenges and opportunities
Date: February 14th, 2023 -16:00, Aula Beltrami and Zoom
Abstract: A well-functioning transport system is not only critical to European businesses and global supply chains, and as a rather important economic activity, contributing in the European Union (EU) to around 5% of GDP and more than 10 million jobs, but also critical to guarantee that European citizens have access to essential services such as education, healthcare, or employment. This compounds with the fact that the transport system is relatively hard to decarbonise, and a sector that brings many external costs to the society (GHG and pollutant emissions, noise, road crashes and congestion). Against this context, the transport sector plays a key role in one of the main EU policy priorities under the European Green Deal, the achievement of climate neutrality by 2050. The EU mandate includes the monitoring across all Member States of the deployment and the evaluation of the performance of both public and private transport infrastructure. This is used to inform relevant policy initiatives on issues such as guaranteeing a level playing field for competition across transport modes or identifying where funding is most needed to ensure access to an affordable and sustainable transport system. In this talk we will present details of different lines of work in the European Commission’s Joint Research Centre (EC-JRC) to support the abovementioned mandate, providing an overview of some of the transport-related modelling challenges faced and some of possible solution methods proposed. More elaboration will be provided on methodologies developed by the EC-JRC that focus on employing comprehensive (EU-wide) data to compute performance and access-to-opportunities metrics associated with different modes transport, underlining the network (graph building and routing) challenges addressed to compute these metrics with a sufficiently high level of spatial detail for the scale of interest (EU-wide). The discussion will refer to methodologies that exploit routing over large transport networks, for both private (road) and public (railways, buses, etc.) means of transport. On the latter we will present results from an ongoing collaboration with the Department of Mathematics of the University of Pavia on an implementation of an innovative method for fast computation of all-to-all routing over large schedule-based network graphs.
Seminar title: Incremental knapsack problems
Date: November 29th, 2022 - 15:00, Aula Beltrami
Abstract: In this talk, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. We will mostly focus on incremental versions of the classical knapsack. In such models, we are given an added time component and weakly increasing capacities for each time, as to mimic the increase in available resources. Items can be inserted at any time, but once an item is inserted, it cannot be removed in future times. The goal is to maximize some item-dependent, and possibly also time-dependent, objective function under such constraints. We will present algorithms that perform well in theory and/or in practice for incremental knapsack problems and their extensions.
Based on joint work with Danny Segev (Tel Aviv) and Lingyi Zhang (Columbia-> Uber)
Short Bio: Yuri Faenza is an associate professor in the IEOR department at Columbia University. He works in discrete optimization, operations research, matching theory, and their applications. His research has been funded by the NSF (including an NSF Career award), the ONR, the Swiss NSF, and by a Meta Research Award.
Seminar title: Semidefinite Lift-and-Project relaxation for the Stable Set Problem
Date: November 16th, 2022 -14:30, Aula Beltrami
Abstract: The stable set problem is one among the fundamental problems in combinatorial optimization and it is well-known to be NP-hard, hence no polynomial time algorithm to solve it exactly is expected to exist unless P=NP. Thus, the study of strong relaxations for this problem is a well-researched topic. In particular, the Lovász theta function θ(G) provides a good upper bound on the stability number of any graph G. It can be computed in polynomial time by solving a semidefinite program (SDP), which in addition turns often out to be fairly tractable in practice. As a consequence, θ(G) achieves a hard-to-beat trade-off between computational effort and strength of the bound. Hierarchies of relaxations to strengthen θ(G) towards the stability number have been documented, but in general such improvements come at a heavy computational burden with off-the-shelf SDP algorithms and require highly specialized methods to be addressed.
In the last decades, Lift-and-Project methods have gained a lot of attention, being able to generate strong relaxations for combinatorial optimization problems. In particular, starting from any linear relaxation Lovász and Schrijver’s Lift-and-Project framework generates a semidefinite relaxation. Its application to the fractional stable set polytope showed its potential, producing bounds stronger than θ(G) but in general they come at a nontrivial computational cost.
In this talk we introduce a new semidefinite relaxation for the stable set problem obtained by the lifting of a more compact linear formulation than the classical one. Then, we characterize some classes of valid inequalities for the stable set polytope which are implied by our proposal. We then discuss how to face the computational burden arising from these semidefinite programs by the employment of a general purpose solver for SDPs.
Alternating Direction Methods of Multipliers (ADMMs) represent the most popular alternative to interior-point methods for solving SDPs. As first-order methods, ADMMs are suited to scale to much largers SDPs, at some cost in accuracy that should be correctly addressed when bounding the optimal solution of some combinatorial optimization problem. Here we discuss different methodologies to compute a valid bound on the optimal value of the SDP starting from a medium accuracy solution and we discuss the employments of these methodologies within ADMMs.
Seminar title: Scheduling appointments for blood donation: from donations at the collection center to home blood donation
Date: November 9th, 2022 -11:30, Aula Beltrami
Abstract: Blood plays a crucial role in all health care systems, it is a limited resource and its shelf life is short. In Western countries, blood is collected from donors, and the so-called Blood Donation Supply Chain (BDSC) aims to provide an adequate supply of blood units to transfusion centers and hospitals.
Short Bio: Ettore Lanzarone is a tenure-track assistant professor at the Department of Management, Information and Production Engineering of the University of Bergamo. His research focuses on optimization, and stochastic model applied to bioengineering problems, operations research applications in health care, and stochastic differential equations.
Seminar title: Imposing contiguity constraints in political districting models
Date: June 21st, 2022
Abstract: Beginning in the 1960s, techniques from operations research began to be used to generate political districting plans. A classic example is the integer programming model of Hess et al. (Operations Research 13, 998-1006, 1965). Due to the model’s compactness-seeking objective, it tends to generate contiguous or nearly contiguous districts, although none of the model’s constraints explicitly impose contiguity. Consequently, Hess et al. had to manually adjust their solutions to make them contiguous. Since then, there have been several attempts to adjust the Hess model and other models so that contiguity is explicitly ensured. In this talk, we review two existing models for imposing contiguity, propose two new ones, and analytically compare them in terms of their strength and size. We conduct an extensive set of numerical experiments to evaluate their performance. While many believe that contiguity constraints are particularly difficult to deal with, we find that the districting problem considered by Hess et al. does not become harder when contiguity is imposed. In fact, a branch-and-cut implementation of a cut-based model generates, for the first time, optimally compact districting plans for 21 different US states at the census tract level. To encourage future research in this area, and for purposes of transparency, we make our test instances and source code publicly available. This is joint work with Hamidreza Validi and Eugene Lykhovyd.
Seminar title: A Bayesian approach to the problem of forecast reconciliation
Date: May 24th, 2022
Abstract: Often time series are organized into a hierarchy. For example, the total visitors of a country can be divided into regions and the visitors of each region can be further divided into sub-regions. Forecasts of hierarchical time series should be coherent; for instance, the sum of the forecasts of the different regions should equal the forecast for the total. The forecasts are incoherent if they do not satisfy such constraints.
Reconciliation methods proceed in two steps. First, base forecasts are computed by fitting an independent model to each time series and ignoring the sum constraints. Then, the base forecasts are adjusted to become coherent; this step is called reconciliation. Besides being coherent, reconciled forecasts are generally more accurate than the base forecasts, as they benefit from information coming from multiple time series.
In this talk, we show how forecast reconciliation can be addressed by taking a Bayesian viewpoint.
Seminar title: Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric
Date: April 6th, 2022
Abstract: The seminar aims at presenting a method to solve stochastic problems where the distribution of the uncertain parameters is only observable through a small training dataset. In particular, an ambiguity set will be defined using the Wasserstein metric, and we will seek decisions that perform best in view of the worst-case distribution within the ambiguity set. We will see that this type of problem has nice (convex or even linear) reformulations in many cases of practical interests. The talk will be concluded with the presentation of a numerical test.
Seminar title: What Makes Neural Networks So Expressive, and What Could Make Them Smaller? Some Answers Based on Polyhedral Theory and Mixed-Integer Linear Programming
Date: March 31st, 2022
Abstract: Neural networks have been successfully applied to complex predictive modeling tasks in areas such as computer vision and natural language processing. On the one hand, they have been shown to be a very powerful mathematical modeling tool: a neural network can model a piecewise-linear function with an exponential number of pieces with respect to its number of artificial neurons. On the other hand, we may still need an unreasonably large neural network in order to obtain a predictive model with good accuracy in many cases. How can we reconcile those two facts?
In this talk, we apply traditional tools from operations research to analyze neural networks that use the most common type of artificial neuron: the Rectified Linear Unit (ReLU). First, we investigate both theoretically and empirically the number of linear regions that networks with such neurons can attain, which reflect the number of pieces of the piecewise linear functions modeled by those networks. With respect to that metric, we unexpectedly find that sometimes a shallow network is more expressive than a deep network having the same number of neurons. Second, we show that we can use optimization models to remove units and layers of a neural network while not changing the output that is produced, which thus implies a lossless compression of the network. We find that such a form of compression can be facilitated by training neural networks with certain types of regularization that induce a stable behavior on its neurons.
This talk is based on papers coauthored with Christian Tjandraatmadja (Google Research), Srikumar Ramalingam (Google Research), Abhinav Kumar (Michigan State University) , and Xin Yu (The University of Utah); and published at ICML 2018 (https://arxiv.org/abs/1711.02114), AAAI 2020 (https://arxiv.org/abs/1810.03370), CPAIOR 2020 (https://arxiv.org/abs/2001.00218), and NeurIPS 2021 (https://arxiv.org/abs/2102.07804).
Seminar title: Norm minimization problems in data science: an integer programming perspective
Date: March 9th, 2022
Abstract: The talk addresses data-science problems involving the minimization of vector norms, which arise in, among others, sparse regression, certain clustering problems involving hyperplanes, and linear classification. Focusing on how those problems can be cast as (mixed integer) nonlinear optimization problems, the talk illustrates different mathematical-programming ways to handle vector norms, as well as geometrical reformulations leading to easier to solve problem whose optimal solutions are within a constant approximation factor of the optimal solution value of the original problem.
Seminar title: Frank-Wolfe methods for large-scale constrained optimization
Date: February 2nd, 2021
Abstract: Conditional gradient algorithms allow the integration of convex constraints in a first-order optimization method. We present a new Julia toolbox integrating several variants of the Conditional Gradient method and detail the design choices that enable large-scale and atypical applications. In particular, we will present the linear minimization oracle interface making the library extensible and allowing users to leverage closed-form solutions of linear minimization subproblems when they are known.
Seminar title: Early detection of incipient VOC’s penetration via funnel plots of regional reproduction numbers
Date: January 26th, 2021
Abstract: Tools to early detect the emergence of a new variant of concern are essential to develop strategies that contain epidemic outbreaks and their health-economic-social consequences. In this talk, we ‘funnel plots’ as a statistical process control method that can quickly identify regions of a country where the reproduction number is anomalous with respect to the national one, while keeping false alarms under control. The method is validated on public COVID-19 data demonstrating its efficacy in the early detection of SARS-CoV-2 variants in India, South Africa, England, and Italy.
Seminar title: Decision Trees under a modern optimization lens
Date: December 6th, 2021
Abstract: Decision tree is a commonly used supervised method in Machine Learning and Data Mining for regression and classification tasks. Decision tree classifier involves segmenting the predictor space into a number of simple regions, each one corresponding to a qualitative response, taking the form of a binary tree. State-of-the-art decision tree learning methods apply heuristics recursively to create each split in isolation, which may not capture well the underlying characteristics of the dataset. The Optimal Decision Tree problem attempts to resolve this by creating the entire decision tree at once to achieve global optimality. Through mixed-integer optimization and huge improvements in both hardware and software resources, we present a novel formulation of the optimal decision tree learning problem.
Seminar title: On the computation of the exact chi-square index by Integer Programming
Date: November 24th, 2021
Abstract: Consider a set of observations consisting of measures on two variables. A statistical test of independence of the two variables is the maximum Pearson’s Chi-square index, defined as a Quadratic Transportation Problem (QTP). The QTP is derived from the Linear Transportation Problem: they are both defined on the transportation polytope, but the QTP has an objective function quadratic and convex in the flow variables. Since the solution is one of the many extreme points of the transportation polytope, it is hard to certify the optimality. We introduce a combinatorial relaxation of QTP, and we propose a decomposition method to compute upper bounds, in which the QTP is reduced to 0-1 knapsack problems.