An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
From MaRDI portal
Publication:2196299
DOI10.1007/S10107-020-01482-5zbMATH Open1450.90040arXiv1811.02822OpenAlexW3007634324MaRDI QIDQ2196299FDOQ2196299
Rosario Scatamacchia, F. Della Croce
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1811.02822
bilevel programmingexact approachbilevel knapsack with interdiction constraintsmin-max regret knapsack problem
Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- The polynomial hierarchy and a simple model for competitive analysis
- Title not available (Why is that?)
- Robust discrete optimization and its applications
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- A Minimal Algorithm for the 0-1 Knapsack Problem
- The Mixed Integer Linear Bilevel Programming Problem
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- A dynamic reformulation heuristic for generalized interdiction problems
- One-level reformulation of the bilevel Knapsack problem using dynamic programming
- A class of algorithms for mixed-integer bilevel min-max optimization
- An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions
- A Complexity and Approximability Study of the Bilevel Knapsack Problem
- Approximation algorithms for a bi-level knapsack problem
- A fast algorithm for strongly correlated knapsack problems
- Pinpointing the complexity of the interval min-max regret knapsack problem
- Enhanced exact algorithms for discrete bilevel linear problems
- An exact approach for the 0-1 knapsack problem with setups
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
- On the product knapsack problem
- A new exact approach for the 0-1 collapsing knapsack problem
- Improved dynamic programming and approximation results for the knapsack problem with setups
- Exact approaches for the knapsack problem with setups
- New exact approaches and approximation results for the penalized knapsack problem
- Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- Bilevel Knapsack with Interdiction Constraints
- The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
- On the use of intersection cuts for bilevel optimization
- Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
- A Stackelberg knapsack game with weight control
- Improved approximation algorithms for a bilevel knapsack problem
- A polynomial algorithm for a continuous bilevel knapsack problem
Cited In (13)
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- 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
- Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds
- Lower bounds and a new exact approach for the Bilevel Knapsack with Interdiction Constraints
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities
- Solution techniques for bi-level knapsack problems
Uses Software
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)
