Portrait de Margarida Carvalho

Margarida Carvalho

Membre académique associé
Professeure adjointe, Université de Montréal, Département d'informatique et de recherche opérationnelle
Sujets de recherche
Équité algorithmique
IA et durabilité
Optimisation
Optimisation combinatoire
Théorie de la décision
Théorie des jeux
Site web
Google Scholar

Biographie

Margarida Carvalho est titulaire d'un baccalauréat et d'une maîtrise en mathématiques. Elle a obtenu un doctorat en informatique à l'Université de Porto, pour lequel elle a reçu le prix de la thèse EURO en 2018. La même année, elle est devenue professeure adjointe au Département d'informatique et de recherche opérationnelle de l'Université de Montréal, où elle occupe la Chaire de recherche FRQ-IVADO en science des données pour la théorie des jeux combinatoires.

Elle est une experte en recherche opérationnelle, notamment en optimisation combinatoire et en théorie algorithmique des jeux. Ses recherches sont motivées par des problèmes de prise de décision du monde réel impliquant l'interaction de plusieurs agents, tels que les programmes d'échange de reins, le choix des écoles et les marchés concurrentiels.

Étudiants actuels

Marylou Fauchard
Maîtrise recherche - UdeM
Co-superviseur⋅e :
Golnoosh Farnadi
marylou.fauchard@mila.quebec
William St-Arnaud
Doctorat - UdeM
Superviseur⋅e principal⋅e :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorat - UdeM

Publications

Integer Programming Games: A Gentle Computational Overview
Margarida Carvalho
Gabriele Dragotto
Andrea Lodi
Sriram Sankaranarayan
2023-06-05
ArXiv (prépublication)
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 (publié)
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 (prépublication)
doi.org
arxiv.org
Game theoretical analysis of Kidney Exchange Programs
Margarida Carvalho
Andrea Lodi
2023-02-01
European Journal of Operational Research (publié)
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… (voir plus)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. (publié)
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… (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.
2022-07-01
ArXiv (prépublication)
arxiv.org
arxiv.org
Capacity Variation in the Many-to-one Stable Matching
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Alfredo Torrico
2022-05-03
ArXiv (prépublication)
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 (publié)
doi.org
arxiv.org
ZERO: Playing Mathematical Programming Games
Gabriele Dragotto
S. Sankaranarayanan
Margarida Carvalho
Andrea Lodi
2021-11-15
ArXiv (prépublication)
arxiv.org
arxiv.org
The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations
Margarida Carvalho
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… (voir plus)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.
2021-11-10
ArXiv (prépublication)
arxiv.org
arxiv.org
Capacity Planning in Stable Matching
Federico Bobbio
Margarida Carvalho
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… (voir plus) 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.
2021-10-02
ArXiv (prépublication)
arxiv.org
arxiv.org
Individual Fairness in Kidney Exchange Programs
Golnoosh Farnadi
William St-Arnaud
Behrouz Babaki
Margarida Carvalho
2021-05-18
AAAI Conference on Artificial Intelligence (publié)
doi.org