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
William St-Arnaud
PhD - Université de Montréal
Principal supervisor :
Golnoosh Farnadi
Nagisa Sugishita
Postdoctorate - HEC Montréal

Publications

Integer Programming Games.
Margarida Carvalho
Gabriele Dragotto
Andrea Lodi
Sriram Sankaranarayanan 0002
2025-01-01
Foundations and Trends® in Optimization (published)
doi.org
A Learning-Based Framework for Fair and Scalable Solution Generation in Kidney Exchange Problems
William St-Arnaud
Margarida Carvalho
Golnoosh Farnadi
2025-01-01
Trans. Mach. Learn. Res. (published)
openreview.net
openreview.net
Software and Data for "Capacity Planning in Stable Matching"
Federico Bobbio
Margarida Carvalho
Andrea Lodi
Ignacio Rios
Alfredo Torrico
2025-01-01
Operational Research (published)
doi.org
A stochastic integer programming approach to reserve staff scheduling with preferences
Carl Perreault‐Lafleur
Margarida Carvalho
Guy Desaulniers
2025-01-01
Int. Trans. Oper. Res. (published)
doi.org
arxiv.org
The Strength of Flow Refueling Location Problem Formulations and an Extension to Cyclic Routing
Nagisa Sugishita
Margarida Carvalho
Ribal Atallah
The Flow Refueling Location Problem (FRLP) is a stylized model for determining the optimal placement of refueling stations for vehicles with… (see more) limited travel ranges, such as hydrogen fuel cell vehicles and electric vehicles. A notable extension, the deviation FRLP, accounts for the possibility that drivers may deviate from their preferred routes to refuel or recharge. While solution techniques based on various mathematical programming formulations have been thoroughly explored for this extension, there is a lack of theoretical insights into the relationships and strengths of these formulations. In this work, for the deviation extension, we study two prominent FRLP formulations from the literature and compare their strengths in terms of linear programming (LP) relaxations. We show that the LP relaxation of one formulation yields a bound that is at least as tight as that of the other, which may explain its observed superior performance. Building on these insights, we address a common modeling assumption in the FRLP that requires drivers to use the same paths for their outbound and inbound trips. Specifically, we relax this assumption and introduce the cyclic FRLP, where drivers may use different paths in each direction. We show how existing formulations can be naturally extended to accommodate this setting and describe a branch-and-cut algorithm to solve the problem. We provide numerical experiments highlighting the benefits of such asymmetric routing. For example, in an instance based on the Californian network, the cyclic FRLP serves all demands using 30% fewer facilities than the original FRLP.
2024-09-06
ArXiv (preprint)
arxiv.org
arxiv.org
The Strength of Fuel Refueling Location Problem Formulations
Nagisa Sugishita
Margarida Carvalho
Ribal Atallah
2024-09-06
ArXiv (preprint)
arxiv.org
arxiv.org
Accelerated Benders Decomposition and Local Branching for Dynamic Maximum Covering Location Problems
Steven Lamontagne
Margarida Carvalho
Ribal Atallah
The maximum covering location problem (MCLP) is a key problem in facility location, with many applications and variants. One such variant is… (see more) 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-07-01
Computers & Operations Research (published)
doi.org
arxiv.org
Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract)
William St-Arnaud
Margarida Carvalho
Golnoosh Farnadi
2024-03-24
Proceedings of the AAAI Conference on Artificial Intelligence (published)
doi.org
The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.
Henrique Brito
Henrique Lopes
Margarida Carvalho
Daniel Carrilho
Adriano Carvalho
Duarte Araújo
2024-03-01
Psychology of Sport And Exercise (published)
doi.org
The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.
Henrique Brito
Henrique Lopes
Margarida Carvalho
Daniel Carrilho
Adriano Carvalho
Duarte Araújo
2024-03-01
Psychology of Sport And Exercise (published)
doi.org
Solving Two-Stage Stochastic Programs with Endogenous Uncertainty via Random Variable Transformation
Maria Bazotte
Margarida Carvalho
Thibaut Vidal
2024-02-23
ArXiv (preprint)
arxiv.org
arxiv.org
The Sample Average Approximation Method for Solving Two-Stage Stochastic Programs with Endogenous Uncertainty
Maria Bazotte
Margarida Carvalho
Thibaut Vidal
Real-world decision-making problems involve Type 1 decision-dependent uncertainty, where the probability distribution of the stochastic proc… (see more)ess depends on the model decisions. However, few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We thus propose herein a general method for solving a class of these programs based on the transformation of random variables, a technique widely employed in probability and statistics. The proposed method is tailored to large-scale problems with discrete or continuous endogenous random variables. The random variable transformation allows the use of the sample average approximation (SAA) method, which provides optimality convergence guarantees under certain conditions. We show that, for some classical distributions, the proposed method reduces to solving mixed-integer linear or convex programs. Finally, we validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. Whereas most distributions result in a nonlinear nonconvex deterministic equivalent program, the proposed method solves mixed-integer linear programs in all cases. In addition, it produces attractive performance estimators for the SAA method in a reasonable computational time and outperforms the case in which the endogenous distribution defines a mixed-integer deterministic equivalent.
2024-02-23
ArXiv (preprint)
arxiv.org
arxiv.org