A study on the computational complexity of the bilevel knapsack problem

DOI10.1137/130906593zbMATH Open1297.90134OpenAlexW2046432398MaRDI QIDQ3192105FDOQ3192105

Authors: Alberto Caprara, Margarida Carvalho, Andrea Lodi, Gerhard J. Woeginger 

Publication date: 26 September 2014

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/275b26fb-dcdb-47f1-abec-b06339952892

Recommendations

• A complexity and approximability study of the bilevel knapsack problem
• A dynamic programming algorithm for the bilevel Knapsack problem
• Bilevel programming with knapsack constraints
• Exact solution approach for a class of nonlinear bilevel knapsack problems
• Improved approximation algorithms for a bilevel knapsack problem

zbMATH Keywords

computational complexitybilevel programmingknapsack problempolynomial hierarchyapproximation schemeapproximability

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (26)

• Single machine adversarial bilevel scheduling problems
• Computational complexity characterization of protecting elections from bribery
• Algorithms and applications for a class of bilevel MILPs
• Complexity of the multilevel critical node problem
• An exact method for binary fortification games
• The stochastic bilevel selection problem
• Complexity of near-optimal robust versions of multilevel optimization problems
• On bilevel optimization with inexact follower
• On the Stackelberg knapsack game
• A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints
• The subset sum game revisited
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds
• A Stackelberg knapsack game with weight control
• The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
• The trouble with the second quantifier
• Computing equilibria for integer programming games
• A faster algorithm for the continuous bilevel knapsack problem
• A survey on mixed-integer programming techniques in bilevel optimization
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Observability of power systems with optimal PMU placement
• Mixed-integer bilevel representability
• A dynamic reformulation heuristic for generalized interdiction problems
• Bilevel optimization: theory, algorithms, applications and a bibliography
• Solution techniques for bi-level knapsack problems
• A complexity and approximability study of the bilevel knapsack problem

This page was built for publication: A study on the computational complexity of the bilevel knapsack problem

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