Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem

Submission Status:under review
  • Developing solution methods for discrete bilevel problems is known to be a challenging task - even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a Γ-robust approach, we present an extended formulation and a multi-follower formulation to model this type of problem. For both settings, we provide a generic branch-and-cut framework. Specifically, we investigate interdiction problems with a monotone Γ-robust follower and we derive problem-tailored cuts, which extend existing techniques that have been proposed for the deterministic case. For the Γ-robust knapsack interdiction problem, we computationally evaluate and compare the performance of the proposed algorithms for both modeling approaches.

Download full text files

Export metadata

Author:Yasmine Beck, Ivana Ljubic, Martin Schmidt
Document Type:Preprint
Date of Publication (online):2021/11/10
Release Date:2021/11/10
Tag:Bilevel optimization; Branch-and-Cut; Knapsack interdiction; Mixed-integer programming; Robust optimization
Page Number:39
Institutes:Universität Trier
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International