Margarida Carvalho

Daniel Carrilho

Adriano Carvalho

Duarte Araújo

2024-02-29

Psychology of Sport And Exercise (publié)

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… (voir plus)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-22

ArXiv (prépublication)

Diagnosis Model for Detection of e-threats Against Soft-Targets

Sónia M. A. Morgado

Sérgio Felgueiras

2024-02-13

Lecture Notes in Networks and Systems (publié)

Asymmetry in the complexity of the multi-commodity network pricing problem

Quang Minh Bui

José Neto

2023-12-31

Math. Program. (publié)

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… (voir plus)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-30

Web and Internet Economics (publié)

When Nash Meets Stackelberg

Gabriele Dragotto

Felipe Feijoo

Andrea Lodi

Sriram Sankaranarayanan

2023-12-21

Management Science (publié)

Capacity Planning in Stable Matching: An Application to School Choice

Federico Bobbio

Andrea Lodi

Ignacio Rios

Alfredo Torrico

Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students … (voir plus)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-06

Proceedings of the 24th ACM Conference on Economics and Computation (publié)

Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming

Mostafa Elaraby

Guy Wolf

2023-05-22

Integration of Constraint Programming, Artificial Intelligence, and Operations Research (publié)

Optimization of the location and design of urban green spaces

Caroline Leboeuf

Yan Kestens

Benoit Thierry

2023-03-12

ArXiv (prépublication)

A theoretical and computational equilibria analysis of a multi-player kidney exchange program

Andrea Lodi

2023-01-31

European Journal of Operational Research (publié)

Optimising Electric Vehicle Charging Station Placement using Advanced Discrete Choice Models

Steven Lamontagne

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 multi-period time frame so as to max… (voir plus)imise electric vehicle adoption. Via the use of advanced 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. Instead of embedding an analytical probability model in the formulation, we adopt a simulation approach and pre-compute 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. Using the pre-computed error terms to calculate the users covered by each charging station allows for a maximum covering model, for which solutions can 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 GRASP heuristics to obtain good quality solutions more efficiently. Extensive computational results are provided, which compare the maximum covering formulation with the current state-of-the-art, both for exact solutions and the heuristic methods. Keywords: Electric vehicle charging stations, facility location, integer programming, discrete choice models, maximum covering

2022-12-31

INFORMS J. Comput. (publié)

Capacity Variation in the Many-to-one Stable Matching

Federico Bobbio

Andrea Lodi

Alfredo Torrico

2022-05-02

ArXiv (prépublication)