Research Interests

  • Nash equilibria
  • Algorithmic Game Theory
  • Bilevel Programming
  • Interdiction Problems
  • Integer Programming Games
  • Computational Complexity
  • Policy Making
  • Robust Optimization
  • Matching Markets

Applications

  • Kidney Exchange Programs
  • Electric Vehicles Adoption
  • Social Good
  • Cyber Security
  • Sustainability
  • Artificial Neural Networks sparsification

Publications

M. Carvalho, A. Lodi, A theoretical and computational equilibria analysis of a multi-player kidney exchange program

European Journal of Operational Research, Volume 305, Issue 1, 373-385, .

﹀ Show more

Abstract

A main aim of kidney exchange programs (KEPs) is to maximize the number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP involving pairs from pools of several hospitals, regions, or countries has the potential to increase the number of transplants. These entities may behave strategically and strive to maximize the transplant benefit for their patients. Recently, a decentralized non-cooperative game was formulated to model this situation, and the game solutions (equilibria) for the 2-player case were characterized when each player's utility is the number of her patients receiving a kidney and exchanges are restricted to pairwise.

In this paper, we generalize the result on the existence of social welfare equilibra for $N$-players and discuss the impact in the game solutions when transplant information quality is introduced, changing the players' utilities. Furthermore, the game theory model is analyzed through computational experiments on instances generated by leveraging data of the Canadian Kidney Paired Donation Program. These experiments highlight the importance of using the concept of Nash equilibrium, as well as, the need of further research to assist policy makers once measures on transplant quality are available.

Keywords

  • Game theory
  • Kidney exchange program
  • Non-cooperativem Nash Equilibria
  • Social Welfare
  • Maximum Matching
  • Graft survival

M. Carvalho, A. Lodi, J. P. Pedroso, Computing equilibria for integer programming games

European Journal of Operational Research, Volume 303, Issue 3, 1057-1070, .

﹀ Show more

Abstract

The recently-defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be cast in this way, hence anticipating IPG outcomes is of crucial value for policy makers. Nash equilibria have been widely accepted as the solution concept of a game. Thus, their computation provides a reasonable prediction of 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 a general algorithmic approach that is guaranteed to return a Nash equilibrium when the game is finite and to approximate an equilibrium when payoff functions are Lipschitz continuous. We also showcase how our methodology can be changed to determine other types of equilibria. The performance of our methods is analysed through computational experiments on knapsack, kidney exchange and a competitive lot-sizing games. To the best of our knowledge, this is the first time that equilibria computation methods for general IPGs have been designed and computationally tested.

Keywords

  • Nash equilibria
  • Correlated equilibria
  • Integer programming game
  • Algorithmic game theory

C. Perreault-Lafleur, M. Carvalho, G. Desaulniers, A stochastic integer programming approach to reserve staff scheduling with preferences

Working paper,.

﹀ Show more

Abstract

Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. We tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an unstudied operational problem from the transit industry. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees' days-off preferences into the model to examine how employee satisfaction may affect their own absence rates.

Keywords

  • Personnel scheduling
  • Stochastic programming
  • Integer programming
  • Employee preferences
  • Transit industry
  • Endogenous uncertainty

F. Bobbio, M. Carvalho, A. Lodi, Ignacio Rios, A. Torrico, Capacity Planning in Stable Matching: An Application to School Choice

Working paper,.

﹀ Show more

Abstract

In this work, we introduce the problem of jointly allocating a school capacity expansion (given a fixed budget) and finding the best allocation for the students in the expanded market. Given the computational complexity of the problem, we provide an integer quadratically-constrained programming formulation and study its linear reformulations. We also propose two heuristics: A greedy algorithm and an LP-based method. We empirically evaluate the performance of our approaches in a detailed computational study. We observe the practical superiority of the linearized model in comparison with its quadratic counterpart and we outline their computational limits. Finally, we use the Chilean school choice system data to empirically demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. In addition, depending on the decision-maker, our methodology can prioritize the assignment of previously unassigned students or improve the assignment of several students through improvement chains.

Keywords

  • Stable matching
  • Capacity planning
  • Hospital/resident problem
  • School choice
  • Integer programming

A. Mukherjee, M. Carvalho, G. Zaccour, Managing quality and pricing during a product recall: an analysis of pre-crisis, crisis and post-crisis regimes

