Margarida Carvalho

Guy Desaulniers

2023-04-14

International Transactions in Operational Research (publié)

Optimization of the location and design of urban green spaces

Caroline Leboeuf

Yan Kestens

Benoit Thierry

2023-03-13

ArXiv (prépublication)

Game theoretical analysis of Kidney Exchange Programs

2023-02-01

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 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é)

Adaptation, Comparison and Practical Implementation of Fairness Schemes in Kidney Exchange Programs

William St-Arnaud

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)

Capacity Variation in the Many-to-one Stable Matching

Federico Bobbio

Alfredo Torrico

2022-05-03

ArXiv (prépublication)

Computing Nash equilibria for integer programming games

Joao Pedro Pedroso

2022-01-01

European Journal of Operational Research (publié)

ZERO: Playing Mathematical Programming Games

Gabriele Dragotto

S. Sankaranarayanan

2021-11-15

ArXiv (prépublication)

The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations

Gabriele Dragotto

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)

Capacity Planning in Stable Matching

Federico Bobbio

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)