Workshop on Data Science for Real-Time Decision Making

Abstract: In this talk we provide an overview of a few works having a common general theme. Namely, we embed predictions from supervised learning to speed up the computation of high-quality solutions to discrete optimization problems subject to uncertainty. We focus the talk on key takeaways and future research perspectives.

The talk is based on joint work with (in alphabetic order) Yoshua Bengio, Justin Dumouchelle, Bernard Gendron, Sébastien Lachapelle, Eric Larsen, Simon Lacoste Julien and Andrea Lodi.

Abstract: One of the attributes of public transport service that is most important to riders is the variability of travel times. Thus, many bus operators are trying to increase the regularity of their service, also referred to as reliability. Our work explores methods to potentially improve service reliability in the operational planning stage using a data-driven approach. First, travel time distributions are predicted using historical Automatic Vehicle Location (AVL) data. These predictions are then integrated in the reliable multi-depot vehicle scheduling problem with stochastic travel time (R-MDVSP-STT) which aims to build vehicle schedules that are both cost- and delay-efficient. Experimental results with real data collected by buses running in Montréal (Canada) indicate that the R-MDVSP-STT provides more reliable vehicle schedules for a negligible increase in operational costs compared to the multi-depot vehicle scheduling problem.

Abstract: Patient scheduling is a difficult task involving stochastic factors such as the unknown arrival times of patients. Similarly, the scheduling of radiotherapy for cancer treatments needs to handle patients with different urgency levels when allocating resources. High priority patients may arrive at any time, and there must be resources available to accommodate them. A common solution is to reserve a flat percentage of treatment capacity for emergency patients. However, this solution can result in overdue treatments for urgent patients, a failure to fully exploit treatment capacity, and delayed treatments for low-priority patients. This problem is especially severe in large and crowded hospitals. In this paper, we propose a prediction-based approach for online dynamic radiotherapy scheduling that dynamically adapts the present scheduling decision based on each incoming patient and the current allocation of resources. Our approach is based on a regression model trained to recognize the links between patients’ arrival patterns, and their ideal waiting time in optimal offline solutions where all future arrivals are known in advance. When our prediction-based approach is compared to flat- reservation policies, it does a better job of preventing overdue treatments for emergency patients, while also maintaining comparable waiting times for the other patients. We also demonstrate how our proposed approach supports explainability and interpretability in scheduling decisions using SHAP values.

Abstract: Branch and cut is the dominant paradigm for solving a wide range of mathematical programming problems — linear or nonlinear — combining intelligent search (via branch and bound) and relaxation-tightening procedures (via cutting planes, or cuts). While there is a wealth of computational experience behind existing cutting strategies, there is simultaneously a relative lack of theoretical explanations for these choices, and for the tradeoffs involved therein. Recent papers have explored abstract models for branching and for comparing cuts with branch and bound. However, to model practice, it is crucial to understand the impact of jointly considering branching and cutting decisions. In this paper, we provide a framework for analyzing how cuts affect the size of branch-and-cut trees, as well as their impact on solution time. Our abstract model captures some of the key characteristics of real-world phenomena in branch-and-cut experiments, regarding whether to generate cuts only at the root or throughout the tree, how many rounds of cuts to add before starting to branch, and why cuts seem to exhibit nonmonotonic effects on the solution process.

Abstract: Given its wide spectrum of applications, the classical problem of all-terminal network reliability evaluation remains a highly relevant problem in network design, and its associated optimization problem—to find a network with the best possible reliability—presents an even more complex challenge. In this work, we propose a novel reliability optimization framework for network design in series-parallel graphs. We formulate the reliability optimization problem as a mixed-integer nonlinear optimization problem and solve it using classical convex envelopes of bilinear functions and a new family of convex envelopes we developed for special expressions that appear in the evaluation of network reliability. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem.

Abstract: With the growing penetration of renewable generation and distributed energy resources, modern power grids face increasing operational uncertainty which, in turn, calls for systematic risk assessment and management. In that context, ML-based optimization proxies enable real-time risk assessment, without the computational cost of solving numerous economic dispatch problems. Motivated by a principled analysis of the market-clearing optimizations of US system operators, the proposed just-in-time learning pipeline addresses the main challenges of learning economic dispatch solutions, i.e., the variability in load, renewable output and production costs, as well as the combinatorial structure of commitment decisions. This enables the fast training of expert models, together with a novel classification-then-regression architecture that further leverages the behavior of economic dispatch solutions. Numerical experiments will be presented on the French transmission system.

Abstract: How to choose a solution when an optimization problem has multiple ones? How to derive insights from the optimal solutions in this case?