European Journal of Operational Research, Accepted,.

﹀ Show more

Abstract

Product recalls are often consequences of quality failures. While such failures are related to a manufacturer's or supplier's design quality, the perceived quality of products may be severely damaged when a product harm crisis occurs. However, most often, such a crisis will not last forever, and a firm at fault eventually recovers. Considering an optimal control model, we investigate the optimal pricing decisions, advertising and quality efforts of a firm while it anticipates a product recall and a subsequent recovery. We show that the decisions and profits of the manufacturer vary widely with the stochastic parameters: crisis likelihood, recovery likelihood, crisis impact and recovery intensity. We illustrate that myopic firms are more severely affected by a product recall than farsighted firms when the impact of recall is high. However, it might not be so detrimental to take myopic decisions for low impact recalls. In the absence of recovery, a product recall can lead to bankruptcy. High initial perceived quality may not insulate a firm against bankruptcy.

Keywords

  • OR in Marketing
  • Optimal control theory
  • Product recall
  • Advertising and Pricing
  • Quality

M.V.C. Vieira, M. Carvalho, Lexicographic optimization for the multi-container loading problem with open dimensions for a shoe manufacturer

4OR, Accepted, .

﹀ Show more

Abstract

Motivated by a real-world application, we present a multi-container loading problem with 3-open dimensions. We formulate it as a biobjective mixed-integer nonlinear program with lexicographic objectives in order to reflect the decision maker's optimization priorities. The first objective is to minimize the number of containers, while the second objective is to minimize the volume of those containers. Besides showing the NP-hardness of this sequential optimization problem, we provide bounds for it which are used in the three proposed algorithms, as well as, on their evaluation when a certificate of optimality is not available. The first is an exact parametric-based approach to tackle the lexicographic optimization through the second objective of the problem. Nevertheless, given that the parametric programs correspond to large nonlinear mixed-integer optimizations, we present a heuristic that is entirely mathematical-programming based. The third algorithm enhances the solution quality of the heuristic. These algorithms are specifically tailored for the real-world application. The effectiveness and efficiency of the devised heuristics is demonstrated with numerical experiments.

Keywords

  • Packing
  • 3-open dimensions
  • Mixed-integer programming
  • Lexicographic optimization

J. Oliveira, M. Carvalho, D. M. Nogueira, M. Coimbra, The selection of an optimal segmentation region in physiological signals

International Transactions in Operational Research, Volume 30, Issue 1, 601-618, .

﹀ Show more

Abstract

Physiological signals are often corrupted by noisy sources. Usually, artificial intelligence algorithms analyze the whole signal, regardless of its varying quality. Instead, experienced cardiologists search for a high-quality signal segment, where more accurate conclusions can be draw. We propose a methodology that simultaneously selects the optimal processing region of a physiological signal and determines its decoding into a state sequence of physiologically meaningful events. Our approach comprises two phases. First, the training of a neural network that then enables the estimation of the state probability distribution of a signal sample. Second, the use of the neural network output within an integer program. The latter models the problem of finding a time window by maximizing a likelihood function defined by the user. Our method was tested and validated in two types of signals, the phonocardiogram and the electrocardiogram. In phonocardiogram and electrocardiogram segmentation tasks, the system's sensitivity increased on average from 95.1% to 97.5% and from 78.9% to 83.8%, respectively, when compared to standard approaches found in the literature.

Keywords

  • Physiological signals
  • Deep neural networks
  • Integer programming
  • Optimal region selection

A. Nabli, M. Carvalho, P. Hosteins, Complexity of the Multilevel Critical Node Problem

Journal of Computer and System Sciences, Volume 127, 122-145, .

﹀ Show more

Abstract

In this work, we analyze a sequential game played in a graph called the Multilevel Critical Node problem (MCN). A defender and an attacker are the players of this game. The defender starts by preventively interdicting vertices (vaccination) from being attacked. Then, the attacker infects a subset of non-vaccinated vertices and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected and directed graphs, we clarify how the theoretical tractability or intractability of those problems vary. Our findings contribute with new NP-complete, Σp2-complete and Σp3-complete problems.

Keywords

  • Trilevel programming
  • Interdiction problems
  • Defender-attacker-defender
  • Polynomial Hierarchy
  • Critical node problems

