Abstract

This study addresses the bilevel network design problem (NDP) with congestion. The upper-level decision-maker (a network designer) selects a set of arcs to add to an existing transportation network, while the lower-level decision-makers (drivers) respond by choosing routes that minimize their individual travel times, resulting in user equilibrium. In this work, we propose two novel single-level reformulations: one based on strong duality and the other based on the value function of the lower-level problem. Unlike existing approaches in the literature, which are specialized for optimizing the total travel time of all drivers, our approach is flexible and can optimize other metrics related to individual travel times or fairness. We discuss the differences between the two reformulations, as well as their computational performance on academic test instances of the NDP. We then apply our methods to the EV charging station capacity expansion problem. We define a metric, the cost of sustainability, to measure the service quality experienced by individual EV drivers, and optimize the charging station locations to improve this metric. We present the results of experiments using the road network in Quebec, including public fast EV charging stations.

Abstract

We provide a comprehensive survey of Integer Programming Games (IPGs), focusing on both simultaneous games and bilevel programs. These games are characterized by integral constraints within the players' strategy sets. We start from the fundamental definitions of these games and various solution concepts associated with them, and derive the properties of the games and the solution concepts. For each of the two types of games - simultaneous and bilevel - we have one chapter dedicated to the analysis of the games and another chapter dedicated to the development and analyses of algorithms to solve them. The analyses chapters present results on the computational complexity of the general as well as various restricted versions of the game. These chapters also discuss the structural properties of the games and the equilibrium concepts associated with them. The algorithm chapters, in contrast, presents some of the state-of-the-art algorithms developed to solve these games, either exactly or approximately or fast under fixed-parameter assumptions. These chapters also contain proofs of correctness of these algorithms and assessment of their theoretical run times in the worst-case scenario.

Abstract

Kidney Exchange Programs (KEPs) typically maximize overall patient benefit through donor exchanges. This aggregation of benefits (utilitarian objective) calls into question potential individual patient disparities in terms of access to transplantation in KEPs. Moreover, 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 extend the space of policies by seeking a lottery over the set of exchange plans that contemplates the (ex-ante) probability of patients 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.

Abstract

Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel and multilevel optimization by studying its computational complexity. We show that deciding whether an optimistic linear bilevel problem is unbounded is strongly NP-complete, even without linking constraints. Furthermore, we extend the hardness result to the linear multilevel case, by showing that for each extra level added, the decision problem of checking unboundedness moves up a level in the polynomial hierarchy. Deciding unboundedness of a mixed-integer multilevel problem is shown to be one level higher in the polynomial complexity hierarchy than the decision problem for linear multilevel problem with the same number of levels. Finally, we introduce two algorithmic approaches to determine whether a linear bilevel problem is unbounded and, if so, return a certificate of unboundedness. This certificate consists of a direction of unboundedness and corresponding bilevel feasible point. We present a proof of concept of these algorithmic approaches on some relevant examples, and provide a brief computational comparison.

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.

Abstract

We define a framework to investigate and assess the impact of prompt and dynamic reactions to market competition in production planning problems. It depicts two firms that produce and sell substitutable products over a finite time horizon. Each firm optimizes its sales and production costs, and has sufficient market power to affect the sales of the other firm.

The framework can capture several production and market competition features. We model production plans using mixed-integer programs and market competition using sequential Stackelberg games. Under certain conditions, we can solve the models in our framework in polynomial-time.

We provide examples to illustrate how the framework can match the requirements of production planning and sales. Then, we perform a computational study to analyze a planning problem that features the possibility of technological investments to reduce the variable production costs. We draw insights on the value of our polynomial-time method to compute subgame perfect equilibria by comparing its optimal production plans against a static model, where firms fix the entire production plan at the beginning of the planning horizon, and a myopic model, where firms ignore the impact that current decisions will have in future periods.

Abstract

Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse aims to implement contingent priorities, i.e., priorities that depend on the current assignment, to prioritize students with siblings and match them together. We provide a series of guidelines and introduce two natural approaches to implement them: (i) absolute, whereby a prioritized student can displace any student without siblings assigned to the school, and (ii) partial, whereby prioritized students can only displace students that have a less favorable lottery than their priority provider. We study several properties of the corresponding mechanisms, including the existence of a stable assignment under contingent priorities, the complexity of deciding whether there exists one, and its incentive properties. Furthermore, we introduce a soft version of these priorities to guarantee existence, and we provide mathematical programming formulations to find such stable matching or certify that one does not exist. Finally, using data from the Chilean school choice system, we show that our framework can significantly increase the number of students assigned to their top preference and the number of siblings assigned together relative to current practice.

Abstract

The Fuel Refueling Location Problem (FRLP) is a stylized model for determining the optimal siting of refueling stations for vehicles with limited travel ranges, such as hydrogen fuel cell vehicles and electric vehicles. This problem becomes particularly relevant when the goal is to facilitate long-distance travel using these vehicles. A variant of the FRLP, known as the Deviation Fuel Refueling Location Problem, accounts for the possibility that drivers may deviate from their preferred routes to ensure sufficient fuel or charging to complete their trips. While solution techniques based on various mathematical programming formulations have been thoroughly explored for these problems, there is a lack of theoretical insights into the relationships and strengths of these formulations. In this work, we study formulations of these problems used in the literature and compare their strengths in terms of linear programming relaxations. Furthermore, we explore approaches to tighten the formulations.

