Operations Research 2025
Abstract Submission

243. Parametric Linear Programming Interdiction

Invited abstract in session WC-4: Bilevel and Mixed-Integer Nonlinear Programming, stream Continuous and Global Optimization.

Wednesday, 13:30-15:00
Room: H6

Authors (first author is the speaker)

1. Simon Wirschem
Mathematics, RPTU Kaiserslautern
2. Alexey Bochkarev
Department of Mathematics, RPTU Kaiserslautern-Landau
3. Stefan Ruzika
Mathematik, Rheinland-Pfälzische Technische Universität Kaiserslautern

Abstract

We study the parametric linear programming interdiction problem, where an interdictor seeks to deteriorate the optimal objective value of a linear program using limited resources (budget).
Interdiction problems are well-suited for detecting weak spots and to measure a system's robustness against worst-case influences.
While most existing work on interdiction focuses on networks, we consider a more general setting where the follower solves an arbitrary linear program.
In our formulation, the leader's budget acts as a parameter, allowing us to examine how the impact of interdiction evolves as this budget varies.
This parametric perspective reflects a natural robustness analysis: any fixed budget represents an arbitrary threat level, whereas understanding the problem across a range of budgets offers deeper insight into the system’s vulnerability and stability.

We show that the nonparametric version of this can be reformulated as a bilinear program, a well-studied class in the literature and which is known to be NP-hard.
The computational complexity also carries over to our nonparametric sub-problem.
Besides discussing the structure, we propose an exact branch-and-bound procedure along with numerical results.
Our work enables the application of parametric worst-case analysis to the wide class of linear models, which holds potential applications in robustness, security, and adversarial optimization.

Keywords

Status: accepted

Back to the list of papers