W. St-Arnaud, M. Carvalho, G. Farnadi, Adaptation, Comparison and Practical Implementation of Fairness Schemes in Kidney Exchange Programs

Working paper,.

﹀ Show more

Abstract

The privileged treatment for patients suffering from end-stage renal disease is transplantation. In Kidney Exchange Programs (KEPs), each participating patient is registered together with an incompatible donor. Then, KEPs maximize overall patient benefit through donor exchanges. Compatibility requirements can severely restrict these programs, with certain patients waiting long to be selected for an exchange. Thus, the policy governing the selection of exchanges requires a careful balance between fairness in terms of individual access to transplantation and utilitarian criteria (e.g., total number of transplants). In this work, we review several fairness schemes, interpret them in the context of KEPs and describe their weaknesses. To overcome those drawbacks, we propose a novel scheme based on the Nash Social Welfare Program that simultaneously optimizes the fairness and the utilitarian objectives. Because the application of fairness schemes and a utilitarian objective implies solving conic programs of exponential size, we design a decomposition methodology to efficiently run them on KEP instances. Finally, we make an extensive comparison of the different schemes and validate the scalability of our methodology for benchmark instances from the literature.

Keywords

  • Kidney exchange programs
  • Fairness
  • Nash social welfare program
  • Conic programming
  • Integer programming

S. Lamontagne, M. Carvalho, E. Frejinger, B. Gendron, M. F. Anjos, R. Atallah, Optimising Electric Vehicle Charging Station Placement using Advanced Discrete Choice Models

Working paper,.

﹀ Show more

Abstract

We present a new model for finding the optimal placement of electric vehicle charging stations across a multi-period time frame so as to maximise 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

F. Bobbio, M. Carvalho, A. Lodi, A. Torrico, Capacity Variation in the Many-to-one Stable Matching

Working paper, .

﹀ Show more

Abstract

The many-to-one stable matching problem provides the fundamental abstraction of several real-world matching markets such as school choice and hospital-resident allocation. The agents on both sides are often referred to as residents and hospitals. The classical setup assumes that the agents rank the opposite side and that the capacities of the hospitals are fixed. It is known that increasing the capacity of a single hospital improves the residents' final allocation. On the other hand, reducing the capacity of a single hospital deteriorates the residents' allocation. In this work, we study the computational complexity of finding the optimal variation of hospitals' capacities that leads to the best outcome for the residents, subject to stability and a capacity variation constraint. First, we show that the decision problem of finding the optimal capacity expansion is NP-complete and the corresponding optimization problem is inapproximable within a certain factor. This result holds under strict and complete preferences, and even if we allocate extra capacities to disjoint sets of hospitals. Second, we obtain analogous computational complexity results for the problem of capacity reduction. Finally, we study the variants of these problems when the goal is to maximize the size of the final matching under incomplete preference lists.

Keywords

  • Many-to-one stable matching
  • Hospital-resident proble
  • Capacity expansion
  • Capacity reduction
  • Computational complexity

Q. M. Bui, B. Gendron, M. Carvalho, A Catalog of Formulations for the Network Pricing Problem

INFORMS Journal on Computing, Accepted, .

﹀ Show more

Abstract

We study the network pricing problem where the leader maximizes their revenue by determining the optimal amounts of tolls to charge on a set of arcs, under the assumption that the followers will react rationally and choose the shortest paths to travel. Many distinct single-level reformulations of this bilevel optimization program have been proposed, however, their relationship has not been established. In this paper, we aim to build a connection between those reformulations and explore the combination of the path representation with various modeling options, allowing us to generate 12 different reformulations of the problem. Moreover, we propose a new path enumeration scheme, path-based preprocessing, and hybrid framework to further improve performance and robustness when solving the final model. We provide numerical results, comparing all the derived reformulations and confirming the efficiency of the novel dimensionality reduction procedures.

Keywords

  • Networks
  • Pricing
  • Bilevel programming
  • Multi-commodity transportation

A. Mukherjee, M. Carvalho, Dynamic decision making in a mixed market under cooperation: towards sustainability

International Journal of Production Economics, Volume 241,.

﹀ Show more

Abstract

