An exact approach for the Stackelberg knapsack problem with weight selection

Yeonghun Lee (), Kiho Seo (), Seulgi Joung () and Sungsoo Park ()
Additional contact information
Yeonghun Lee: Korea Advanced Institute of Science and Technology
Kiho Seo: Samsung Electronics
Seulgi Joung: Ajou University
Sungsoo Park: Korea Advanced Institute of Science and Technology

Journal of Global Optimization, 2025, vol. 92, issue 4, No 6, 973-991

Abstract: 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.

Keywords: Integer programming; Knapsack problem; Stackelberg game; Bilevel programming; Exact approach (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01488-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:4:d:10.1007_s10898-025-01488-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01488-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().