Margarida Carvalho

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)

Computing Nash Equilibria for Integer Programming Games

Andrea Lodi

João Pedro Pedroso

The recently defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, wit… (voir plus)h their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be fit in this class, and hence anticipating IPG outcomes is of crucial value for policy makers and regulators. Nash equilibria have been widely accepted as the solution concept of a game. Consequently, their computation provides a reasonable prediction of the games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop two general algorithmic approaches that are guaranteed to approximate an equilibrium under mild conditions. We also showcase how our methodology can be changed to determine other equilibria definitions. The performance of our methods is analyzed through computational experiments in a knapsack game, a competitive lot-sizing game, and a kidney exchange game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games have been designed and computationally tested.

2021-12-31

European Journal of Operational Research (publié)

ZERO: Playing Mathematical Programming Games

Gabriele Dragotto

S. Sankaranarayanan

Andrea Lodi

2021-11-14

ArXiv (prépublication)

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

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-09

ArXiv (prépublication)

Individual Fairness in Kidney Exchange Programs

Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a dono… (voir plus)r which matches their physiological characteristics. Kidney exchange programs (KEPs) seek to match such incompatible patient-donor pairs together, usually with the main objective of maximizing the total number of transplants. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. In this paper, the existence of multiple optimal plans for a KEP is explored as a mean to achieve individual fairness. We propose the use of randomized policies for selecting an optimal solution in which patients' equal opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. The advantages of our proposed method over the common practice of using the optimal solution obtained by a solver are stressed through computational experiments. Our methodology enables decision makers to fully control KEP outcomes, overcoming any potential bias or vulnerability intrinsic to a deterministic solver.

2021-05-17

AAAI Conference on Artificial Intelligence (publié)

Capacity Expansion in the College Admission Problem

Federico Bobbio

Andrea Lodi

Alfredo Torrico

2020-12-31

arXiv.org (prépublication)

dblp.uni-trier.de

Multilevel Approaches for the Critical Node Problem

Andrea Baggio

Andrea Lodi

Andrea Tramontani

In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious … (voir plus)viral attacks. In particular, many results rely on two different viewpoints. On the one hand, network safety is investigated from a preventive perspective. In this paradigm, for a given network, the goal is to modify its structure, in order to minimize the propagation of failures. On the other hand, blocking models have been proposed for scenarios where the attack has already taken place. In this case, a harmful spreading process is assumed to propagate through the network with particular dynamics, allowing some time for an effective defensive reaction. In this work, we combine these two perspectives. More precisely, following the framework Defender-AttackerDefender, we consider a model of prevention, attack, and damage containment using a three-stage, sequential game. Thus, we assume the defender not only to be able to adopt preventive strategies but also to defend the network after an attack takes place. Assuming that the attacker will act optimally, we want to chose a defensive strategy for the first stage that would minimize the total damage to the network in the end of the third stage. Our contribution consists of considering this problem as a trilevel Mixed-Integer Program and design an exact algorithm for it based on tools developed for multilevel programming.

2020-12-31

Operational Research (publié)

Multi-agent Assortment Optimization in Sequential Matching Markets

Alfredo Torrico

Andrea Lodi

2020-06-07

ArXiv (prépublication)