Sustainability goals are becoming a priority in many societies. An important element in this context is the success of environmentally friendly products. Hence, we consider a manufacturer-retailer vertical supply chain model, managing a green product and its conventional counterpart, designated by brown product. We analyze three kinds of dynamic market scenarios: no market leadership, the manufacturer as the market leader, and the retailer as the market leader. Under each scenario, we determine the equilibrium decisions for pricing and greening investments as well as their dependence on a cost-sharing proportion agreement between the firms. We find that generally both firms have similar pricing trends, where the gap between the two product prices increases with the share of cost carried by the retailer. Moreover, we analyze how these decisions affect the consumer surplus and the performance of the firms. The absence of a market leader leads to higher consumer surplus with the manufacturer investing more in greening. However, cost-sharing may fail if there is no market leader. The retailer has incentive to share the highest proportion of greening costs when it is the leader. When the manufacturer is the leader, the retailer may have incentive to change the cost-sharing proportion over time. Finally, we compare the greening level and learning trajectories for the different scenarios. We provide essential managerial insights on how decisions should be operated, enabling green products to successfully gain a stable market share.

Keywords

  • Differential game theory
  • Mixed market
  • Coordination
  • Green supply chain

G. Dragotto, S. Sankaranarayanan, M. Carvalho, A. Lodi ZERO: Playing Mathematical Programming Games

Working paper, .

﹀ Show more

Abstract

We present ZERO, a modular and extensible C++ library interfacing Mathematical Programming and Game Theory. ZERO provides a comprehensive toolkit of modeling interfaces for designing games, helper tools, and algorithms to find Nash equilibria. Specifically, the software supports Reciprocally Bilinear Games (RBGs), i.e., simultaneous non-cooperative games where each player solves a mathematical program with a linear objective in the player's variable and bilinear in its opponents' variables. This class of games generalizes to a multi-agent setting the classical problems of Operations Research. ZERO provides extended support for integer non-convexities, linear bilevel problems, and linear equilibrium problems with equilibrium constraints. Its modular structure provides users with all the elementary ingredients to devise new models and algorithms for RBGs, aiming to boost methodological advancement in the field. We provide an overview of the software's key components and showcase a Knapsack Game, i.e., each player solves a binary knapsack problem. Code, documentation and examples are available at www.getzero.one .

Keywords

  • Nash Equilibria
  • Reciprocally Bilinear Games
  • Mixed Integer Programming
  • Software

M. Carvalho, G. Dragotto, A. Lodi, S. Sankaranarayanan, The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations

Working paper, .

﹀ Show more

Abstract

The concept of Nash equilibrium enlightens the structure of rational behavior in multi-agent settings. However, the concept is as helpful as one may compute it efficiently. We introduce the Cut-and-Play, an algorithm to compute Nash equilibria for non-cooperative simultaneous games where each player's objective is linear in their variables and bilinear in the other players' variables. Using the rich theory of integer programming, we alternate between constructing (i.) increasingly tighter outer approximations of the convex hull of each player's feasible set -- by using branching and cutting plane methods -- and (ii.) increasingly better inner approximations of these hulls -- by finding extreme points and rays of the convex hulls. In particular, we prove the correctness of our algorithm when these convex hulls are polyhedra. Our algorithm allows us to leverage the mixed integer programming technology to compute equilibria for a large class of games. Further, we integrate existing cutting plane families inside the algorithm, significantly speeding up equilibria computation. We showcase a set of extensive computational results for Integer Programming Games and simultaneous games among bilevel leaders. In both cases, our framework outperforms the state-of-the-art in computing time and solution quality.

Keywords

  • Nash Equilibria
  • Mixed Integer Programming
  • Integer Programming Games
  • Nash games Among Stackelberg Players
  • Separation Oracle

F. Bobbio, M. Carvalho, A. Lodi, A. Torrico, Capacity Expansion in the College Admission Problem

Working paper,.

﹀ Show more

Abstract

The college admission problem plays a fundamental role in several real-world allocation mechanisms such as school choice and supply chain stability. The classical framework assumes that the capacity of each college is known and fixed in advance. However, increasing the quota of even a single college would improve the overall cost of the students. In this work, we study the problem of finding the college capacity expansion that achieves the best cost of the students, subject to a cardinality constraint. First, we show that this problem is NP-hard to solve, even under complete and strict preference lists. We provide an integer quadratically constrained programming formulation and study its linear reformulation. We also propose two natural heuristics: A greedy algorithm and an LP-based method. We empirically evaluate the performance of our approaches in a detailed computational study. We observe the practical superiority of the linearized model in comparison with its quadratic counterpart and we outline their computational limits. In terms of solution quality, we note that the allocation of a few extra spots can significantly impact the overall student satisfaction.

