A study on the computational complexity of the bilevel knapsack problem

DOI10.1137/130906593MaRDI QIDQ3192105zbMATHOpenAlexFDO

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

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)

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

Cited in

(26)

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