DS4DM Coffee Talks

Andrea Lodi

Mixed-Integer Programming: 65 years of history and the Artificial Intelligence challenge

Abstract: Mixed-Integer Programming (MIP) technology is used daily to solve (discrete) optimization problems in contexts as diverse as energy, transportation, logistics, telecommunications, biology, just to mention a few. The MIP roots date back to 1958 with the seminal work by Ralph Gomory on cutting plane generation. In this talk, we will discuss — taking the (biased) viewpoint of the speaker — how MIP evolved in its main algorithmic ingredients, namely preprocessing, branching, cutting planes and primal heuristics, to become a mature research field whose advances rapidly translate into professional, widely available software tools. We will then discuss the next phase of this process, where Artificial Intelligence and, specifically, Machine Learning are already playing a significant role, a role that is likely to increase.

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

Walter Rei

Decision-Based Scenario Clustering - General Bounds for Stochastic Optimization Models

Abstract: In order to make sense of future uncertainty, managers have long resorted to creating scenarios that are then used to evaluate how uncertainty affects decision-making. The large number of scenarios that are required to faithfully represent several sources of uncertainty leads to major computational challenges in using these scenarios in a decision-support context. Moreover, the complexity induced by the large number of scenarios can stop decision makers from reasoning about the interplay between the uncertainty modelled by the data and the decision-making processes (i.e., how uncertainty affects the decisions to be made). To meet this challenge, we propose a new clustering approach to group scenarios based on the decisions associated to them. In this talk, I will present the developed scenario clustering approach and show how it can be used to derive efficient bounds for stochastic optimization models.

