Geodesic
Integer Programming Formulation of the Bilevel Knapsack Problem
R. Mansi1 ; S. Hanafi1 ; L. Brotcorne1
1 LAMIH-SIADE, University of Valenciennes, France
Mathematical modelling of natural phenomena, Tome 5 (2010) no. 7 Supplement, pp. 116-121.

Voir la notice de l'article provenant de la source EDP Sciences

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that the integer program reformulation is equivalent to the BKP. Numerical results show the efficiency of our method compared with those obtained by the algorithm of Moore and Bard
DOI : 10.1051/mmnp/20105719

R. Mansi 1 ; S. Hanafi 1 ; L. Brotcorne 1

1 LAMIH-SIADE, University of Valenciennes, France 
@article{MMNP_2010_5_7_Supplement_a19,
     author = {R. Mansi and S. Hanafi and L. Brotcorne},
     title = {Integer {Programming} {Formulation} of the {Bilevel} {Knapsack} {Problem}},
     journal = {Mathematical modelling of natural phenomena},
     pages = {116--121},
     publisher = {mathdoc},
     volume = {5},
     number = {7 Supplement},
     year = {2010},
     doi = {10.1051/mmnp/20105719},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20105719/}
}
TY  - JOUR
AU  - R. Mansi
AU  - S. Hanafi
AU  - L. Brotcorne
TI  - Integer Programming Formulation of the Bilevel Knapsack Problem
JO  - Mathematical modelling of natural phenomena
PY  - 2010
SP  - 116
EP  - 121
VL  - 5
IS  - 7 Supplement
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20105719/
DO  - 10.1051/mmnp/20105719
LA  - en
ID  - MMNP_2010_5_7_Supplement_a19
ER  - 
%0 Journal Article
%A R. Mansi
%A S. Hanafi
%A L. Brotcorne
%T Integer Programming Formulation of the Bilevel Knapsack Problem
%J Mathematical modelling of natural phenomena
%D 2010
%P 116-121
%V 5
%N 7 Supplement
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20105719/
%R 10.1051/mmnp/20105719
%G en
%F MMNP_2010_5_7_Supplement_a19
R. Mansi; S. Hanafi; L. Brotcorne. Integer Programming Formulation of the Bilevel Knapsack Problem. Mathematical modelling of natural phenomena, Tome 5 (2010) no. 7 Supplement, pp. 116-121. doi : 10.1051/mmnp/20105719. http://geodesic.mathdoc.fr/articles/10.1051/mmnp/20105719/

[1] L. Brotcorne, S. Hanafi, R. Mansi A dynamic programming algorithm for the bilevel knapsack problem Operations Research Letters 2009 215 218

[2] P. Calamai, L. Vicente Generating linear and linear-quadratic Bilevel programming problems SIAM Journal on Scientific and Statistical Computing 1993 770 782

[3] B. Colson, P. Marcotte, G. Savard Bilevel programming, a survey 4OR 2005 87 107

[4] S. Dempe. Foundation of Bilevel programming. Kluwer academic publishers, 2002.

[5] S. Dempe, K. Richter Bilevel programming with Knapsack constraints Central European Newspaper of Operations Research 2000 93 107

[6] P. Hansen, B. Jaumard, G. Savard New branch-and-bound rules for linear bilevel programming SIAM Journal on Scientific and Statistical Computing 1992 1194 1217

[7] H. Kellerer, U. Pferschy, D. Pisinger. Knapsack problems. Springer-Verlag, 2004.

[8] J.T. Moore, J.F. Bard The mixed integer linear Bilevel programming problem Operations Research 1990 911 921

Cité par Sources :