2613. Game-theoretic relaxations in bilevel optimization
Invited abstract in session MB-17: Combinatorial bilevel optimization 2, stream Combinatorial Optimization.
Monday, 10:30-12:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Noah Weninger
|
| Combinatorics & Optimization, University of Waterloo | |
| 2. | Ricardo Fukasawa
|
| Combinatorics & Optimization, University of Waterloo |
Abstract
We introduce a framework for relaxing Stackelberg zero-sum games with perfect information, with a focus on those arising from discrete bilevel optimization. The framework consists of operators which transform games while maintaining an approximation or bound on the optimal objective value. This simplifies and generalizes our two previous works on knapsack and matroid interdiction. It also generalizes well-known techniques including the high point relaxation and the derivation of bounds by restricting/relaxing the lower level problem. To further motivate this approach, we apply it to matching interdiction, in which the objective is to interdict (i.e., remove) edges from a graph so that the maximum matching weight is minimized, subject to a knapsack constraint on the set of interdicted edges. We present a branch-and-bound algorithm for this problem which uses a new lower bound derived using our framework.
Keywords
- Algorithms
- Programming, Dynamic
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers