Portrait of Margarida Carvalho

Margarida Carvalho

Associate Academic Member
Assistant Professor, Université de Montréal, Department of Computer Science and Operations Research
Research Topics
AI and Sustainability
Algorithmic Fairness
Combinatorial Optimization
Decision Theory
Game Theory
Optimization

Biography

Margarida Carvalho holds a bachelor’s and master’s degree in mathematics. She completed her PhD in computer science at the University of Porto, for which she received the 2018 EURO Doctoral Dissertation Award.

In 2018, Carvalho was appointed assistant professor in the Department of Computer Science and Operations Research at Université de Montréal, where she holds the FRQ-IVADO Research Chair in Data Science for Combinatorial Game Theory.

She is an expert in operations research, in particular, combinatorial optimization and algorithmic game theory. Her research is motivated by real-world decision-making problems that involve the interaction of multiple agents, such as kidney exchange programs, school choice and competitive markets.

Current Students

Master's Research - Université de Montréal
Co-supervisor :
PhD - Université de Montréal
Principal supervisor :
Postdoctorate - HEC Montréal

Publications

Capacity Planning in Stable Matching
Federico Bobbio
Andrea Lodi
Ignacio Rios
Alfredo Torrico
Optimizing School Seat Allocation to Improve Access and Fairness A growing shortage of public school seats in Chile has left thousands of st… (see more)udents unassigned each year. In their forthcoming Operations Research paper, “Capacity Planning in Stable Matching,” Bobbio et al. (2025) develop a novel framework that jointly determines where to expand school capacities and computes a student-optimal stable assignment in the enlarged market. The study develops exact and heuristic methods that make this theoretically complex problem tractable in practice. Using rich administrative data from the Chilean school choice system, the framework demonstrates how adding a limited number of seats can trigger improvement chains benefiting multiple students, also revealing diminishing marginal returns to capacity expansion. Beyond the Chilean context, the framework provides a versatile toolkit that can be adapted to other constrained allocation problems, offering a rigorous foundation for data-driven policy design in education and beyond.
Capacity Planning in Stable Matching
Federico Bobbio
Andrea Lodi
Ignacio Rios
Alfredo Torrico
We introduce the problem of jointly increasing school capacities and finding a student-optimal assignment in the expanded market. Due to the… (see more) impossibility of efficiently solving the problem with classical methods, we generalize existent mathematical programming formulations of stability constraints to our setting, most of which result in integer quadratically-constrained programs. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially large on the problem size. We show that its stability constraints can be separated by exploiting the objective function, leading to an effective cutting-plane algorithm. We conclude the theoretical analysis of the problem by discussing some mechanism properties. On the computational side, we evaluate the performance of our approaches in a detailed study, and we find that our cutting-plane method outperforms our generalization of existing mixed-integer approaches. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional seat can benefit multiple students and that we can effectively target the assignment of previously unassigned students or improve the assignment of several students through improvement chains. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.
Capacity Planning in Stable Matching
Federico Bobbio
Andrea Lodi
Ignacio Rios
Alfredo Torrico
Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets
Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets
Recent advances in reasoning with large language models (LLMs) have demonstrated strong performance on complex mathematical tasks, including… (see more) combinatorial optimization. Techniques such as Chain-of-Thought and In-Context Learning have further enhanced this capability, making LLMs both powerful and accessible tools for a wide range of users, including non-experts. However, applying LLMs to matching problems, which require reasoning under preferential and structural constraints, remains underexplored. To address this gap, we introduce a novel benchmark of 369 instances of the College Admission Problem, a canonical example of a matching problem with preferences, to evaluate LLMs across key dimensions: feasibility, stability, and optimality. We employ this benchmark to assess the performance of several open-weight LLMs. Our results first reveal that while LLMs can satisfy certain constraints, they struggle to meet all evaluation criteria consistently. They also show that reasoning LLMs, like QwQ and GPT-oss, significantly outperform traditional models such as Llama, Qwen or Mistral, defined here as models used without any dedicated reasoning mechanisms. Moreover, we observed that LLMs reacted differently to the various prompting strategies tested, which include Chain-of-Thought, In-Context Learning and role-based prompting, with no prompt consistently offering the best performance. Finally, we report the performances from iterative prompting with auto-generated feedback and show that they are not monotonic; they can peak early and then significantly decline in later attempts. Overall, this work offers a new perspective on model reasoning performance and the effectiveness of prompting strategies in combinatorial optimization problems with preferential constraints.
Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets
Recent advances in reasoning with large language models (LLMs) have demonstrated strong performance on complex mathematical tasks, including… (see more) combinatorial optimization. Techniques such as Chain-of-Thought and In-Context Learning have further enhanced this capability, making LLMs both powerful and accessible tools for a wide range of users, including non-experts. However, applying LLMs to matching problems, which require reasoning under preferential and structural constraints, remains underexplored. To address this gap, we introduce a novel benchmark of 369 instances of the College Admission Problem, a canonical example of a matching problem with preferences, to evaluate LLMs across key dimensions: feasibility, stability, and optimality. We employ this benchmark to assess the performance of several open-weight LLMs. Our results first reveal that while LLMs can satisfy certain constraints, they struggle to meet all evaluation criteria consistently. They also show that reasoning LLMs, like QwQ and GPT-oss, significantly outperform traditional models such as Llama, Qwen or Mistral, defined here as models used without any dedicated reasoning mechanisms. Moreover, we observed that LLMs reacted differently to the various prompting strategies tested, which include Chain-of-Thought, In-Context Learning and role-based prompting, with no prompt consistently offering the best performance. Finally, we report the performances from iterative prompting with auto-generated feedback and show that they are not monotonic; they can peak early and then significantly decline in later attempts. Overall, this work offers a new perspective on model reasoning performance and the effectiveness of prompting strategies in combinatorial optimization problems with preferential constraints.
Adaptation, Comparison and Practical Implementation of Fairness Schemes in Kidney Exchange Programs
In Kidney Exchange Programs (KEPs), each participating patient is registered together with an incompatible donor. Donors without an incompat… (see more)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.
Computing Approximate Nash Equilibria for Integer Programming Games
Aloïs Duguet
Gabriele Dragotto
Sandra-ulrich Ngueveu
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 … (see more)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.
What makes a good public EV charging station? A revealed preference study
Steven Lamontagne
Ribal Atallah
What makes a good public EV charging station? A revealed preference study
Steven Lamontagne
Ribal Atallah
To determine the optimal locations for electric vehicle charging stations, optimisation models need to predict which charging stations users… (see more) will select. We estimate discrete choice models to predict the usage of charging stations using only readily available information for charging network operators. Our parameter values are estimated from a unique, revealed preferences dataset of charging sessions in Montreal, Quebec. We find that user distance to stations, proximity to home areas, and the number of outlets at each station are significant factors for predicting station usage. Additionally, amenities near charging stations have a neutral effect overall, with some users demonstrating strong preference or aversion for these locations. High variability among the preferences of users highlight the importance of models which incorporate panel effects. Moreover, integrating mixed logit models within the optimization of charging station network design yields high-quality solutions, even when evaluated under other model specifications.
Integer Programming Games.
Gabriele Dragotto
Andrea Lodi 0001
Sriram Sankaranarayanan 0002