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 - Université de Montréal

Publications

A stochastic integer programming approach to reserve staff scheduling with preferences
Carl Perreault‐Lafleur
Guy Desaulniers
The Strength of Fuel Refueling Location Problem Formulations
Nagisa Sugishita
Ribal Atallah
Accelerated Benders Decomposition and Local Branching for Dynamic Maximum Covering Location Problems
Steven Lamontagne
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.
Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract)
Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models
Quang Minh Bui
Jos'e 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.
The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.
Henrique Brito
Henrique Lopes
Daniel Carrilho
Adriano Carvalho
Duarte Araújo
The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.
Henrique Brito
Henrique Lopes
Daniel Carrilho
Adriano Carvalho
Duarte Araújo
Solving Two-Stage Stochastic Programs with Endogenous Uncertainty via Random Variable Transformation
Maria Bazotte
Thibaut Vidal
The Sample Average Approximation Method for Solving Two-Stage Stochastic Programs with Endogenous Uncertainty
Maria Bazotte
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.
Computing Approximate Nash Equilibria for Integer Programming Games
Aloïs Duguet
Gabriele Dragotto
Sandra-ulrich Ngueveu
Asymmetry in the complexity of the multi-commodity network pricing problem
Quang Minh Bui
Jos'e Neto
Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs
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.