Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-19T14:47:54.462Z Has data issue: false hasContentIssue false
  • English
  • Français

Integer Programming Formulation of the Bilevel KnapsackProblem

Published online by Cambridge University Press:  26 August 2010

A. Taik ,
R. Mansi ,
S. Hanafi  and
L. Brotcorne
Get access

Abstract

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which thefeasible 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 thatthe integer program reformulation is equivalent to the BKP. Numerical results show theefficiency of our method compared with those obtained by the algorithm of Moore andBard

Keywords

Bilevel programmingKnapsack problemdynamic programmingbranch-and-bound
Type
Research Article
Information
Mathematical Modelling of Natural Phenomena , Volume 5 , Issue 7: JANO9 – The 9thInternational Conference on Numerical Analysis and Optimization , 2010 , pp. 116 - 121
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Brotcorne, L., Hanafi, S., Mansi, R.. A dynamic programming algorithm for the bilevel knapsack problem . Operations Research Letters, 37 (2009), No. 3, 215–218.CrossRefGoogle Scholar
Calamai, P., Vicente, L.. Generating linear and linear-quadratic Bilevel programming problems . SIAM Journal on Scientific and Statistical Computing, 14 (1993), 770–782.CrossRefGoogle Scholar
Colson, B., Marcotte, P., Savard, G.. Bilevel programming, a survey . 4OR, 3 (2005), 87–107. CrossRefGoogle Scholar
S. Dempe. Foundation of Bilevel programming. Kluwer academic publishers, 2002.
Dempe, S., Richter, K.. Bilevel programming with Knapsack constraints . Central European Newspaper of Operations Research, 8 (2000), 93–107.Google Scholar
Hansen, P., Jaumard, B., Savard, G.. New branch-and-bound rules for linear bilevel programming . SIAM Journal on Scientific and Statistical Computing, 13 (1992), 1194–1217.CrossRefGoogle Scholar
H. Kellerer, U. Pferschy, D. Pisinger. Knapsack problems. Springer-Verlag, 2004.
Moore, J.T., Bard, J.F.. The mixed integer linear Bilevel programming problem . Operations Research, 38 (1990), 911–921.CrossRefGoogle Scholar