en.wikipedia.org/wiki/Knapsack_problem
2 corrections found
Besides, here we assume that x i > 0
This is not the standard unbounded knapsack formulation: each item count may be zero or more, not strictly positive.
Full reasoning
In the unbounded knapsack problem, the decision variable for each item type is allowed to be any non-negative integer. Requiring x_i > 0 means every item type must appear at least once, which changes the problem to a different, much more restrictive variant.
A standard formulation is x_1, x_2, ..., x_n in {0,1,2,3,...}. That allows zero copies of an item type, which is essential: optimal solutions often omit some item types entirely. The article itself earlier describes unbounded knapsack as allowing a “non-negative integer” number of copies, so this later x_i > 0 statement conflicts with the standard definition.
1 source
- tutORial: Knapsack Problem
Unbounded Problem ... x1, x2, ... ,xn in {0,1,2,3, ...}. ... The objective is to determine how many items from each pile (xj) should be placed in the knapsack...
H = − ∑ i = 1 n v i x i + P ( ∑ i = 1 n w i x i − W ) 2 ,
This penalty term does not represent the standard knapsack constraint `Σ w_i x_i ≤ W`; it penalizes any feasible solution that does not exactly fill the knapsack.
Full reasoning
The standard knapsack constraint is an inequality: total weight may be any value up to the capacity, Σ w_i x_i ≤ W. But the quadratic term written here is minimized when Σ w_i x_i = W exactly, so it also penalizes under-capacity feasible solutions.
That changes the optimization problem. For example, with capacity W=10, an item of weight 10 and value 0, and another item of weight 9 and value 50, the standard knapsack optimum is the 9-weight item. Under the Hamiltonian shown here, the exact-fill 10-weight choice has energy 0, while the 9-weight feasible choice has energy -50 + P; for sufficiently large positive P, the exact-fill but lower-value solution is preferred. So this formula does not simply “embed the constraint condition” for the ordinary knapsack problem.
Standard quantum/QUBO encodings of knapsack handle the ≤ W constraint differently: they either add auxiliary/slack variables to represent allowable total weights up to W, or use a penalty that charges only excess load above W rather than distance from W on both sides.
2 sources
- Ising formulations of many NP problems
The NP-hard knapsack problem asks us to maximize ... subject to the constraint that ... ≤ W. Let y_n for 1 ≤ n ≤ W denote a binary variable which is 1 if the final weight of the knapsack is n, and 0 otherwise.
- Knapsack | QUBO++ Documentation
The knapsack problem aims to select a subset of items that maximizes the total value while keeping the total weight within the capacity... QUBO++ lets you express this capacity constraint (an inequality constraint) ... With the nonlinear function relu, the squared penalty on the excess only, max(0, load - W)^2, can be written directly.