Abstract

We propose an integrated approach combining a cooperative game model and a multi-objective optimization model to determine the quantities of forest resources to allocate to several mills. The new mechanism developed in this study is applied to a regional case study in the province of Quebec (Canada), where public-owned forest resources should be allocated by the government to multiple competing mills. Collaboration between mills is considered in the upstream supply chain (i.e., harvesting, road construction/upgrading, and transportation operations) as well as their individual sustainability performances (economic, environmental and social aspects) in the allocation process. Moreover, this approach highlights the conditions under which the allocation ensures the stability of the configuration of the coalitions through a coalitional stability analysis. The proposed approach attempts to capture collaboration benefits and mills’ individual performances in the allocation process, while promoting equity among them. The coalitions of the case study overlap and thus, the concept of coalition configuration value is used to measure the marginal contribution of each mill to the cost savings. In particular, a methodology is proposed for the estimation of this value based on real data. The results of this study demonstrate that the allocation honors the efforts made by mills, both individually and collectively. In addition, it stimulates them towards a sustainable resource management relationship.

Abstract

Fortification-interdiction games are tri-level adversarial games where two opponents act in succession to protect, disrupt and simply use an infrastructure for a specific purpose. Many such games have been formulated and tackled in the literature through specific algorithmic methods, however very few investigations exist on the completeness of such fortification problems in order to locate them rigorously in the polynomial hierarchy. We clarify the completeness status of several well-known fortification problems, such as the Tri-level Interdiction Knapsack Problem with unit fortification and attack weights, the Max-flow Interdiction Problem and Shortest Path Interdiction Problem with Fortification, the Multi-level Critical Node Problem with unit weights, as well as a well-studied electric grid defence planning problem. For all of these problems, we prove their completeness either for the Σp2 or the Σp3 class of the polynomial hierarchy. We also prove that the Multi-level Fortification-Interdiction Knapsack Problem with an arbitrary number of protection and interdiction rounds and unit fortification and attack weights is complete for any level of the polynomial hierarchy, therefore providing a useful basis for further attempts at proving the completeness of protection-interdiction games at any level of said hierarchy.

Abstract

Dynamic facility location problems aim at placing one or more valuable resources over a planning horizon to meet customer demand. Existing literature commonly assumes that customer demand quantities are defined independently for each time period. In many planning contexts, however, unmet demand carries over to future time periods. Unmet demand at some time periods may therefore affect decisions of subsequent time periods. This work studies a novel location problem, where the decision maker relocates a single temporary facility over time to capture cumulative customer demand. We propose two mixed-integer programming models for this problem, and show that one of them has a tighter continuous relaxation and allows the representation of more general customer demand behaviour. We characterize the computational complexity for this problem, and analyze which problem characteristics result in NP-hardness. We then propose an exact branch-and-Benders-cut method, and show how optimality cuts can be computed efficiently through an analytical procedure. Computational experiments show that our method is approximately 30 times faster than solving the tighter formulation directly. Our results also quantify the benefit of accounting for cumulative customer demand within the optimization framework, since the corresponding planning solutions perform much better than those obtained by ignoring cumulative demand or employing myopic heuristics.

Abstract

The maximum covering location problem (MCLP) is a key problem in facility location, with many applications and variants. One such variant is 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.

Abstract

With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed-integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

Abstract

Real-world decision-making problems often involve decision-dependent uncertainty, where the probability distribution of the random vector depends on the model decisions. Few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We propose a general method for solving a class of these programs based on random variable transformation, a technique widely employed in probability and statistics. The random variable transformation converts a stochastic program with endogenous uncertainty (original program) into an equivalent stochastic program with decision-independent uncertainty (transformed program), for which solution procedures are well-studied. Additionally, endogenous uncertainty usually leads to nonlinear nonconvex programs, which are theoretically intractable. Nonetheless, we show that, for some classical endogenous distributions, the proposed method yields mixed-integer linear or convex programs with exogenous uncertainty. We validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. While the original formulation of this problem is nonlinear nonconvex for most endogenous distributions, the proposed method transforms it into mixed-integer linear programs with exogenous uncertainty. We solve these transformed programs with the sample average approximation method. We highlight the superior performance of our approach compared to solving the original program in the case a mixed-integer linear formulation of this program exists.

Abstract

We propose a framework to compute approximate Nash equilibria in integer programming games with nonlinear payoffs, i.e., simultaneous and non-cooperative games where each player solves a parametrized mixed-integer nonlinear program. We prove that using absolute approximations of the players' objective functions and then computing its Nash equilibria is equivalent to computing approximate Nash equilibria where the approximation factor is doubled. In practice, we propose an algorithm to approximate the players' objective functions via piecewise linear approximations. Our numerical experiments on a cybersecurity investment game show the computational effectiveness of our approach.

