The Quadratic Knapsack Problem (QKP) is an extension of the classic Knapsack Problem, which is a well-known optimization problem in combinatorial optimization. While the standard Knapsack Problem involves selecting items with given weights and values to maximize the total value without exceeding a weight capacity, the Quadratic Knapsack Problem adds an additional layer of complexity by considering the interactions between the items.
Articles by others on the same topic
The quadratic knapsack problem includes pairwise interactions between selected items. For symmetric , a sum over all ordered pairs counts each unordered interaction twice; an alternative convention sums only over . The objective convention must be kept consistent when bounding or fixing variables.