An Exact Algorithm for Bilevel 0-1 Knapsack Problems

Raid Mansi, Cláudio Alves, J. M. Valério de Carvalho and Saïd Hanafi

Mathematical Problems in Engineering, 2012, vol. 2012, 1-23

Abstract:

We propose a new exact method for solving bilevel 0-1 knapsack problems. A bilevel problem models a hierarchical decision process that involves two decision makers called the leader and the follower. In these processes, the leader takes his decision by considering explicitly the reaction of the follower. From an optimization standpoint, these are problems in which a subset of the variables must be the optimal solution of another (parametric) optimization problem. These problems have various applications in the field of transportation and revenue management, for example. Our approach relies on different components. We describe a polynomial time procedure to solve the linear relaxation of the bilevel 0-1 knapsack problem. Using the information provided by the solutions generated by this procedure, we compute a feasible solution (and hence a lower bound) for the problem. This bound is used together with an upper bound to reduce the size of the original problem. The optimal integer solution of the original problem is computed using dynamic programming. We report on computational experiments which are compared with the results achieved with other state-of-the-art approaches. The results attest the performance of our approach.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2012/504713.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2012/504713.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:504713

DOI: 10.1155/2012/504713

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().