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

DOI10.1007/978-3-031-32726-1_31MaRDI QIDQ6086022zbMATH OpenOpenAlexFDO

Authors 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

bilevel programmingbranch and boundcombinatorial algorithmdynamic programminginterdictionknapsack problem

Mathematics Subject Classification ID

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

Recommendations

• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
• Bilevel knapsack with interdiction constraints
• A faster algorithm for the continuous bilevel knapsack problem
• A polynomial algorithm for a continuous bilevel knapsack problem

Cites work

• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• A class of algorithms for mixed-integer bilevel min-max optimization
• A dynamic reformulation heuristic for generalized interdiction problems
• A new general-purpose algorithm for mixed-integer bilevel linear programs
• A study on the computational complexity of the bilevel knapsack problem
• A survey of network interdiction models and algorithms
• A survey on mixed-integer programming techniques in bilevel optimization
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• An expanding-core algorithm for the exact 0-1 knapsack problem
• Benchmarking optimization software with performance profiles.
• Bilevel knapsack with interdiction constraints
• Bilevel optimization: theory, algorithms, applications and a bibliography
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Where are the hard knapsack problems?

Cited in

(8)

• Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
• A polynomial algorithm for a continuous bilevel knapsack problem
• A faster algorithm for the continuous bilevel knapsack problem
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
• On extensions of min-k-union
• A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints
• Interdiction of minimum spanning trees and other matroid bases

This page was built for publication: A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086022)