DS4DM Coffee Talks

Sonja Rohmer

Operations Research in the food system - Sustainable choices and the transportation of perishable products

Abstract: The use of operations research holds potential to improve and evaluate decision-making in the food system, proposing new decision pathways that can contribute to a sustainable transformation of the current system. The specific requirements of food and agricultural products, on the other hand, give rise to decision problems that pose new challenges from an OR perspective. This seminar aims to explore different decision aspects in the context of the food system, focusing in particular on sustainable choices and the role of quality considerations. Following from this, the seminar will elaborate on a specific OR problem linked to integrated logistics planning, by presenting the Production Routing Problem for perishable products.

When: 5th of June 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Sentao Miao

Dynamic Pricing with Fairness Constraints

Abstract: Following the increasing popularity of personalized pricing, there is a growing concern from customers and policy makers regarding fairness considerations. This paper studies the problem of dynamic pricing with unknown demand under two types of fairness constraints: price fairness and demand fairness. For price fairness, the retailer is required to (i) set similar prices for different customer groups (called group fairness) and (ii) ensure that the prices over time for each customer group is relatively stable (called time fairness). We propose an algorithm based on an infrequently-changed upper-confidence-bound (UCB) method, which is proved to yield a near-optimal regret performance. We then leverage this method to address the extension of non-stationary demand, which is particularly relevant for time fairness to prevent price gouging practices. For demand fairness, the retailer is required to satisfy that the resulting demand from different customer groups is relatively similar (e.g., the retailer offers a lower price to students to increase their demand to a similar level as non-students). In this case, we design an algorithm adapted from a primal-dual learning framework and prove that our algorithm also achieves a near-optimal regret performance.

When: 12th of June 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Past Talks

Adrian Vetta

Matching Markets: Incentives under the Deferred Acceptance Algorithm

I will give a short overview of several important applications of algorithmic mechanism design and game theory. Then I will focus on one specific problem: what incentives arise in matching markets when the classical deferred acceptance algorithm is used to obtain a stable matching? This talk is based on work with Ndiame Ndiaye and Sergey Norin.
When: 10th of November 2021 - 2.30pm (EST)
More: Adrian's Website
Recording: video reccording

Can Li

Algorithms and Software for Two-stage Stochastic Mixed-integer Nonlinear Programs

Two-stage stochastic programming is one of the approaches to model decision-making under uncertainty. Although there have been algorithmic advances in two-stage stochastic mixed-integer linear programs in the past two decades, the algorithms to address the nonlinear counterpart are few. In this talk, I will first give an overview of the recent advances in solving stochastic MINLP problems. The major focus of this talk is a generalized Benders decomposition-based branch and cut algorithm that combines strengthened Benders cuts and Lagrangean cuts for solving two stage stochastic MINLPs with mixed-binary first and second stage variables. The proposed algorithm is applied to a stochastic pooling problem, a crude selection problem, and a storage design problem. The performance of the proposed algorithm is compared with a Lagrangean decomposition-based branch and bound algorithm and solving the corresponding deterministic equivalent with the solvers including BARON, ANTIGONE, and SCIP.

When: 24th of November 2021 - 11am (EST)
More: Can's Website
Recording: video recording

Guanyi Wang

Solving row-sparse principal component analysis via convex integer programs

For general computational-intensive mixed-integer non-linear optimization problems, a major challenge is to verify/guarantee the quality of any feasible solution within tractable time/computational limits. A natural idea to tackle this challenge is constructing tight relaxations and designing approximation algorithms for relaxed problems. In this talk, we focus on the (row) sparse principal component analysis (rsPCA) problem, i.e., the problem of finding the top-r leading principal components of a covariance matrix such that all these principal components are linear combinations of a subset of k variables. We propose: (a) a convex integer programming relaxation of rsPCA that gives upper (dual) bounds for rsPCA, and; (b) a new local search algorithm for finding primal feasible solutions for rsPCA. We also show that, in the worst-case, the dual bounds provided by the convex IP are within an affine function of the globally optimal value. We demonstrate our techniques applied to large-scale covariance matrices. This is a joint work with Santanu S. Dey, Rahul Mazumder, Macro Molinaro.

