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
Website
Google Scholar

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

Marylou Fauchard
Master's Research - Université de Montréal
Co-supervisor :
Golnoosh Farnadi
marylou.fauchard@mila.quebec
William St-Arnaud
PhD - Université de Montréal
Principal supervisor :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorate - Université de Montréal

Publications

Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs
Margarida Carvalho
Alison Caulfield
Yi Lin
Adrian Vetta
A kidney exchange program, also called a kidney paired donation program, can be viewed as a repeated, dynamic trading and allocation mechani… (see more)sm. This suggests that a dynamic algorithm for transplant exchange selection may have superior performance in comparison to the repeated use of a static algorithm. We confirm this hypothesis using a full scale simulation of the Canadian Kidney Paired Donation Program: learning algorithms, that attempt to learn optimal patient-donor weights in advance via dynamic simulations, do lead to improved outcomes. Specifically, our learning algorithms, designed with the objective of fairness (that is, equity in terms of transplant accessibility across cPRA groups), also lead to an increased number of transplants and shorter average waiting times. Indeed, our highest performing learning algorithm improves egalitarian fairness by 10% whilst also increasing the number of transplants by 6% and decreasing waiting times by 24%. However, our main result is much more surprising. We find that the most critical factor in determining the performance of a kidney exchange program is not the judicious assignment of positive weights (rewards) to patient-donor pairs. Rather, the key factor in increasing the number of transplants, decreasing waiting times and improving group fairness is the judicious assignment of a negative weight (penalty) to the small number of non-directed donors in the kidney exchange program.
2023-12-31
Web and Internet Economics (published)
doi.org
arxiv.org
When Nash Meets Stackelberg
Margarida Carvalho
Gabriele Dragotto
Felipe Feijoo
Andrea Lodi
Sriram Sankaranarayanan
2023-12-22
Management Science (published)
doi.org
arxiv.org
Maximum flow-based formulation for the optimal location of electric vehicle charging stations
Pierre-Luc Parent
Margarida Carvalho
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… (see more)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.
2023-12-10
ArXiv (preprint)
doi.org
arxiv.org
Capacity Planning in Stable Matching: An Application to School Choice
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Ignacio Rios
Alfredo Torrico
Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students … (see more)to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. 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 school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.
2023-07-07
Proceedings of the 24th ACM Conference on Economics and Computation (published)
doi.org
Integer Programming Games: A Gentle Computational Overview
Margarida Carvalho
Gabriele Dragotto
Andrea Lodi
Sriram Sankaranarayan
2023-06-05
ArXiv (preprint)
doi.org
arxiv.org
Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming
Mostafa ElAraby
Guy Wolf
Margarida Carvalho
2023-05-23
Integration of Constraint Programming, Artificial Intelligence, and Operations Research (published)
doi.org
arxiv.org
Optimization of the location and design of urban green spaces
Caroline Leboeuf
Margarida Carvalho
Yan Kestens
Benoit Thierry
2023-03-13
ArXiv (preprint)
doi.org
arxiv.org
Game theoretical analysis of Kidney Exchange Programs
Margarida Carvalho
Andrea Lodi
2023-02-01
European Journal of Operational Research (published)
doi.org
arxiv.org
Optimising Electric Vehicle Charging Station Placement Using Advanced Discrete Choice Models
Steven Lamontagne
Margarida Carvalho
Emma Frejinger
Bernard Gendron
Miguel F. Anjos
Ribal Atallah
D'epartement d'informatique et de recherche op'erationnelle
U. Montr'eal
S. O. Mathematics
U. Edinburgh
Institut de Recherche d'Hydro-Qu'ebec
We present a new model for finding the optimal placement of electric vehicle charging stations across a multiperiod time frame so as to maxi… (see more)mise electric vehicle adoption. Via the use of stochastic discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. We adopt a simulation approach and precompute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Our major contribution is a reformulation into a maximum covering model, which uses the precomputed error terms to calculate the users covered by each charging station. This allows solutions to be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and greedy randomised adaptive search procedure heuristics to obtain good-quality solutions more efficiently. Extensive computational results are provided, and they compare the maximum covering formulation with the current state of the art for both exact solutions and the heuristic methods. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Hydro-Québec and the Natural Sciences and Engineering Research Council of Canada [Discovery grant 2017-06054; Collaborative Research and Development Grant CRDPJ 536757–19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0185 .
2023-01-01
INFORMS J. Comput. (published)
doi.org
arxiv.org
Adaptation, Comparison and Practical Implementation of Fairness Schemes in Kidney Exchange Programs
William St-Arnaud
Margarida Carvalho
Golnoosh Farnadi
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.
2022-07-01
ArXiv (preprint)
doi.org
arxiv.org
Capacity Variation in the Many-to-one Stable Matching
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Alfredo Torrico
2022-05-03
ArXiv (preprint)
doi.org
arxiv.org
Computing Nash equilibria for integer programming games
Margarida Carvalho
Andrea Lodi
João Pedro Pedroso
2022-01-01
European Journal of Operational Research (published)
doi.org
arxiv.org