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

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...

Full description

Bibliographic Details
Main Author: Mansi, Raid (author)
Other Authors: Alves, Cláudio (author), Carvalho, J. M. Valério de (author), Brotcorne, Luce (author), Hanafi, Said (author)
Format: conferencePaper
Language:eng
Published: 2011
Subjects:
Bilevel programming
Heuristics
Surrogate relaxation
Online Access:http://hdl.handle.net/1822/15449
Country:Portugal
Oai:oai:repositorium.sdum.uminho.pt:1822/15449
Description
Summary: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.

Similar Items