<p>The Stackelberg knapsack game with weight selection (SKPW) is a variation of the bilevel knapsack problem in which the leader must determine the weights of a given subset of items, and then, the follower solves the knapsack problem to maximize the profit sum. The leader’s objective is to maximize the sum of the weights of the leader’s items included in the follower’s knapsack solution. In this paper, we present an exact algorithm to solve SKPW for the first time in the literature. We establish a strict linear inequality system with an exponential number of constraints, whose feasibility can be utilized to find an optimal solution for SKPW. To address the challenge posed by the strict inequalities more effectively, we propose a linear program with exponentially many constraints. We report computational results on several randomly generated instances and compare the solutions derived from the proposed exact algorithm with those obtained using heuristic algorithms.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An exact approach for the Stackelberg knapsack problem with weight selection

  • Yeonghun Lee,
  • Kiho Seo,
  • Seulgi Joung,
  • Sungsoo Park

摘要

The Stackelberg knapsack game with weight selection (SKPW) is a variation of the bilevel knapsack problem in which the leader must determine the weights of a given subset of items, and then, the follower solves the knapsack problem to maximize the profit sum. The leader’s objective is to maximize the sum of the weights of the leader’s items included in the follower’s knapsack solution. In this paper, we present an exact algorithm to solve SKPW for the first time in the literature. We establish a strict linear inequality system with an exponential number of constraints, whose feasibility can be utilized to find an optimal solution for SKPW. To address the challenge posed by the strict inequalities more effectively, we propose a linear program with exponentially many constraints. We report computational results on several randomly generated instances and compare the solutions derived from the proposed exact algorithm with those obtained using heuristic algorithms.