-
Competing for the most profitable tour: The orienteering interdiction game
Authors:
Eduardo Álvarez-Miranda,
Markus Sinnl,
Kübra Tanınmış
Abstract:
The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which…
▽ More
The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which a competitor (the leader) tries to minimize the total prize that the follower can collect within a feasible tour. To this end, the leader interdicts some of the nodes so that the follower cannot collect their prizes. The resulting interdiction game is formulated as a bilevel optimization problem, and a single-level reformulation is obtained based on interdiction cuts. A branch-and-cut algorithm with several enhancements, including the use of a solution pool, a cut pool and a heuristic method for the follower's problem, is proposed. In addition to this exact approach, a genetic algorithm is developed to obtain high-quality solutions in a short computing time. In a computational study based on instances from the literature for the orienteering problem, the usefulness of the proposed algorithmic components is assessed, and the branch-and-cut and genetic algorithms are compared in terms of solution time and quality.
△ Less
Submitted 3 July, 2024;
originally announced July 2024.
-
Benders decomposition algorithms for minimizing the spread of harmful contagions in networks
Authors:
Kübra Tanınmış,
Necati Aras,
Evren Güney,
Markus Sinnl
Abstract:
The COVID-19 pandemic has been a recent example for the spread of a harmful contagion in large populations. Moreover, the spread of harmful contagions is not only restricted to an infectious disease, but is also relevant to computer viruses and malware in computer networks. Furthermore, the spread of fake news and propaganda in online social networks is also of major concern. In this study, we int…
▽ More
The COVID-19 pandemic has been a recent example for the spread of a harmful contagion in large populations. Moreover, the spread of harmful contagions is not only restricted to an infectious disease, but is also relevant to computer viruses and malware in computer networks. Furthermore, the spread of fake news and propaganda in online social networks is also of major concern. In this study, we introduce the measure-based spread minimization problem (MBSMP), which can help policy makers in minimizing the spread of harmful contagions in large networks. We develop exact solution methods based on branch-and-Benders-cut algorithms that make use of the application of Benders decomposition method to two different mixed-integer programming formulations of the MBSMP: an arc-based formulation and a path-based formulation. We show that for both formulations the Benders optimality cuts can be generated using a combinatorial procedure rather than solving the dual subproblems using linear programming. Additional improvements such as using scenario-dependent extended seed sets, initial cuts, and a starting heuristic are also incorporated into our branch-and-Benders-cut algorithms. We investigate the contribution of various components of the solution algorithms to the performance on the basis of computational results obtained on a set of instances derived from existing ones in the literature.
△ Less
Submitted 25 April, 2024; v1 submitted 22 March, 2023;
originally announced March 2023.
-
On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
Authors:
Elisabeth Gaar,
Jon Lee,
Ivana Ljubić,
Markus Sinnl,
Kübra Tanınmış
Abstract:
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing re…
▽ More
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables.
We present an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our binary instances.
△ Less
Submitted 8 January, 2023; v1 submitted 11 July, 2022;
originally announced July 2022.
-
An Exact Method for Fortification Games
Authors:
Markus Leitner,
Ivana Ljubić,
Michele Monaci,
Markus Sinnl,
Kübra Tanınmış
Abstract:
A fortification game (FG) is a three-level, two-player Stackelberg game, also known as defender-attacker-defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while a…
▽ More
A fortification game (FG) is a three-level, two-player Stackelberg game, also known as defender-attacker-defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while at the innermost level the defender solves a recourse problem over the surviving or partially damaged assets. Fortification games have applications in various important areas, such as military operations, design of survivable networks, protection of facilities, or power grid protection. In this work, we present an exact solution algorithm for FGs, in which the recourse problems correspond to (possibly NP-hard) combinatorial optimization problems. The algorithm is based on a new generic mixed-integer linear programming reformulation in the natural space of fortification variables. Our new model makes use of fortification cuts that measure the contribution of a given fortification strategy to the objective function value. These cuts are generated on-the-fly by solving separation problems, which correspond to (modified) middle-level interdiction games. We design a branch-and-cut-based solution algorithm based on fortification cuts, their lifted versions, and other speed-up techniques. We present a computational study using the knapsack fortification game and the shortest path fortification game. For the latter one, we include a comparison with a state-of-the-art solution method from the literature. Our algorithm outperforms this method and allows us to solve previously unsolved instances to optimality.
△ Less
Submitted 9 February, 2022; v1 submitted 26 November, 2021;
originally announced November 2021.
-
SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs
Authors:
Elisabeth Gaar,
Jon Lee,
Ivana Ljubić,
Markus Sinnl,
Kübra Tanınmış
Abstract:
We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of d…
▽ More
We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.
△ Less
Submitted 8 March, 2022; v1 submitted 12 November, 2021;
originally announced November 2021.
-
A branch-and-cut algorithm for submodular interdiction games
Authors:
Kübra Tanınmış,
Markus Sinnl
Abstract:
Many relevant applications from diverse areas such as marketing, wildlife conservation, or defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective…
▽ More
Many relevant applications from diverse areas such as marketing, wildlife conservation, or defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective value achievable by the follower, who seeks to maximize a submodular set function over the uninterdicted items subject to knapsack constraints.
We propose an exact branch-and-cut algorithm for these kind of interdiction games. The algorithm is based on interdiction cuts which allow to capture the follower's objective function value for a given interdiction decision of the leader and exploit the submodularity of the objective function. We also present extensions and liftings of these cuts and discuss additional preprocessing procedures.
We test our solution framework on the weighted maximal covering interdiction game and the bipartite inference interdiction game. For both applications, the improved variants of our interdiction cut perform significantly better than its basic version. For the weighted maximal covering interdiction game for which a mixed-integer bilevel linear programming (MIBLP) formulation is available, we compare the results with those of a state-of-the-art MIBLP solver. While the MIBLP solver yields a minimum of 54% optimality gap within one hour, our best branch-and-cut setting solves all but 4 of 108 instances to optimality with a maximum of 3% gap among unsolved ones.
△ Less
Submitted 29 March, 2021;
originally announced March 2021.
-
Improved x-space Algorithm for Min-Max Bilevel Integer Programming with an Application to Misinformation Spread in Social Networks
Authors:
Kübra Tanınmış,
Necati Aras,
İ. Kuban Altınel
Abstract:
In this work we propose an improvement of the $x$-space algorithm developed for solving a class of min--max bilevel optimization problems (Tang Y., Richard J.P.P., Smith J.C. (2016), A class of algorithms for mixed-integer bilevel min--max optimization. Journal of Global Optimization, 66(2), 225--262). In this setting, the leader of the upper level problem aims at restricting the follower's decisi…
▽ More
In this work we propose an improvement of the $x$-space algorithm developed for solving a class of min--max bilevel optimization problems (Tang Y., Richard J.P.P., Smith J.C. (2016), A class of algorithms for mixed-integer bilevel min--max optimization. Journal of Global Optimization, 66(2), 225--262). In this setting, the leader of the upper level problem aims at restricting the follower's decisions by minimizing an objective function, which the follower intends to maximize in the lower level problem by making decisions still available to her. The $x$-space algorithm solves upper and lower bound problems consecutively until convergence, and requires the dualization of an approximation of the follower's problem in formulating the lower bound problem. We first reformulate the lower bound problem using the properties of an optimal solution to the original formulation, which makes the dualization step unnecessary. The reformulation makes possible the integration of a greedy covering heuristic into the solution scheme, which results in a considerable increase in the efficiency. The new algorithm referred to as the improved $x$-space algorithm is implemented and applied to a recent min--max bilevel optimization problem that arises in the context of reducing the misinformation spread in social networks. It is also assessed on the benchmark instances of two other bilevel problems: zero-one knapsack problem with interdiction and maximum clique problem with interdiction. Numerical results indicate that the performance of the new algorithm is superior to that of the original algorithm, and also compares favorably with a recent algorithm developed for mixed-integer bilevel linear programs.
△ Less
Submitted 10 May, 2021; v1 submitted 16 May, 2020;
originally announced May 2020.