When: 24th of November 2021 - 11am (EST)
More: Guanyi's Website
Recording: video recording

Didier Chételat

Continuous cutting planes algorithms

Standard cutting plane algorithms are iterative, in that cuts are added as rounds, and the resulting linear program grows at every round. Ineffective cuts are sometimes pruned, but the number of cuts must still fundamentally grow for the algorithm to converge. This is problematic for computational stability, as well as memory and time. In this talk, we present an alternative class of algorithms that finds good cuts by deformation: it starts with a fixed number of initial cuts, and continuously deforms them by gradient ascent to tighten the LP relaxation. The number of cuts never changes throughout the process, and interestingly, it frames the problem of computing good cuts as a continuous optimization problem. Computational experiments show that this can be made to work in practice, although the method is not currently time competitive against the more classical cutting plane algorithms.
When: 22nd of February 2022 - 11am (EST)
More: Didier's Website
Recording: video recording

Maxime Gasse

Causal Reinforcement Learning using Observational and Interventional Data

Learning efficiently a causal model of the environment is a key challenge of model-based RL. In this work we consider a POMDP scenario where the learning agent has the ability to collect online experiences through direct interactions with the environment (interventional data), but has also access to a large collection of offline experiences, obtained by observing another agent interacting with the environment (observational data). A key ingredient, that makes this situation non-trivial, is that we allow the observed agent to interact with the environment based on hidden information, which is not observed by the learning agent. We then ask the following questions: can the online and offline experiences be safely combined for learning a causal model ? And can we expect the offline experiences to improve the agent's performances ? To answer these, we import ideas from the well-established causal framework of do-calculus, and we express model-based reinforcement learning as a causal inference problem.
When: 22nd of February 2022 - 11am (EST)
More: Maxime's Website
Recording: video recording

Alexandre Florio

Large-Scale Dynamic Vehicle Routing Problems with Stochastic Requests

Dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to approximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knapsack with a capacity given by the remaining service time available along the vehicle's route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed methods in prescribing high-quality offline route plans and online scheduling decisions. This work is available as a preprint at arxiv:2202.12983 and implementations (and visualizations) are available here.
When: 7th of April 2022 - 11am (EST)
Recording: video recording

Kilian Fatras

Optimal Transport

Optimal transport distances have found many applications in machine learning for their capacity to compare non-parametric probability distributions. Yet their algorithmic complexity generally prevents their direct use on large scale datasets. Among the possible strategies to alleviate this issue, practitioners can rely on computing estimates of these distances over minibatches of data. While computationally appealing, we highlight in this talk some limits of this strategy, arguing it can lead to undesirable smoothing effects. As an alternative, we suggest that the same minibatch strategy coupled with unbalanced optimal transport can yield more robust behaviours. We discuss the associated theoretical properties, such as unbiased estimators, existence of gradients and concentration bounds. Our experimental study shows that in challenging problems associated to domain adaptation, the use of unbalanced optimal transport leads to significantly better results, competing with or surpassing recent baselines.
When: 7th of April 2022 - 11am (EST)
More: Kilian's Website
Recording: video recording

Alfredo Torrico

Preserving diversity when partitioning: A geometric approach

Diversity plays a crucial role in team formation, representation of minority groups and generally when allocating resources fairly. Given a community composed by individuals of different types, we study the problem of dividing this community such that the global diversity is preserved as much as possible in each subgroup. We consider the diversity metric introduced by Simpson in his influential work that, roughly speaking, corresponds to the inverse of the probability that two individuals are from the same type when taken at random, with replacement. We provide a novel perspective by reinterpreting this quantity in geometric terms. We characterize the instances in which the optimal partition exactly preserves the global diversity in each subgroup. When this is not possible, we provide an efficient polynomial-time algorithm that outputs an optimal partition for the problem with two types. Finally, we discuss further challenges and open questions for the problem that considers more than two types.

When: 13th of May 2022 - 11am (EST)
More: Alfredo's Website
Recording: video recording

Dounia Lakhmiri

A Stochastic Proximal Method for Non-smooth Regularized Finite Sum Optimization

