期刊
DISCRETE OPTIMIZATION
卷 10, 期 1, 页码 1-10出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disopt.2012.09.001
关键词
Bilevel programming; Knapsack problem; Dynamic programming; Branch-and-bound
资金
- International Campus on Safety and Intermodality in Transportation
- Nord-Pas-de-Calais Region
- European Community
- Regional Delegation for Research and Technology
- Ministry of Higher Education and Research
- National Center for Scientific Research
- Portuguese Science and Technology Foundation [SFRH/BPD/64766/2009]
- Algorithmic Research Center of the University of Minho
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. (C) 2012 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据