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.
Conditioning on selecting item leaves capacity . Its fractional knapsack problem bounds that item's total interaction with the other selected items. Thus the ordered-pair quadratic objective is at most . Remove overweight items before defining their residual-capacity problems.
Articles by others on the same topic
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.