Keywords

  • College admission
  • Stable matching
  • Capacity expansion
  • Integer programming

M. Carvalho, X. Klimentova, K. Glorie, A. Viana, M. Constantino, Robust Models for the Kidney Exchange Problem

INFORMS Journal on Computing, Volume 33, Issue 3, 861-881, .

﹀ Show more

Abstract

Kidney exchange programs aim at matching end-stage renal disease patients who have a willing but incompatible kidney donor with another donor. The programs comprise a pool of such incompatible patient-donor pairs and, whenever a donor from one pair is compatible with the patient of another pair, and vice versa, the pairs may be matched and exchange kidneys. This is typically a two-step process in which, first, a set of pairs is matched based on preliminary compatibility tests and, second, the matched pairs are notified and more accurate compatibility tests are performed to verify that actual transplantation can take place. These additional tests may reveal incompatibilities not previously detected. When that happens, the planned exchange will not proceed. Furthermore, pairs may drop out before the transplant, and thus the planned exchange is canceled. In this paper, we study the case in which a new set of pairs may be matched if incompatibilities are discovered or a pair withdraws from the program. The new set should be as close as possible to the initial set in order to minimize the material and emotional costs of the changes. Various recourse policies that determine the admissible second-stage actions are investigated. For each recourse policy, we propose a novel adjustable robust integer programming model. We also propose solution approaches to solve this model exactly. The approaches are validated through thorough computational experiments.

Keywords

  • Kidney Exchange
  • Robust Optimization
  • Integer Programming

A. Torrico, M. Carvalho, A. Lodi, Multi-agent Assortment Optimization in Sequential Matching Markets

Working paper, . Short talk (DOTs)

﹀ Show more

Abstract

Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, labor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the tradeoff between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences.

In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected revenue of the matching. Given the computational complexity of the problem, we show several constant factor guarantees for the general model that, in particular, significantly improve the approximation factors previously obtained. Furthermore, we obtain the first constant approximation guarantees when the problem is subject to cardinality constraints. Our approach relies on submodular optimization techniques and appropriate linear programming relaxations. Finally, we provide a computational study on different settings that supports our technical results.

Keywords

  • Matching Platforms
  • Two-sided Markets
  • Assortment Optimization
  • Discrete Choice Models

G. Farnadi, W. St-Arnaud, B. Babaki, M. Carvalho, Individual Fairness in Kidney Exchange Programs

Proceedings of the AAAI Conference on Artificial Intelligence, Vol 35, No 13, 11496-11505, Technical Track on Philosophy and Ethics of AI, . (21% acceptance rate) Paper version with appendix

﹀ Show more

Abstract

Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a donor 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.

M. J. Santos, E. Curcio, P. Amorim, M. Carvalho, A. Marques, A bilevel approach for the collaborative transportation planning problem

International Journal of Production Economics, .

﹀ Show more

Abstract

The integration of the outbound and the inbound logistics of a company leads to a large transportation network, allowing to detect backhauling opportunities to increase the efficiency of the transportation. In collaborative networks, backhauling is used to find profitable services in the return trip to the depot and to reduce empty running of vehicles. This work investigates the vertical collaboration between a shipper and a carrier for the planning of integrated inbound and outbound transportation. Based on the hierarchical nature of the relation between the shipper and the carrier and their different goals, the problem is formulated as a bilevel Vehicle Routing Problem with Selective Backhauls (VRPSB). At the upper level, the shipper decides the minimum cost delivery routes and the set of incentives offered to the carrier to perform integrated routes. At the lower level, the carrier decides which incentives are accepted and on which routes the backhaul customers are visited. We devise a mathematical programming formulation for the bilevel VRPSB, where the routing and the pricing problems are optimized simultaneously, and propose an equivalent reformulation to reduce the problem to a single-level VRPSB. The impact of collaboration is evaluated against non-collaborative approaches and two different side payment schemes. The results suggest that our bilevel approach leads to solutions with higher synergy values than the approaches with side payments.

Keywords

  • Bilevel optimization
  • Vertical collaboration
  • Vehicle routing problem with selective backhauls