We consider the problem of training a deep neural network with non-smooth regularization to retrieve a sparse and efficient sub-structure. Our regularizer is only assumed to be lower semi-continuous and prox-bounded. We combine an adaptive quadratic regularization approach with proximal stochastic gradient principles to derive a new solver, called SR2. Our experiments on network instances trained on CIFAR-10 and CIFAR-100 with L1 and L0 regularization show that SR2 achieves higher sparsity than other proximal methods such as ProxGEN and ProxSGD with satisfactory accuracy.

When: 20th of May 2022 - 11am (EST)

Alexandre Forel

Robust counterfactual explanations for random forests

Counterfactual explanations describe how to modify a feature vector to flip the outcome of a trained classifier. Several methods have been proposed to generate counterfactual explanations, but their robustness when the classifier is re-trained has not been studied so far. Our goal is to obtain counterfactual explanations for random forests that are robust to algorithmic uncertainty. We study the link between the robustness of ensemble models and base learners and formulate a chance-constrained optimization model. We provide statistical guarantees for random forests of stumps and develop a practical method with good performance. We show that existing naive and plausibility-based methods provide surprisingly low robustness. Our method achieves the best trade-off between robustness and the distance of counterfactual explanations to the initial observation.

When: 20th of May 2022 - 11am (EST)

Gauthier Gidel

Extragradient Methods: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities

The Extragradient [Korpelevich, 1976] and the Past Extragradient [Popov, 1980] methods are among the most popular methods for solving saddle point and variational inequalities problems (VIP). Recently, they have known a surge of interest with the emergence of variational inequality formulation for machine learning such as Generative Adversarial Networks. Despite their long history and significant attention in the optimization community, there remain important open problems about their convergence in the monotone setting. In this talk, we present how we resolved some of these open questions and derived the first last-iterate O(1/K) convergence rates for monotone and Lipschitz VIP without any additional assumptions on the operator. The central part of our analysis is based on Performance Estimation Problems and computer-aided proofs. In the presentation, I will pay special attention to this approach and explain the main non-trivial issues we faced to get the final proofs via numerical computations.
When: 2nd of June 2022 - 11am (EST)

Recording: video recording

Emma Frejinger

Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning

We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time, for example, in transport planning related to fleet management, routing and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9\% of the time it takes the state-of-the-art exact method, and in the case of SMKP the same figure is 20%. Average optimality gaps are in most cases less than 0.1%.
When: 9th of June 2022 - 11am (EST)

Julien Ferry

Operational Research for Fairness, Privacy and Interpretability in Machine Learning: Leveraging ILP to Learn Optimal Fair Rule Lists

Fairness, interpretability, and privacy are important fields for the development of responsible AI. While these three topics are often considered separately, their simultaneous application also seems desirable. The objective of my PhD is to study their interactions leveraging tools from operations research and combinatorial optimization. In a first part of my talk, I will provide an overview of my different past and current works on the frontiers of these different topics. In a second part, I will present my work on the use of Integer Linear Programming to learn interpretable, fair and optimal models.
When: 7th of July 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th Floor in the CERC conference Room (5496)
More: Julien's Website
Recording: video recording

Natasja Sluijk

Dynamic Fleet Size and Order Assignment Problem

The dynamic fleet size and order assignment problem (DFSOAP) is a canonical version of a real-world problem faced by a logistic service provider. Each day, the company has to decide on the assignment of newly arrived orders to delivery days, as well as the number of additional vehicles to rent for each day in the planning horizon. When making these decisions, one has to trade-off the increasing rental costs and decreasing demand uncertainty. We formalize the problem and formulate a sequential stochastic optimization model for DFSOAP. We propose four algorithms (policies) that, given a state, return a decision for DFSOAP. Preliminary computation results on a set of instances show the benefit of assigning multiple orders simultaneously, rather than one at a time.
When: 21th of July 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th floor, Cirrelt Conference Room(5441)

Recording: video recording

Sitao Luan

On Addressing the Limitations of Graph Convolutional Networks

