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 :

Publications

Optimization of the location and design of urban green spaces
Caroline Leboeuf
Yan Kestens
Benoit Thierry
Game theoretical analysis of Kidney Exchange Programs
Andrea Lodi
Optimising Electric Vehicle Charging Station Placement Using Advanced Discrete Choice Models
Steven Lamontagne
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 .
Capacity Variation in the Many-to-one Stable Matching
Federico Bobbio
Andrea Lodi
Alfredo Torrico
Computing Nash equilibria for integer programming games
Andrea Lodi
João Pedro Pedroso
ZERO: Playing Mathematical Programming Games
Gabriele Dragotto
S. Sankaranarayanan
Andrea Lodi
The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations
Gabriele Dragotto
Andrea Lodi
Sriram Sankaranarayanan
We introduce the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve non… (see more)convex and possibly unbounded optimization problems. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the original game and refines them with techniques from integer programming, for instance, cutting planes and branching operations. We test our algorithm on two families of challenging nonconvex games involving discrete decisions and bilevel programs, and we empirically demonstrate that it efficiently computes equilibria and outperforms existing game-specific algorithms.
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.
Individual Fairness in Kidney Exchange Programs
William St-Arnaud
Behrouz Babaki
Capacity Expansion in the College Admission Problem
Federico Bobbio
Andrea Lodi
Alfredo Torrico
Multilevel Approaches for the Critical Node Problem
Andrea Baggio
Andrea Lodi
Andrea Tramontani
Multi-agent Assortment Optimization in Sequential Matching Markets
Alfredo Torrico
Andrea Lodi