One-level reformulation of the bi-level Knapsack problem using dynamic programming

Abstract : In this paper, we consider the Bilevel Knapsack Problem (BKP), which is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions for a parametric Knapsack Problem. We introduce a new reformulation of the BKP into a one-level integer programming problem using dynamic programming. We propose an algorithm that allows the BKP to be solved exactly in two steps. In the first step, a dynamic programming algorithm is used to compute the set of follower reactions to leader decisions. In the second step, an integer problem that is equivalent to the BKP is solved using a branch-and-bound algorithm. Numerical results are presented to show the performance of our method.
Type de document :
Article dans une revue
Discrete Optimization, Elsevier, 2013, 10 (1), pp.1-10. 〈10.1016/j.disopt.2012.09.001〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00759250
Contributeur : Luce Brotcorne <>
Soumis le : vendredi 30 novembre 2012 - 12:26:50
Dernière modification le : vendredi 7 décembre 2018 - 12:50:03

Lien texte intégral

Identifiants

Citation

Luce Brotcorne, Saïd Hanafi, Raïd Mansi. One-level reformulation of the bi-level Knapsack problem using dynamic programming. Discrete Optimization, Elsevier, 2013, 10 (1), pp.1-10. 〈10.1016/j.disopt.2012.09.001〉. 〈hal-00759250〉

Partager

Métriques

Consultations de la notice

284