An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
From MaRDI portal
Publication:2196299
Abstract: We consider the Bilevel Knapsack with Interdiction Constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower's profits. The presence of two decision levels makes this problem very difficult to solve in practice: the current state-of-the-art algorithms can solve to optimality instances with 50-55 items at most. We derive effective lower bounds and present a new exact approach that exploits the structure of the induced follower's problem. The approach successfully solves all benchmark instances within one second in the worst case and larger instances with up to 500 items within 60 seconds.
Recommendations
- Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
- Bilevel knapsack with interdiction constraints
- On exact solution approaches for bilevel quadratic 0-1 knapsack problem
- An exact algorithm for bilevel 0-1 knapsack problems
- Exact solution approach for a class of nonlinear bilevel knapsack problems
Cites work
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Minimal Algorithm for the 0-1 Knapsack Problem
- A Stackelberg knapsack game with weight control
- A class of algorithms for mixed-integer bilevel min-max optimization
- A complexity and approximability study of the bilevel knapsack problem
- A dynamic reformulation heuristic for generalized interdiction problems
- A fast algorithm for strongly correlated knapsack problems
- A new exact approach for the 0-1 collapsing knapsack problem
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A polynomial algorithm for a continuous bilevel knapsack problem
- An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions
- An exact approach for the 0-1 knapsack problem with setups
- Approximation algorithms for a bi-level knapsack problem
- Bilevel knapsack with interdiction constraints
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- Enhanced exact algorithms for discrete bilevel linear problems
- Exact approaches for the knapsack problem with setups
- Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
- Improved approximation algorithms for a bilevel knapsack problem
- Improved dynamic programming and approximation results for the knapsack problem with setups
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- New exact approaches and approximation results for the penalized knapsack problem
- On the product knapsack problem
- On the use of intersection cuts for bilevel optimization
- One-level reformulation of the bilevel Knapsack problem using dynamic programming
- Pinpointing the complexity of the interval min-max regret knapsack problem
- Robust discrete optimization and its applications
- The Mixed Integer Linear Bilevel Programming Problem
- The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
- The polynomial hierarchy and a simple model for competitive analysis
Cited in
(18)- On exact solution approaches for bilevel quadratic 0-1 knapsack problem
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- Bilevel knapsack with interdiction constraints
- Complexity of the multilevel critical node problem
- An exact method for binary fortification games
- On the Stackelberg knapsack game
- Distributionally risk‐receptive and risk‐averse network interdiction problems with general ambiguity set
- Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
- A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
- Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds
- The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
- Exact solution approach for a class of nonlinear bilevel knapsack problems
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- A dynamic reformulation heuristic for generalized interdiction problems
- An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities
- Solution techniques for bi-level knapsack problems
This page was built for publication: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196299)
