An exact approach for the bilevel knapsack problem with interdiction constraints and extensions

• 成果类型: Article
• 署名作者: Della Croce, Federico; Scatamacchia, Rosario
• 署名单位: Polytechnic University of Turin; Consiglio Nazionale delle Ricerche (CNR); Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni (IEIIT-CNR)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01482-5
• 发表日期: 2020
• 页码: 249-281
• 关键词: min-max; algorithm

摘要

We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower's total profit. We derive effective lower bounds for the bilevel knapsack problem and present an exact method that exploits the structure of the induced follower's problem. The approach strongly outperforms the current state-of-the-art algorithms designed for the problem. We extend the same algorithmic framework to the interval min-max regret knapsack problem after providing a novel bilevel programming reformulation. Also for this problem, the proposed approach outperforms the exact algorithms available in the literature.