Many real-world tasks can be modeled as graphs. Recently, graph convolutional neural network (GCN) based approaches have achieved significant progress for solving large, complex, graph-structured problems. Although with high expressive power, GCNs still suffer from several difficulties, e.g. the over-smoothing problem limits deep GCNs to sufficiently exploit multi-scale information, heterophily problem makes the graph-aware models underperform the graph-agnostic models. In this presentation, I will summarize those challenges, propose some methods to address them and put forward several research problems we are currently investigating.
When: 21th of July 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th floor, Cirrelt Conference Room(5441)

Recording: video recording

Zhaocheng Zhu

Knowledge Graph Reasoning with Graph Neural Networks

Knowledge graphs encode real-world facts and are critical in various applications and domains such as natural language understanding, recommender systems, drug discovery. A fundamental problem on knowledge graphs is to predict the answer to some queries by reasoning over existing facts, a.k.a. knowledge graph reasoning. Such a problem is commonly solved by embedding methods. In this talk, we take another approach, and solves knowledge graph reasoning with graph neural networks. First, we propose Neural Bellman-Ford Networks (NBFNet) that solves single-hop reasoning with the generalized Bellman-Ford algorithm and learned operators in the path formulation. Then we introduce Graph Neural Network Query Executor (GNN-QE) that combines GNNs with fuzzy sets for answering multi-hop queries on knowledge graphs. Both models are highly related to traditional symbolic methods, such as personalized PageRank and subgraph matching, but can additionally deal with the missing links in knowledge graphs. Meanwhile, both models can visualize their intermediate steps, which may help us better understand the reasoning process.
When: 4th of August 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th floor, Cirrelt Conference Room(5441)
More: Zhaocheng's Website
Recording: video recording

Rosemarie Santa González

A Stochastic Prize Collection Methodology for Mobile Clinic Deployment Planning

Practitioners strive to deploy clinics that can access populations with the highest needs. However, when planning humanitarian operations, there is uncertainty that arises in the travel time, usability of roads, and access to population points. This study models mobile clinic deployment as a two-stage Stochastic Prize Collection Problem that maximizes the benefit offered and minimizes the costs, while considering several sources of uncertainty. The impact of four recourse policies (simple recourse, select-then-route, re-route per time period, and full network recourse) on the mobile clinic deployment plans are also studied. The recourse policies’ performance is evaluated on three different severity levels: moderate, medium, and severe. Results and managerial insights are presented for the real-world instance of Kenya.
When: 4th of August 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th floor, Cirrelt Conference Room(5441)

Recording: video recording

Claudia Bongiovanni

Guiding metaheuristics trough machine learning predictions: a case study in dynamic autonomous ridesharing

Many dynamic optimization problems in urban mobility and supply chain are modeled as a sequence of independent static subproblems that must be rapidly re-optimized as new information arrives. These subproblems typically repeat over time and share many common characteristics that directly impact the efficiency of the optimization strategy. This means that subproblems solved in the past can become useful in guiding the optimization process of future subproblems. This talk presents a machine learning-based meta-heuristic approach that efficiently reoptimizes autonomous ridesharing plans as new online demand arrives. The optimization approach consists of a local search-based metaheuristic that iteratively revisits previously made vehicle-trip assignments through exchanges within and between vehicles. These exchanges are performed by selecting from a pool of destroy-repair operators using a machine learning approach that is trained offline on a large dataset consisting of more than one and a half million examples of previously solved autonomous ridesharing subproblems. Computational experiments are performed on dynamic instances extracted from real ridesharing data published by Uber Technologies Inc. The results show that the proposed machine learning-based optimization approach outperforms benchmark data-driven metaheuristics by about nine percent, on average. Managerial insights highlight the correlation between the selected vehicle routing features and the performance of metaheuristics in the context of autonomous ridesharing operations. This work is in collaboration with Dr. Mor Kaspi (Tel-Aviv University), Prof. Nikolas Geroliminis (EPFL) and Prof. Jean-François Cordeau (HEC Montréal). The full paper is accessible at here
When: 24th of October 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Recording: video recording

Tu-San Pham

Machine learning-based algorithms for dynamic patient scheduling problems with uncertainty: a case study in radiotherapy scheduling