A. Baggio, M. Carvalho, A. Lodi, A. Tramontani, Multilevel Approaches for the Critical Node Problem

Operations Research, Vol 69, No 2, 486-508, .

﹀ Show more

Abstract

In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious 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-Attacker-Defender, 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.

Keywords

  • Multilevel Programming
  • Critical Node Problem
  • Firefighter Problem
  • Mixed-Integer Programming
  • Defender-Attacker-Defender

A. Nabli, M. Carvalho, Curriculum learning for multilevel budgeted combinatorial problems

NeurIPS 2020, . (20% acceptance rate)

﹀ Show more

Abstract

Learning heuristics for combinatorial optimization problems through graph neural networks have recently shown promising results on some classic NP-hard problems. These are single-level optimization problems with only one player. Multilevel combinatorial optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to B, then solving instances with budget B+1 can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to 100 nodes and a 185× speedup on average compared to the quickest exact solver known for the Multilevel Critical Node problem, a max-min-max trilevel problem that has been shown to be at least Σp2-hard.

Keywords

  • Trilevel programming
  • Graph games
  • Defender-attacker-defender
  • Reinforcement Learning
  • Combinatorial optimization

M. ElAraby, G. Wolf, M. Carvalho, Identifying Efficient Sub-networks using Mixed Integer Programming

12th OPT Workshop on Optimization for Machine Learning, NeurIPS 2020 workshop,

﹀ Show more

Abstract

We introduce a novel approach to optimize the architecture of deep neural networks by identifying critical neurons and removing non-critical ones. The proposed approach utilizes a mixed integer programming (MIP) formulation of neural models which includes a continuous importance score computed for each neuron in the network. The optimization in MIP solver minimizes the number of critical neurons (i.e., with high importance score) that need to be kept for maintaining the overall accuracy of the model. Further, the proposed formulation generalizes the recently considered lottery ticket optimization by identifying multiple "lucky" sub-networks resulting in optimized architecture that not only perform well on a single dataset, but also generalize across multiple ones upon retraining of network weights. Finally, the proposed framework provides significant improvement in scalability of automatic sparsification of deep network architectures compared to previous attempts. We validate the performance and generalizability of our approach on MNIST, Fashion-MNIST, and CIFAR-10 datasets, using three different neural networks: LeNet 5 and two ReLU fully connected models.

Keywords

  • Mixed Integer Programming
  • Neural Networks
  • Critical Neuron

A. Mukherjee, M. Carvalho, Pricing and Quality Investments in a Mixed Brown-Green Product Market

In: Lalla-Ruiz E., Mes M., Voß S. (eds) Computational Logistics. ICCL 2020. Lecture Notes in Computer Science, vol 12433, 715-732. Springer, Cham. .

﹀ Show more

Abstract

Sustainable Supply Chain Management (SSCM) has assumed a position of prominence for academics and industry over the last two decades. The sustainability literature shows that typically manufacturers aim to optimize their pricing and greening level decisions in a mixed (green and brown) consumer market. In this work, we capture a manufacturer’s classic dilemma on the pricing of green and brown products, and greening investments, while subject to budget constraint. We compute and analyze the variations of optimal decisions over time. Our findings underscore the importance of investing in greening technologies and learning for the survival of green products. Furthermore, we show that a manufacturer’s optimal pricing strategy is to enter the market with a lower price for the green product and to increase it over time, eventually, surpassing the price for the brown product. Our analysis reveals that the greening level attraction can nullify the effect of a high price on the green product, resulting in higher green demand than brown. Higher green product demand is a win-win situation for both the manufacturer and the environment.

Keywords

  • Greem products
  • Pricing
  • Greening level
  • Learning
  • Sustainability
  • Optimal control

M. Carvalho, G. Dragotto, F. Feijoo, A. Lodi, S. Sankaranarayanan, When Nash Meets Stackelberg

Working paper, , Short video(MIP), DOTs Seminar.

﹀ Show more

Abstract

We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is Σp2-hard to decide if the game has a mixed-strategy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a finite time algorithm with a running time bounded by O(n^2^2) which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders' feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.

Keywords

  • Nash Equilibria
  • Stackelberge Games
  • Algorithmic Game Theory
  • Computational Complexity.

M. ElAraby, G. Wolf, M. Carvalho, Identifying Critical Neurons in ANN Architectures using Mixed Integer Programming

