An exact approach for the Stackelberg knapsack problem with weight selection

Abstract

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.