A dynamic programming algorithm for the bilevel knapsack problem

We propose an efficient dynamic programming algorithm for solving a bilevel program where the leader controls the capacity of a knapsack, and the follower solves the resulting knapsack problem. We propose new recursive rules and show how to solve the problem as a sequence of two standard knapsack problems. (C) 2009 Elsevier B.V. All rights reserved.