When: 27 May 2024, 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)

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 - 10am-11am (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Andreea Deac

Title: Deploying Neural Algorithmic Reasoning

Abstract: Neural networks that are able to reliably execute algorithmic computation may hold transformative potential to both machine learning and theoretical computer science. On one hand, they could enable the kind of extrapolative generalisation scarcely seen with deep learning models. On another, they may allow for running classical algorithms on inputs previously considered inaccessible to them. Both of these promises are shepherded by the neural algorithmic reasoning blueprint. In this talk, I aim to provide an introduction to how to develop neural networks that execute algorithmic computation, followed by examples on how to deploy such neural networks in real-world problems, such as learning to do implicit planning.

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

Alexis Montoison

Title: JuliaHSL: the ultimate collection for large-scale scientific computation

Abstract: HSL is a collection of state-of-the-art Fortran packages for large-scale scientific computation. The new package JuliaHSL, jointly developed with the Computational Mathematics Group at the STFC Rutherford Appleton Laboratory, aims to facilitate the use of all HSL packages in Julia. We describe its applications and features through the Julia packages HSL.jl and Ipopt.jl.

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

Michel Bierlaire

Solving a pricing problem under irrational behavior

Mathematical modeling of choice behavior is rooted in microeconomic theory, and relies on the assumption that economic actors behave rationally. However, there is empirical evidence that the rationality assumption does not always hold. In this talk, we will present some of this evidence and describe how to develop behavioral models that can account for this apparent irrationality. We will then consider a formulation of a price problem where the customers’ choice is represented by that behavioral model.

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

Abdel Ghani Labassi

Title: Learn to Compare Nodes in Branch and Bound

Abstract: The Branch and Bound method aims to find optimal solutions to NP-hard problems. It divides the search space into subproblems, which are recursively solved, while eliminating branches whose potential solution is inferior to the one already found. The choice of the exploration order of nodes is essential to the performance of this algorithm. An efficient selection strategy can speed up the solution and reduce the branching tree. We will discuss various node selection approaches, with an emphasis on data-based methods. We will also present our contribution, which uses graph neural networks to compare nodes, which are represented as bipartite graphs. Our model, capable of handling variable dimension data, has shown faster resolution and reduction of the branching tree than competitors, across three NP-hard benchmarks, while offering natural generalization to larger instances.

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

Francois Lamothe

Title: A study of the set-covering polyhedron through tilting vectors

Abstract : Given a ground-set of elements and a family of subsets, the set covering problem consists in choosing a minimum number of elements such that each subset contains at least one of the chosen elements. In this work, we study the set-covering polyhedron which is the convex hull of integer solutions of the set-covering problem. In particular, we link the study of the facets of the set-covering polyhedron to the theory of inequality tilting. This theory, introduced by Chvatal et al. (2013), studies how inequalities can be rotated around their contact points with a polyhedron in order to obtain new inequalities that induce faces of higher dimension. To that end, we introduce the \textit{tilting vectors} which characterize the degrees of freedom of the possible rotations of a valid inequality. We will present the following contributions. We study how tilting vectors characterize facet-defining inequalities. We show that tilting vectors can be used to tilt inequalities similarly to the procedure proposed by Chvatal et al. (2013). We present how the number of computations required to tilt an inequality can be reduced when the inequality has a lot of zero coefficients. Finally, we use the tilting vectors to extend several necessary and/or sufficient conditions for facets of the set-covering polyhedron presented by Cornuéjols and Sassano (1989), Sassano (1989) and Balas and Ng (1989).

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

Petar Veličković

The Melting Pot of Neural Algorithmic Reasoning

Abstract: With the eyes of the AI world pointed at the alignment of large language models, another revolution has been more silently---yet intensely---taking place: the algorithmic alignment of neural networks. After briefly surveying how we got here, I'll present some of the interesting 2023 works I've had the pleasure to co-author in this space.

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

Claudio Contardo

Title: On the solution of pseudo-polynomial dynamic programs involving large magnitudes

Abstract: In this presentation, we will introduce an iterative algorithm for the exact solution of dynamic programs of pseudo-polynomial complexity, especially useful when large magnitudes are involved. Our method iterates between the solution of a dynamic program on a loser dimensional space providing a dual approximation, and of a refinement procedure used to achieve primal feasibility. We illustrate our method on three problems relevant in practice: the ranged subset-sum problem, the tree partitioning problem, and the shortest path problem with waiting costs. We show that the proposed method is capable of providing significant speedups over classical implementations of dynamic programming.

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

Marc Lanctot

Title: Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning

Abstract: In this talk, I will cover a recent AAMAS paper that was joint work with Zun Li from University of Michigan from and several others. Multiagent reinforcement learning (MARL) has benefited significantly from population-based and game-theoretic training regimes. One approach, Policy-Space Response Oracles (PSRO), employs standard reinforcement learning to compute response policies via approximate best responses and combines them via meta-strategy selection. We augment PSRO by adding a novel search procedure with generative sampling of world states, and introduce two new meta-strategy solvers based on the Nash bargaining solution. We evaluate PSRO's ability to compute approximate Nash equilibrium, and its performance in two negotiation games: Colored Trails, and Deal or No Deal. We conduct behavioral studies where human participants negotiate with our agents (N=346). We find that search with generative modeling finds stronger policies during both training time and test time, enables online Bayesian co-player prediction, and can produce agents that achieve comparable social welfare negotiating with humans as humans trading among themselves.

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

Marlos C. Machado

Title: Representation-driven Option Discovery in Reinforcement Learning

Abstract: The ability to reason at multiple levels of temporal abstraction is a fundamental aspect of intelligence. In reinforcement learning, this attribute is often modeled through temporally extended courses of actions called options. Despite the popularity of options as a research topic, they are seldom included as an explicit component in traditional solutions within the field. In this talk, I will try to provide an answer for why this is the case and emphasize the vital role options can play in continual learning. Rather than assuming a predetermined set of options, I will introduce a general framework for option discovery, which utilizes the agent's representation to discover useful options. By leveraging these options to generate a rich stream of experience, the agent can improve its representations and learn more effectively. This representation-driven option discovery approach creates a virtuous cycle of refinement, continuously improving both the representation and options, and it is particularly effective for problems that require agents to exhibit different levels of abstractions to succeed.

When: August 23 2023, at 3pm EST
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Nicholas Le Roux

Title: Recent Advances in Functional Optimization

Abstract: Classical continuous optimization generally studies the dynamics in parameter space. We argue that, in several cases, it is more appropriate to analyze these problems in function space. Using as examples standard problems in reinforcement learning and supervised learning, we show both new theoretical results as well as novel practical algorithms.

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

Nadia Lahrichi

Stochastic tabu search and improvements, application for physician scheduling

Abstract: Many approaches are used to handle uncertainty in stochastic combinatorial optimization problems. In this talk, we describe the application of a tabu search approach in a stochastic environment together with a real application in physician scheduling in a radiotherapy center. The goal is to determine a weekly cyclic schedule that improves the patient flow and shortens the pretreatment duration. High uncertainty is associated with the arrival day, profile and type of cancer of each patient. Additionally, two approaches to improve the efficiency of the method are introduced, both are based on leveraging methods that originate outside the field of metaheuristics. The first one discusses hyperparameters tuning. Research shows that it is a nontrivial task and efficient methods are required to obtain the best possible results. We present how blackbox optimization can help choose the tabu search parameters efficiently. We are solving this problem through a Mesh Adaptive Direct Search (MADS) algorithm with no derivative information. The second one presents a learning algorithm for improving tabu search by reducing its search space and evaluation effort. The learning tabu search algorithm uses classification methods in order to better motivate moves through the search space.

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

Sarath Chandar Anbil Parthipan

Limitations of Large Language Models

Abstract: Large language models (LLMs) are becoming increasingly used in various downstream applications not only in natural language processing but also in various other domains including computer vision, reinforcement learning, and scientific discovery to name a few. This talk will focus on the limitations of using LLMs as task solvers. What are the effects of using LLMs as task solvers? What kind of knowledge can an LLM encode (and also what it cannot encode)? Can they efficiently use all the encoded knowledge while learning a downstream task? Are LLMs susceptible to the usual catastrophic forgetting while learning many tasks? How do we identify the biases that these LLMs encode and how do we eliminate those biases? In this talk, I will present an overview of several research projects in my lab that attempt to answer all these questions. This talk will bring to light some of the current limitations of LLMs and how to move forward to build more intelligence systems.

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

Okan Arslan

A contextual framework for learning routing experiences in last-mile delivery

Abstract: We present a contextual framework for learning routing experiences in last-mile delivery. The objective of the framework is to generate routes similar to historic high-quality ones as classified by the operational experts by considering the unstructured features of the last-mile delivery operations. The framework encompasses descriptive, prescriptive and predictive analytics. In the descriptive analytics, we extract rules and preferences of high-quality routes from the data. In the predictive analytics stage, we investigate different derivative-free algorithms for learning the preferences in order to improve the effectiveness of the methods. We develop a label-guided algorithm, which captures any hidden preferences that are not obtained in the descriptive analytics stage. We then use prescriptive methods to generate the routes. Our approach allows us to blend the advantages of all facets of data science in a single collaborative framework, which is effective in learning the preferences and generating high-quality routes. A preliminary version of our descriptive method received the third-place award in the 2021 Amazon Last-Mile Routing Research Challenge.

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

Hani Zbib

Leveraging mutual catastrophe insurance to establish horizontal collaborations in disaster operations management

Abstract: In recent years, the world has witnessed an unprecedented increase in the frequency, intensity, and spread of natural disasters. Enhancing disaster resilience requires affected communities and emergency management agencies to strengthen their disaster preparedness capacities to ensure fast and efficient emergency response post-disasters. One commonly applied preparedness policy is prepositioning, where strategic reserves (e.g., food, water, medicine, rescue supplies) are pre-stored at selected locations for future use. However, building a prepositioning network is expensive. Stakeholders facing similar disaster risks could benefit from establishing a horizontal collaboration by pooling risks, and sharing the network, its resources, and its costs. The design of such collaborations necessitates the integration of logistical and financial considerations and the identification of effective risk pooling, and cost/benefit sharing mechanisms. In this talk, I will present how we can adapt concepts from the mutual catastrophe insurance literature into an effective optimization framework to design multi-year horizontal collaborations. In mutual catastrophe insurance, a set of policyholders contribute premiums to a shared capital pool administered by an insurer for subsequent use when disaster loss occurs. The framework incorporates four integrated decision-making components: contractual design, the prepositioning network design, the management of the insurer’s capital pool, and premiums allocation. I will discuss how each component can be modeled from an Operations Research perspective, the various possible contract types between the insurer and policyholders and their operational implications, and how to solve the resulting large-scale nonlinear multi-stage stochastic program using a tailored solution approach based on Benders’ decomposition.

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

Nicolau Andres-Thio

Characterising harmful data sources in surrogate model construction

Abstract: In the field of Multi-fidelity Expensive Black-Box (Mf-EBB), a problem instance consists of an expensive yet accurate source of information, and one or more cheap yet less accurate sources of information. The field aims to provide techniques either to accurately explain how decisions affect design outcome, or to find the best decisions to optimise design outcomes. Despite the existence of many techniques which provide solutions to both aims, only in recent years have researchers begun to explore the conditions under which the information sources of lesser accuracy can be exploited reliably. This talk will present recent work which approaches the characterisation of harmful low-fidelity sources as an algorithm selection problem. We employ recently developed benchmark filtering techniques to conduct a bias-free assessment, generating and analysing an objectively varied benchmark suite with the technique known as Instance Space Analysis, which provides an intuitive visualisation of when a low-fidelity source should be used. By performing this analysis using only the limited data available to train a surrogate model, we are also able to provide guidelines that can be directly used in an applied industrial setting.

When: 29th of November 2023, 3pm(EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Matthias Soppert

Demand Management in Shared Mobility Systems

Abstract: Shared mobility systems like car sharing and bike sharing have become an attractive and wide-spread type of urban mobility over the past decades. The biggest challenge regarding the profitable operation of such systems is the occurring dynamic imbalance between supply and demand, which stems from fluctuating demand patterns and spatially unbalanced vehicle movements. To counter these imbalances, the scientific literature traditionally focused on the supply-sided control approach by means of active vehicle relocation. In my talk, I present approaches in which demand management is proposed as a cost-efficient alternative, meaning that the system’s demand side is influenced through pricing and availability control. On the one hand, specific practice-relevant problems are addressed and solved. On the other hand, general modeling and solution approaches are developed, which can be transferred to related optimization problems for tactical and operational control of shared mobility systems. Extensive numerical studies, including case studies of Europe’s largest car sharing company Share Now, demonstrate that demand management can be implemented successfully in shared mobility systems.

When: 29th of November 2023, 3pm(EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Mahdis Bayani

A data-driven method for constraint customization in optimization models

Abstract: Decision-makers in different industries use optimization software for planning and decision-making. In numerous practical applications, these optimization tools are often not readily adjustable or configurable by end users due to limited knowledge, resources, or the required investment to consistently make such customizations. As a result, planners frequently adjust the solutions obtained from software based on implicit internal operational rules and preferences in order to make them feasible in practice. These practices may differ across various business units and subsidiaries. To ensure that such rules can be learned and systematically incorporated into optimization models, one can leverage data-driven methods to learn and embed implicit side constraints in a mixed integer linear program (MILP). These customization constraints can be created from machine learning models which are trained using previously implemented solutions. To this end, we extend a data-driven constraint customization framework in the literature which has been developed to extract constraints in the form of a traditional linear regression model to the case when constraints take the form of decision trees. This allows us to learn and incorporate customization constraints in a non-linear or logical form. To demonstrate the value of this data-driven constraint customization framework, experiments were conducted on the knapsack and nurse rostering problems where various combinations of hidden operational rules were simulated.

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

Marius Roland

Adaptive Partitioning for Chance-Constrained Problems

Abstract: This presentation considers chance-constrained stochastic optimization problems (CCSPs) with finite support. We present an iterative algorithm that solves a reduced size chance-constrained model. This reduced model is obtained by partitioning the scenario set and, when solved to optimality, yields a bound on the optimal objective value of the original CCSP. Moreover, the algorithm ensures finite termination at an optimal solution of the original CCSP. At the heart of the algorithm lie two fundamental operations: refinement and merging. Refinement involves splitting a subset of the partition, while merging combines two subsets. These operations are executed to enhance the bound obtained in each step of the algorithm while minimally increasing the size of the reduced model to be solved. Under mild conditions, we prove that, for specific refinement and merge operations, the bound obtained after solving each reduced model strictly improves throughout the iterative process. Furthermore, the algorithm structure allows for the seamless integration of various computational enhancements, significantly reducing the computational time required to solve the reduced chance-constrained problems. Based on theoretical arguments we also provide strategies to initialize the partition considered in the algorithm. Further, we make a parallel with the well studied quantile cuts, leading to a new family of stronger valid inequalities. The efficiency of the algorithm is assessed through numerical experiments. We study the impact of every component of the algorithm and compare its performance against state-of-the-art methods on chance constrained multidimensional knapsack problems.

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

Sean Sinclair

Hindsight Learning for MDPs with Exogenous Inputs

Abstract: Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem: allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods.

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

Maximilian Schiffer

Combinatorial optimization augmented machine learning for contextual multi-stage problems

Abstract: Combinatorial optimization augmented machine learning (COAML) is a novel field that combines methods from machine learning and operations research to tackle contextual data-driven problems that involve both uncertainty and combinatorics. These problems arise frequently in industrial processes, where firms seek to leverage large and noisy data sets to optimize their operations. COAML typically involves embedding combinatorial optimization layers into neural networks and training them with decision-aware learning techniques. This talk provides an overview of the underlying paradigm, algorithmic pipelines, and foundations based on selected application cases. Particularly, I will demonstrate the effectiveness of COAML on contextual and dynamic stochastic optimization problems, as evidenced by its winning performance on the 2022 EUROMeetsNeurIPS dynamic vehicle routing challenge.

When: 22 February 2023, 3pm (EST)
Where: Pavillon André-Aisenstadt (Université de Montréal), 4th floor, GERAD Conference Room(4488)

Justin Dumouchelle

Neural Heuristics for Mathematical Optimization via Value Function Approximation

Abstract: Mathematical optimization is an invaluable framework for modeling and solving decision-making problems with many successes in single-level deterministic problems (e.g., mixed-integer linear or nonlinear optimization). However, many real-world problems require accounting for uncertainty or the reaction of another agent. Paradigms such as stochastic optimization, bilevel optimization, and robust optimization can model these situations but are much slower to solve than their deterministic counterparts, especially when discrete decisions must be made. In this work, we demonstrate how a single learning-based framework, based on value function approximation, can be adapted to all three domains. Empirically, we find solutions of similar, and in some cases significantly better, quality than state-of-the-art algorithms in each field, often within a fraction of the running time. The datasets and three frameworks, Neur2SP (NeurIPS'22), Neur2RO (ICLR'24), and Neur2BiLO (under review at ICML'24), are open-sourced for further research.

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

Ricardo Fukasawa

Fast exact algorithms for some interdiction problems

Abstract: While several optimization problems consider that there is a single decision-maker involved, interdiction problems are a form of Stackelberg game where there are two decision-makers involved: a leader and a follower. The follower follows a “classical” optimization problem, trying to optimize a given objective subject to some constraints. The leader is allowed to interdict/block items that are available to the follower, with the goal to make the follower’s objective as bad as possible. This form of zero-sum game can be significantly harder than the original classical counterparts, both in terms of complexity class and in terms of exact algorithm performance. We study two variants of this problem, with the assumption that the leader must satisfy a knapsack constraint. The different variants relate to the problem the follower solves: knapsack and minimum spanning tree. The algorithms we develop are based on branch-and-bound with a carefully devised bounding scheme. They improve significantly (by orders of magnitude) the limits of exact algorithms for these problems and show that there is much that can be further researched in this area.

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