Abstract

The network pricing problem (NPP) is a bilevel problem, where the leader optimizes its revenue by deciding on the prices of certain arcs in a graph, while expecting the followers (also known as the commodities) to choose a shortest path based on those prices. In this paper, we investigate the complexity of the NPP with respect to two parameters: the number of tolled arcs, and the number of commodities. We devise a simple algorithm showing that if the number of tolled arcs is fixed, then the problem can be solved in polynomial time with respect to the number of commodities. In contrast, even if there is only one commodity, once the number of tolled arcs is not fixed, the problem becomes NP-hard. We characterize this asymmetry in the complexity with a novel property named strong bilevel feasibility. Finally, we describe an algorithm to generate valid inequalities to the NPP based on this property, whose numerical results illustrate its potential for effectively solving the NPP with a high number of commodities.

Abstract

This article introduces a class of Nash games among Stackelberg players (NASPs), namely, a class of simultaneous non-cooperative games where the players solve sequential Stackelberg games. Specifically, each player solves a Stackelberg game where a leader optimizes a (parametrized) linear objective function subject to linear constraints while its followers solve convex quadratic problems subject to the standard optimistic assumption. Although we prove that deciding if a NASP instance admits a Nash equilibrium is generally a Σ^p₂-hard decision problem, we devise two exact and computationally-efficient algorithms to compute and select Nash equilibria or certify that no equilibrium exists. We employ NASPs to model the hierarchical interactions of international energy markets where climate-change aware regulators oversee the operations of profit-driven energy producers. By combining real-world data with our models, we find that Nash equilibria provide informative, and often counterintuitive, managerial insights for market regulators.

Abstract

A kidney exchange program, also called a kidney paired donation program, can be viewed as a repeated, dynamic trading and allocation mechanism. 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.

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.

Abstract

We introduce the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve nonconvex 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.

Abstract

In this tutorial, we present a computational overview on computing Nash equilibria in Integer Programming Games (IPGs), i.e., how to compute solutions for a class of non-cooperative and nonconvex games where each player solves a mixed-integer optimization problem. IPGs are a broad class of games extending the modeling power of mixed-integer optimization to multi-agent settings. This class of games includes, for instance, any finite game and any multi-agent extension of traditional combinatorial optimization problems. After providing some background motivation and context of applications, we systematically review and classify the state-of-the-art algorithms to compute Nash equilibria. We propose an essential taxonomy of the algorithmic ingredients needed to compute equilibria, and we describe the theoretical and practical challenges associated with equilibria computation. Finally, we quantitatively and qualitatively compare a sequential Stackelberg game with a simultaneous IPG to highlight the different properties of their solutions.

Abstract

In this work, we concentrate on the problem of finding a set of neurons in a trained neural network whose pruning leads to a marginal loss in accuracy. To this end, we introduce Optimizing ANN Architectures using Mixed-Integer Programming (OAMIP) to identify critical neurons and prune non-critical ones. The proposed OAMIP uses a Mixed-Integer Program (MIP) to assign importance scores to each neuron in deep neural network architectures. The impact of simultaneous neuron pruning on the main learning tasks guides the neurons' scores. By carefully devising the objective function of the MIP, we drive the solver to minimize the number of critical neurons (i.e., with high importance score) that maintain the overall accuracy of the trained neural network. Our formulation identifies optimized sub-network architectures that generalize across different datasets, a phenomenon known as lottery ticket optimization. This optimized architecture not only performs well on a single dataset but also generalizes across multiple ones upon retraining of network weights. Additionally, we present a scalable implementation of our pruning methodology by decoupling the importance scores across layers using auxiliary networks. Finally, we validate our approach experimentally, showing its ability to generalize on different datasets and architectures.

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 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 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. Our major contribution is a reformulation into a maximum covering model, which uses the pre-computed 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 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.

Abstract

The recent promotion of sustainable urban planning combined with a growing need for public interventions to improve well-being and health have led to an increased collective interest for green spaces in and around cities. In particular, parks have proven a wide range of benefits in urban areas. This also means inequities in park accessibility may contribute to health inequities. In this work, we showcase the application of classic tools from Operations Research to assist decision-makers to improve parks' accessibility, distribution and design. Given the context of public decision-making, we are particularly concerned with equity and environmental justice, and are focused on an advanced assessment of users' behavior through a spatial interaction model. We present a two-stage fair facility location and design model, which serves as a template model to assist public decision-makers at the city-level for the planning of urban green spaces. The first-stage of the optimization model is about the optimal city-budget allocation to neighborhoods based on a data exposing inequality attributes. The second-stage seeks the optimal location and design of parks for each neighborhood, and the objective consists of maximizing the total expected probability of individuals visiting parks. We show how to reformulate the latter as a mixed-integer linear program. We further introduce a clustering method to reduce the size of the problem and determine a close to optimal solution within reasonable time. The model is tested using the case study of the city of Montreal and comparative results are discussed in detail to justify the performance of the model.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 .

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.