16. On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
Invited abstract in session TC-7: Mixed-Integer Bilevel Optimization, stream Bilevel and multilevel optimization.
Tuesday, 14:00-16:00Room: B100/5015
Authors (first author is the speaker)
| 1. | Sergei Ketkov
|
| Department of Business Administration, University of Zurich |
Abstract
In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision-maker (referred to as a leader) and the lower-level decision-maker (referred to as a follower) are induced by two distinct partition matroids with a common weighted ground set. Unlike classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent capacity constraints and engage in a zero-sum game. While the problem of finding a maximum weight independent set in a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is NP-hard even when the weights of ground elements are all binary. On a positive note, it is revealed that, if the number of capacity constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a greedy algorithm for the leader.
Keywords
- Multi-level optimization
- Complexity and efficiency of algorithms
- Nonlinear mixed integer optimization
Status: accepted
Back to the list of papers