554. A Bilevel Critical Node Detection Problem
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. | Ashwin Arulselvan
|
| University of Strathclyde |
Abstract
In this work, we formulate a bilevel critical node detection problem for a given threat level and a budget. A leader has a budget to immunize a subset of nodes. An attacker, with the knowledge of the leader’s choice, will remove any set of non-immunized nodes within their budget, which is the threat level. The leader seeks to maximise the pairwise connectivity of
the nodes for the worst case removal strategy of the attacker. We solve this problem using a high point relaxation within a branch-and-bound framework. We introduce some valid inequalities to strengthen the formulation and introduce a branching strategy to deal with the bilevel infeasibility. We test this procedure on two graph families with varying number
of nodes, edge densities and budgets and share our computational experience. We conclude with the note that the framework could be applied to any network interdiction problem, provided some properties are preserved.
Keywords
- Multi-level optimization
- Computational mathematical optimization
- Nonlinear mixed integer optimization
Status: accepted
Back to the list of papers