期刊
INFORMS JOURNAL ON COMPUTING
卷 28, 期 2, 页码 319-333出版社
INFORMS
DOI: 10.1287/ijoc.2015.0676
关键词
knapsack problem; bilevel programming; min-max problem
资金
- COST Action [TD1207]
- Portuguese Foundation for Science and Technology [SFRH/BD/79201/2011]
- MIUR, Italy [PRIN2009]
- Fundação para a Ciência e a Tecnologia [SFRH/BD/79201/2011] Funding Source: FCT
We consider a bilevel integer programming model that extends the classic 0-1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader's decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants. Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据