In dynamic patient scheduling problems, scheduling decisions are taken periodically (daily, weekly… ) and are evaluated on a rolling horizon. As patient arrivals are stochastic, it is important to take into account uncertainty. Machine learning can provide useful tools for extracting knowledge from the historical distribution of patient arrivals to assist scheduling decisions. In this talk, we will present a case study where a machine learning-based algorithm successfully solves a dynamic scheduling problem in the healthcare domain. Scheduling radiation therapy treatment for cancer patients is a complicated task as the treatment requires multi-appointments and subjects to many technical constraints. The problem is even more challenging as the mix of patients with different priorities and deadlines require a smart allocation of treatment resources. We propose a prediction-based approach, where a regression model learns from offline solutions to smartly delay treatments of non-urgent patients to make space for emergency cases. We also demonstrate how our proposed approach supports explainability and interpretability in scheduling decisions using SHAP values.
When: 24th of October 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Recording: video recording

Pierre-Luc Bacon

Decision Awareness in Reinforcement Learning

Abstract: Decision awareness is the learning principle according to which the components of a learning system ought to be optimized directly to satisfy the global performance criterion: to produce optimal decisions. This end-to-end perspective has recently led to significant advances in model-based reinforcement learning by addressing the problem of compounding errors plaguing alternative approaches. In this talk, I will present some of our recent work on this topic: 1. on learning control-oriented transition models by implicit differentiation and 2. on learning neural ordinary differential equations end-to-end for nonlinear trajectory optimization. Along the way, we will also discuss some of the computational challenges associated with those methods and our attempts at scaling up performance, specifically: using an efficient factorization of the Jacobians in the forward mode of automatic differentiation through novel constrained optimizers inspired by adversarial learning.
When: 7th of November 2022 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)
Recording: video recording

Margarida Carvalho

Responsible algorithm development: An example in health-care

Abstract: Conversations over a cup of coffee can go beyond one's expertise. Often, they provide a comfortable environment to discuss problems and question ideas. Thus, in this coffee talks seminar, I will take their naming literally and provide different ideas encouraging the discussion about the need to develop responsible decision support tools. Otherwise, those tools may create inequalities and hurt social welfare. To achieve my goal, I will describe a series of examples where the human connection of decisions will be emphasized. These examples will range from sustainability to education. Then, I will focus on a particular example in the health field, related to kidney exchange programs, and show how decomposition methods can be used to efficiently implement fairness based on theories of justice.
When: 6th of February 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Quentin Cappart

Learning to bound using decision diagrams and reinforcement learning

Finding tight bounds on the optimal solution is a critical element of practical solution methods for discrete optimization problems. In the last decade, decision diagrams have brought a new perspective on obtaining upper and lower bounds that can be significantly better than classical bounding mechanisms, such as linear relaxations. However, the quality of the bounds achieved through this flexible bounding method is highly reliant on the ordering of variables chosen for building the diagram, and finding an ordering that optimizes standard metrics is an NP-hard problem, which is also difficult to model. In this talk, I will present a generic approach based on deep reinforcement learning for obtaining an ordering for tightening the bounds obtained with approximate decision diagrams, and show that these bounds can be efficiently used to speed-up abranch-and-bound algorithm.
When: 13th of February 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Utsav Sadana

The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems

Conditional value at risk (CVaR) is widely used to account for the preferences of a risk-averse agent in extreme loss scenarios. To study the effectiveness of randomization in interdiction problems with an interdictor that is both risk- and ambiguity-averse, we introduce a distributionally robust maximum flow network interdiction problem in which the interdictor randomizes over the feasible interdiction plans in order to minimize the worst case CVaR of the maximum flow with respect to both the unknown distribution of the capacity of the arcs and the interdictor’s own randomized strategy. Using the size of the uncertainty set, we control the degree of conservatism in the model and reformulate the interdictor’s distributionally robust optimization problem as a bilinear optimization problem. For solving this problem to any given optimality level, we devise a spatial branch-and-bound algorithm that uses the McCormick inequalities and reduced reformulation linearization technique to obtain a convex relaxation of the problem. We also develop a column-generation algorithm to identify the optimal support of the convex relaxation, which is then used in the coordinate descent algorithm to determine the upper bounds. The efficiency and convergence of the spatial branch-and-bound algorithm is established in numerical experiments. Further, our numerical experiments show that randomized strategies can have significantly better performance than optimal deterministic ones. (joint work with Erick Delage).
When: Postponed to 6th of March 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Dan Assouline

