A dynamic programming algorithm for the bilevel Knapsack problem

DOI10.1016/j.orl.2009.01.007zbMath1167.90622OpenAlexW2072408036MaRDI QIDQ833584

Luce Brotcorne, Raïd Mansi, Saïd Hanafi

Publication date: 14 August 2009

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

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

zbMATH Keywords

dynamic programmingbilevel programmingKnapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (24)

On exact solution approaches for bilevel quadratic 0-1 knapsack problem ⋮ The Subset Sum game ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A class of algorithms for mixed-integer bilevel min-max optimization ⋮ The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective ⋮ The stochastic bilevel continuous knapsack problem with uncertain follower's objective ⋮ SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs ⋮ Strategies in competing subset selection ⋮ Bilevel Integer Programs with Stochastic Right-Hand Sides ⋮ A faster algorithm for the continuous bilevel knapsack problem ⋮ Approximation algorithms for a bi-level knapsack problem ⋮ A polynomial algorithm for a continuous bilevel knapsack problem ⋮ Solution techniques for bi-level knapsack problems ⋮ On Bilevel Optimization with Inexact Follower ⋮ An exact algorithm for bilevel 0-1 knapsack problems ⋮ Competitive subset selection with two agents ⋮ Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function ⋮ Feature selection for classification models via bilevel optimization ⋮ Exact solution approach for a class of nonlinear bilevel knapsack problems ⋮ The bilevel knapsack problem with stochastic right-hand sides ⋮ On the Stackelberg knapsack game ⋮ The subset sum game revisited ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography ⋮ Improved approximation algorithms for a bilevel knapsack problem

Uses Software

• CPLEX
• Knapsack

Cites Work

• Bilevel programming: a survey
• Foundations of bilevel programming
• Weak via strong Stackelberg problem: New results
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Bilevel programming with knapsack constraints
• Unnamed Item
• Unnamed Item

This page was built for publication: A dynamic programming algorithm for the bilevel Knapsack problem