A heuristic approach to bilevel multidimensional knapsack problems based on a surrogate relaxation

Abstract

The Bilevel Multidimensional Knapsack Problem is a hierarchical optimization problem involving two agents whose actions are interrelated. The Bilevel Multidimensional Knapsack Problem is used to model a variety of problems in different areas from transportation management to the financial sector. In this paper, we describe a new heuristic method for the Bilevel Multidimensional Knapsack Problem. Our approach relies on an original surrogate relaxation. This relaxation is solved using dynamic programming. At the end of the paper, we report on computational experiments that illustrate the performance of our approach.