These questions form the basis of this work, which considers kidney exchange programs, and thus the allocation of valuable resources to patients. When multiple optimal solutions exist, fairness should be fostered and the choice of a solution should not be left to the discretion of the solver but should be controlled by its developer. In this work, we devise procedural fair methods, determining probability distributions over kidney exchanges that optimize different fairness criteria. These are based on Aristotle’s equity principle, Nash standard of comparison, Rawlsian justice and individual fairness.

This is joint work with William St-Arnaud and Golnoosh Farnadi.

Abstract: Stochastic gradient descent (SGD) is a common optimization method used to train deep networks. Sparse estimation (0-bit) of parameters, or binary estimation (1-bit) requires modification of the SGD towards proximal SGD. BinaryConnect (BC) and its many variations have become the de facto standard for 1-bit quantization of neural networks. However, our understanding of the inner workings of BC is still quite limited. First, we show that existing quantization algorithms, including post-training quantization, are surprisingly similar to each other. We argue for proximal maps as a natural family of quantizers that is both easy to design and analyze. We refine the observation that BC is a special case of dual averaging, which itself is a special case of the generalized conditional gradient algorithm. We propose ProxConnect as a generalization of BC and benefit from this relationship to understand their convergence. Eventually, we demonstrate some product examples of quantized networks running on Huawei P20 cellphones and briefly how one can go from research to an AI product run on a limited edge device.

Abstract: In parallel to the activities of the chair, we witnessed a huge and fast evolution of startups, corporate research labs and research centers, all competing for talent. In this presentation, I’ll give the perspective of a person who has hired and managed data scientists throughout this period and highlight the importance of funding research, developing students and fostering industrial collaborations, not only to grow the talent pool, but to make it rich.

Abstract: This presentation is about my findings on how to connect academic research to enterprises and build value. From operationalization of sustainable development to AI, the common thread is about building the right bridges. From the academic side to the industrial side, there is always friction when you want to connect researchers to product development. There’s not always an obvious link between lab research and practical applications but research is part of the innovation journey. Finding the right path for an idea to become an innovation, is a delicate dance between pushing discoveries and pulling for solutions. But it is more than that and I want to share some insights from my 10 year’s experience on the subject.

Abstract: Graphs are structured discrete objects which have in recent years attracted the attention of the machine learning community. The early efforts on graph neural networks made it possible to learn functions on graphs, or on the nodes and edges of a given graph. This talk will present methods, called generative flow networks (or GFlowNets), that can also output graphs, i.e., sample from a (possibly conditional) distribution over graphs. The idea is to learn a sequential policy that generates a graph one element at a time, conditioned on the already generated elements, while handling the fact that the same graph can be generated in many different ways. GFlowNets have been applied to search in the space of new molecules as well as to model causal graphs, i.e., learning to efficiently approximate a multimodal Bayesian posterior over graphs. Unlike traditional reinforcement learning and optimization methods, rather than searching for a single maximum, GFlowNets learn to sample objects with a probability proportional to a given reward function (somewhat like MCMC methods), i.e., identify the larger modes of a distribution, and this is useful in many contexts where what we actually optimize is a proxy for the non-computable function we wish to really maximize, e.g., in the drug discovery context.

Abstract: Stochastic programming is a powerful modeling framework for decision-making under uncertainty.
In this work, we tackle two-stage stochastic programs (2SPs), the most widely applied and studied stochastic programming models. Solving 2SP can take prohibitively long time, especially when the second-stage problem is a mixed-integer linear program (MIP) or a nonlinear program (NLP), even if specialized algorithms that exploit problem structure are employed. Finding high-quality (first-stage) solutions quickly can be crucial in such settings. For this aim, we develop Neur2SP, a new method that approximates the expected (second-stage) value function via a neural network to obtain a surrogate model, which can be solved more efficiently than the original 2SP. The proposed approach makes no assumptions about the problem structure, in particular about the second-stage problem, and can be implemented using an off-the-shelf solver and open-source libraries.
Our extensive computational experiments on the benchmark instances of a variety of problem classes, 2SPs with different structures, show the efficiency and efficacy of Neur2SP.

Joint work with Justin Dumouchelle, Rahul Patel, and Merve Bodur at the University of Toronto.

https://arxiv.org/abs/2205.12006

Abstract: We present a novel way to find good cuts for mixed-integer linear programs. Instead of relying on an algorithm that produces good cuts by construction, we search within a family of inequalities, valid by construction, for the ones that lead to the highest dual bound possible. We treat this search as a continuous optimization problem, and show on several datasets that it leads to better cuts than those that would be produced by classical algorithms. Moreover, we show that this optimization can be reinterpreted as optimizing a neural network to solve the subadditive dual problem to a MILP, linking this work with machine learning.

Abstract: Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection—but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments with a B&C solver for neural network verification further validate our approach, and exhibit the potential of learning methods in this setting.

Joint work with Max B. Paulus, Andreas Krause, Laurent Charlin, and Chris J. Maddison.