A polynomial algorithm for a continuous bilevel knapsack problem

DOI10.1016/j.orl.2017.12.009OpenAlexW2783872100MaRDI QIDQ2417096

Andrea Lodi, Margarida Carvalho, Patrice Marcotte

Publication date: 11 June 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2017.12.009

zbMATH Keywords

polynomial timebilevel programmingcontinuous knapsack problem

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items

Complexity of the multilevel critical node problem ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective ⋮ A faster algorithm for the continuous bilevel knapsack problem ⋮ Exact solution approaches for a class of bilevel fractional programs ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ The subset sum game revisited

Cites Work

• Unnamed Item
• A dynamic programming algorithm for the bilevel Knapsack problem
• One-level reformulation of the bilevel Knapsack problem using dynamic programming
• Linear programming in \(O(n\times 3^{d^2})\) time
• Improved approximation algorithms for a bilevel knapsack problem
• Bilevel Knapsack with Interdiction Constraints
• Linear Programming in Linear Time When the Dimension Is Fixed
• An Algorithm for Large Zero-One Knapsack Problems
• Bilevel programming with knapsack constraints