A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints

DOI10.1007/978-3-031-32726-1_31zbMath1528.90232OpenAlexW4377200034MaRDI QIDQ6086022

Noah Weninger, Ricardo Fukasawa

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-32726-1_31

zbMATH Keywords

dynamic programmingbranch and boundknapsack problembilevel programmingcombinatorial algorithminterdiction

Mathematics Subject Classification ID

Nonlinear programming (90C30) Hierarchical games (including Stackelberg games) (91A65) Combinatorial optimization (90C27) Dynamic programming (90C39) Discrete location and assignment (90B80)

Cites Work

• A class of algorithms for mixed-integer bilevel min-max optimization
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• A dynamic reformulation heuristic for generalized interdiction problems
• Where are the hard knapsack problems?
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• A survey of network interdiction models and algorithms
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Bilevel Knapsack with Interdiction Constraints
• A Study on the Computational Complexity of the Bilevel Knapsack Problem
• A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
• Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Benchmarking optimization software with performance profiles.
• A survey on mixed-integer programming techniques in bilevel optimization