Working paper,

﹀ Show more

Abstract

We introduce a novel approach to optimize the architecture of deep neural networks by identifying critical neurons and removing non-critical ones. The proposed approach utilizes a mixed integer programming (MIP) formulation of neural models which includes a continuous importance score computed for each neuron in the network. The optimization in MIP solver minimizes the number of critical neurons (i.e., with high importance score) that need to be kept for maintaining the overall accuracy of the model. Further, the proposed formulation generalizes the recently considered lottery ticket optimization by identifying multiple "lucky" sub-networks resulting in optimized architecture that not only perform well on a single dataset, but also generalize across multiple ones upon retraining of network weights. Finally, the proposed framework provides significant improvement in scalability of automatic sparsification of deep network architectures compared to previous attempts. We validate the performance and generalizability of our approach on MNIST, Fashion-MNIST, and CIFAR-10 datasets, using three different neural networks: LeNet 5 and two ReLU fully connected models.

Keywords

  • Mixed Integer Programming
  • Neural Networks
  • Critical Neuron

G. Farnadi, B. Babaki, M. Carvalho, Enhancing Fairness in Kidney Exchange Program by Ranking Solutions

Fair ML for Health, NeurIPS 2019 Workshop,

﹀ Show more

Abstract

Algorithmic decision making is being used with increasing frequency in domains that affect peoples’ lives. In the health-care domain, kidney exchange programs are a notable example of such applications. These programs aim to match incompatible patient-donor pairs and thereby allow some of them to receive a kidney transplant. Since it is often impossible to have everyone receive a transplant, usually a solution that maximizes the overall benefit of patients is selected. When the objective is to maximize the number of transplants, there can be several optimal solutions. Since the way that one of these solutions is selected has a major effect on the lives of the patients who are declined a transplant, special care must be taken to ensure fairness in this process.

We propose a selection method based on enumeration of all optimal solutions. We formulate this enumeration task as a constraint satisfaction problem. We also investigate the differences between the optimal solutions and introduce ranking methods to select a solution that satisfies certain fairness criteria. Preliminary experiments on synthetic graphs show that some patient groups having certain physiological traits are underrepresented in the solutions. The experiments also suggest that our fairness criteria can increase the chances of such patients for receiving a transplant.

M. Carvalho, C. Telha, M. Van Vyve, J. P. Pedroso, Competitive uncapacitated lot-sizing game

International Journal of Production Economics, Volume 204, 148-159, .

﹀ Show more

Abstract

We study the strategical behavior of firms facing a lot-sizing problem with Cournot competition. Each player is a firm with her own production facility, modeled as an uncapacitated lot-sizing problem ({\ie}, production incurs set-up and variable costs and inventories are allowed). A Cournot competition is played in each time period (market) with each player deciding the quantity of product to place on it. The market price of that product in each time period depends on the total quantity placed in the market.

We show that this is a potential game with possibly multiple pure Nash equilibria. We then investigate the plausibility of these equilibria to predict the game outcome by evaluating the difficulty of computing them.
If the game has a single period, we prove that an equilibrium can be found in polynomial time, but it is weakly NP-hard to find an optimal pure Nash equilibrium (with respect to a given equilibrium refinement). If the game has no variable production and inventory costs, we prove that a pure Nash equilibrium can be computed in polynomial time.

Keywords

  • Cournot Competition
  • Lot-Sizing Problem
  • Nash equilibria
  • Potential Game

M. Carvalho, X. Klimentova, A. Viana Observability of power systems with optimal PMU placement

Computers & Operations Research, Volume 96, 330-349, .

﹀ Show more

Keywords

  • Network observability
  • PMU
  • Combinatorial optimization
  • Bilevel programming
  • Cutting plane

M. Carvalho, A. Lodi, P. Marcotte A polynomial algorithm for a continuous bilevel knapsack problem

Operations Research Letters, Volume 46, Issue 2, 185-188, .

﹀ Show more

Keywords

  • Bilevel programming
  • Continuous knapsack problem
  • Polynomial time

M. Carvalho, A. Lodi, J. P. Pedroso Existence of Nash equilibria on integer programming games

In: Vaz A., Almeida J., Oliveira J., Pinto A. (eds) Operational Research. APDIO 2017. Springer Proceedings in Mathematics & Statistics, Volume 223, 11-23, . See complementary note