MAgNet: Mesh Agnostic Neural PDE Solver

The computational complexity of classical numerical methods for solving Partial Differential Equations (PDE) scales significantly as the resolution increases. As an important example, climate predictions require fine spatio-temporal resolutions to resolve all turbulent scales in the fluid simulations. This makes the task of accurately resolving these scales computationally out of reach even with modern supercomputers. As a result, current numerical modelers solve PDEs on grids that are too coarse (3km to 200km on each side), which hinders the accuracy and usefulness of the predictions. In this paper, we leverage the recent advances in Implicit Neural Representations (INR) to design a novel architecture that predicts the spatially continuous solution of a PDE given a spatial position query. By augmenting coordinate-based architectures with Graph Neural Networks (GNN), we enable zero-shot generalization to new non-uniform meshes and long-term predictions up to 250 frames ahead that are physically consistent. Our Mesh Agnostic Neural PDE Solver (MAgNet) is able to make accurate predictions across a variety of PDE simulation datasets and compares favorably with existing baselines. Moreover, MAgNet generalizes well to different meshes and resolutions up to four times those trained on.
When: Postponed to 6th of March 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Massimiliano Amarante

Ideas and problems in decision making under uncertainty & Foundations of Neo-Bayesian Statistics(s)

Part I [crash course di Decision Theory]: Ideas and problems in decision making under uncertainty As these concepts will be freely used in the second portion of the talk, this part quickly reviews some of the main ideas in the theory of decision making under uncertainty such as Expected Utility (EU), Maxmin EU, Choquet EU, the Invariant bi-separable model and the Variational model. We will discuss the relation of these ideas with problems like one-shot learning or learning with corrupted data as well as applications to Robust Statistics, fuzzy systems, climate change and finance. As a bridge to the second part, we will talk about the difficulties encountered in extending non-Bayesian models to a dynamic setting.

Part II: Foundations of Neo-Bayesian Statistics(s): We will take off from the observation that Savage’s axioms (or any axiomatization of EU) map Statistics into (classical) probability theory. Consequently, the axioms of any non-Bayesian model must map Statistics into something else. This observation raises the question of which Statistical theories would emerge via this mapping. We show that many non-Bayesian models map Statistics into alternative theories of probability that display the same structure as classical probability and differ from the latter only in the notion of approximation they use. We then build a general framework encompassing all the models displaying this structure and use it to identify the rules of inference corresponding to several popular models. We conclude by discussing the implications of our findings for issues such dynamic consistency, updating of capacities as well as some open problems.
When: 20th of March 2023 - 10am-11am(Part1), 11:15am-12:15pm(Part2) (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 5th floor, Room 5441

Quentin Bertrand

On the Limitations of Elo: Real-World Games, are Transitive, not Additive

Abstract: Real-world competitive games, such as chess, go, or StarCraft II, rely on Elo models to measure the strength of their players. Since these games are not fully transitive, using Elo implicitly assumes they have a strong transitive component that can correctly be identified and extracted. In this study, we investigate the challenge of identifying the strength of the transitive component in games. First, we show that Elo models can fail to extract this transitive component, even in elementary transitive games. Then, based on this observation, we propose an extension of the Elo score: we end up with a disc ranking system that assigns each player two scores, which we refer to as skill and consistency. Finally, we propose an empirical validation on payoff matrices coming from real-world games played by bots and humans.

When: 3rd of April 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488) Paper: link

Ismail Sevim

A data-driven matching algorithm for ride pooling problem

