Margarida Carvalho

marylou.fauchard@mila.quebec

Francesco Morri

Postdoctorat - Polytechnique

Co-superviseur⋅e :

Quentin Cappart

francesco98m@gmail.com

Doctorat - UdeM

Superviseur⋅e principal⋅e :

william.st-arnaud@mila.quebec

Nagisa Sugishita

Postdoctorat - HEC

nagisa.sugishita@mila.quebec

Publications

Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets

2025-09-21

WiML @ Neural Information Processing Systems (publié)

openreview.net

Computing Approximate Nash Equilibria for Integer Programming Games

Aloïs Duguet

Gabriele Dragotto

Sandra-ulrich Ngueveu

2025-07-30

Optimization Letters (publié)

Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models

Quang Minh Bui

José Neto

The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items … (voir plus)that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader's goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower's problem as a longest path problem using a dynamic programming model, and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to 2 distinct dynamic programming models, namely, a novel formulation designated as selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across 3 different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the 2 proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs.

2025-04-27

INFORMS Journal on Computing (publié)

Adaptation, Comparison and Practical Implementation of Fairness Schemes in Kidney Exchange Programs

William St-Arnaud

In Kidney Exchange Programs (KEPs), each participating patient is registered together with an incompatible donor. Donors without an incompat… (voir plus)ible patient can also register. Then, KEPs typically maximize overall patient benefit through donor exchanges. This aggregation of benefits calls into question potential individual patient disparities in terms of access to transplantation in KEPs. Considering solely this utilitarian objective may become an issue in the case where multiple exchange plans are optimal or near-optimal. In fact, current KEP policies are all-or-nothing, meaning that only one exchange plan is determined. Each patient is either selected or not as part of that unique solution. In this work, we seek instead to find a policy that contemplates the probability of patients of being in a solution. To guide the determination of our policy, we adapt popular fairness schemes to KEPs to balance the usual approach of maximizing the utilitarian objective. Different combinations of fairness and utilitarian objectives are modelled as conic programs with an exponential number of variables. We propose a column generation approach to solve them effectively in practice. Finally, we make an extensive comparison of the different schemes in terms of the balance of utility and fairness score, and validate the scalability of our methodology for benchmark instances from the literature.

2025-03-02

European Journal of Operational Research (publié)

Integer Programming Games: A Gentle Computational Overview

Gabriele Dragotto

Andrea Lodi

Sriram Sankaranarayan

2024-12-31

Foundations and Trends® in Optimization (publié)

A Learning-Based Framework for Fair and Scalable Solution Generation in Kidney Exchange Problems

William St-Arnaud

2024-12-31

Trans. Mach. Learn. Res. (publié)

openreview.net

Software and Data for "Capacity Planning in Stable Matching"

Federico Bobbio

Andrea Lodi

Ignacio Rios

Alfredo Torrico

2024-12-31

Operational Research (publié)

A stochastic integer programming approach to reserve staff scheduling with preferences

Carl Perreault‐Lafleur

Guy Desaulniers

2024-12-31

Int. Trans. Oper. Res. (publié)

The Strength of Fuel Refueling Location Problem Formulations

Nagisa Sugishita

Ribal Atallah

2024-09-05

ArXiv (prépublication)

Accelerated Benders Decomposition and Local Branching for Dynamic Maximum Covering Location Problems

Steven Lamontagne

Ribal Atallah

The maximum covering location problem (MCLP) is a key problem in facility location, with many applications and variants. One such variant is… (voir plus) the dynamic (or multi-period) MCLP, which considers the installation of facilities across multiple time periods. To the best of our knowledge, no exact solution method has been proposed to tackle large-scale instances of this problem. To that end, in this work, we expand upon the current state-of-the-art branch-and-Benders-cut solution method in the static case, by exploring several acceleration techniques. Additionally, we propose a specialised local branching scheme, that uses a novel distance metric in its definition of subproblems and features a new method for efficient and exact solving of the subproblems. These methods are then compared through extensive computational experiments, highlighting the strengths of the proposed methodologies.

2024-06-30

Computers & Operations Research (publié)

Maximum flow-based formulation for the optimal location of electric vehicle charging stations

Pierre‐Luc Parent

Miguel F. Anjos

Ribal Atallah

With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EV… (voir plus)s) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed‐integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real‐world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

2024-04-10

Networks (publié)

Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract)

William St-Arnaud

Generative Flow Networks, known as GFlowNets, have been introduced in recent times, presenting an exciting possibility for neural networks t… (voir plus)o model distributions across various data structures. In this paper, we broaden their applicability to encompass scenarios where the data structures are optimal solutions of a combinatorial problem. Concretely, we propose the use of GFlowNets to learn the distribution of optimal solutions for kidney exchange problems (KEPs), a generalized form of matching problems involving cycles.

2024-03-23

Proceedings of the AAAI Conference on Artificial Intelligence (publié)