﹀ Show more

Abstract

We aim to investigate a new class of games, where each player’s set of strategies is a union of polyhedra. These are called integer programming games. Examples suitable to be modeled by an integer programming game are described motivating our work. We prove that it is a \Sigma_^2-complete problem to decide the existence of Nash equilibria and we provide sufficient conditions for an equilibrium to exist.

Keywords

  • Integer programming games
  • Nash equilibria
  • Computational complexity

M. Carvalho, A. Lodi, J. P. Pedroso, A. Viana Nash Equilibria in the Two-Player Kidney Exchange Game

Mathematical Programming, Volume 161, Issue 1–2, 389–417, .

﹀ Show more

Abstract

Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets.

We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger Bilevel knapsack with interdiction constraints

INFORMS Journal on Computing, Volume 28, Issue 2, 319-333, .

﹀ Show more

Abstract

We consider a Bilevel Integer Programming model that extends the classic 0--1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader's decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants.

Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.

M. Carvalho, J. P. Pedroso Note on the Cournot and Stackelberg Competitions: is it worth to be the last playing?

Technical Report DCC-2015-01, DCC-FC & INESC, Universidade do Porto.

Abstract

In this brief note, a competition on a new product produced by two firms sharing a market is analyzed both from a Cournot and Stackelberg point of view. In contrast with classical models, setup costs are considered in the firms’ production costs, leading to ambiguities in their best response strategies. Our aim is to establish the different equilibria strategies that may arise from these two competition versions. Moreover, our goal is to open the discussion of whether it might be worth for a player to wait for the opponents to move, forcing a Stackelberg equilibrium to be played.

M. Carvalho, A. Lodi, J. P. Pedroso, A. Viana Two-Player Kidney Exchange Game

Poster at IPCO .

﹀ Show more

Abstract

Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger A Study on the Computational Complexity of the Bilevel Knapsack Problem

SIAM Journal on Optimization, Volume 24, Issue 2, 823-838, .

﹀ Show more

Abstract

We analyze the computational complexity of three fundamental variants of the bilevel knapsack problem. All three variants are shown to be complete for the second level of the polynomial hierarchy. We also discuss the somewhat easier situation where the weight and profit coefficients in the knapsack problem are encoded in unary: two of the considered bilevel variants become solvable in polynomial time, whereas the third becomes NP-complete. Furthermore, we design a polynomial time approximation scheme for this third variant, whereas the other two variants cannot be approximated in polynomial time within any constant factor (assuming P≠NP).

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger A Complexity and Approximability Study of the Bilevel Knapsack Problem

In M. Goemans, J. Correa, Eds., Integer Programming and Combinatorial Optimization - IPCO 2013, Lecture Notes in Computer Science 7801, Springer-Verlag, Berlin Heidelberg, , 98-109.

17th Aussois Combinatorial Optimization Workshop 2013 - Bilevel Knapsack with interdiction constraints

Conference ALIO EURO 2011 - Nash Equilibria in Electricity Markets

Technical Report 2012 - Equilibria on the Day-Ahead Electricity Market

M. Carvalho, J.P. Pedroso, J. Saraiva Electricity Day-Ahead Markets: Computation of Nash Equilibria

Journal of Industrial and Management Optimization 11(3), , 985-998.

﹀ Show more

Abstract

In a restructured electricity sector, day-ahead markets can be modeled as a game where some players - the producers - submit their proposals. To analyze the companies' behavior we have used the concept of Nash equilibrium as a solution in these multi-agent interaction problems. In this paper, we present new and crucial adaptations of two well-known mechanisms, the adjustment process and the relaxation algorithm, in order to achieve the goal of computing Nash equilibria. The advantages of these approaches are highlighted and compared with those available in the literature.

Ph.D in Computer Science

M. Carvalho Computation of equilibria on integer programming games

Faculdade de Ciências da Universidade do Porto, .

﹀ Bibtex

Bibtex

@phdthesis{carvalhoPhD,
			author = "Margarida Carvalho",
			year ={2016},
			school = {Faculdade de Ci\^encias da Universidade do Porto},
			title = {Computation of equilibria on integer programming games}
			}
		

Master in Mathematical Engineering

M. Carvalho Nash Equilibria: a Case Study in the Energy Market.

Faculdade de Ciências da Universidade do Porto, .