Abstract: This paper proposes a data-driven matching algorithm for the problem of ride pooling, which is a transportation mode enabling people to share a vehicle for a trip. The problem is considered as a variant of matching problem, since it aims to find a matching between drivers and riders. Proposed algorithm is a machine learning algorithm based on rank aggregation idea, where every feature in a multi-feature dataset provides a ranking of candidate drivers and weight for each feature is learned from past data through an optimization model. Once weight learning and candidate ranking problems are considered simultaneously, resulting optimization model becomes a nonlinear bilevel optimization model, which is reformulated as a single level mixed-integer nonlinear optimization model. To demonstrate the performance of the proposed algorithm, a real-life dataset from a mobile application of a ride pooling start-up company is used and company’s current approach is considered as benchmark.

When: 3rd of April 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Marilène Cherkesly

Routing for healthcare in underserved areas

Abstract: In this presentation, we introduce, model and solve two routing problems to improve healthcare accessibility in underserved areas. This research project is aligned with Goal 3 of the UN Sustainable Development Goals which “ensur[es] healthy lives and promot[es] well-being at all ages”. In underserved areas, e.g., remote areas, conflict and post-conflict zones and refugee camps, the network is often sparse which complexifies the logistical activities. First, we design a community healthcare network for remote regions. In this network, community healthcare workers and their supervisors are located to cover the population seeking healthcare, and supervisors are routed to conduct training with community healthcare workers. Second, we propose a mobile clinic network for conflict zones. In that context, total healthcare benefits which is composed of coverage and continuity benefits are maximized. Third, we propose different mathematical models to tackle the “routing” aspect of the two problems. These models differ according to their sets of variables and of constraints, and we discuss their theoretical strengths and weaknesses. Finally, we conduct computational experiments on real-life instances as well as thorough sensitivity analyses to derive appropriate managerial insights.

When: 11th of April 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Szilvia Papai

Maximum Matching with Consecutive Acceptance Intervals

Abstract: We consider a one-to-one matching market where each agent is to be matched to an object from the set of acceptable objects for this agent, and the acceptable set is consecutive with respect to a fixed “objective” ranking of the objects. The profile of consecutive acceptance intervals is assumed to be commonly known. Each agent has a strict individual preference ranking over the objects in her acceptance interval, which is independent of the common ranking of the objects and assumed to be private information. We first study maximum matchings, which depend on the consecutive interval profile only, and propose a simple algorithm for finding a maximum matching at an arbitrary interval profile. We also characterize maximum matchings for arbitrary acceptance intervals. We then investigate serial dictatorships and show first that for some interval profiles there is no serial dictatorship which always yields a maximum matching. We characterize all the interval profiles for which such a maximum serial dictatorship exists and find all the maximum serial dictatorships in terms of agent permutations that produce a maximum matching. These rules are Pareto-optimal and group-strategyproof.

When: 24th of April 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Antoine Legrain

Operational challenges in integrated mobility systems

Abstract: In an integrated mobility system, users demand diversified and ideally synchronized services to benefit from a quality experience with fast and efficient connections. Services must be coordinated to be productive and to be able to offer reasonable rates. Finally, such a system must be sustainable and thus have a significant impact on GHG emissions, congestion, and parking space, as well as it should ensure equitable access to various users. A synchronization platform would a priori be a solution that will increase the offer of integrated mobility services and improve its access and adoption, thus reducing solo car travel and GHG emissions. Integrated mobility is part of the service mobility movement ("MaaS") but is not exclusive to it. Collaboration of operators at transfer points and services synchronization are the key issues to improve the user experience. However, collaborations are often competitive, making it problematic to share data and revenue between operators and adopt them by users. Furthermore, intelligent mobility management requires the collection and use of a large amount of data, which naturally raises important privacy and ethical issues. These new models are also becoming indispensable in a post-COVID environment that calls into question the expected revenues of mobility infrastructure. In this talk, we will present several key issues in those systems, and propose to reverse the usual process of creating solutions to study in the first place the governance issues of the proposed systems and the legal and ethical aspects of their implementation, as well as the protection of privacy by design ("privacy-by-design"), in order to prevent certain abuses, but also to ensure the social acceptability of the model chosen and ultimately its adoption. Finally, several optimization problems will illustrate the challenges raised by those issues if one wants to study and integrate the proposed solutions.

When: 8th of May 2023 - 11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)