Knapsack Problem

Given a set of items, each with a weight and a value, and a knapsack with a limited weight capacity, the knapsack problem aims to select a subset of items that maximizes the total value while keeping the total weight within the capacity.

Let $w_i$ and $v_i$ ($0\leq i\leq n-1$) denote the weight and value of item $i$, respectively. Let $S\in \lbrace 0, 1, \ldots n-1\rbrace$ be the set of selected items.

\[\begin{aligned} \text{Maximize:} & \sum_{i\in S} v_i \\ \text{Subject to:} & \sum_{i\in S} w_i \leq W \end{aligned}\]

where $W$ is the weight capacity of the knapsack.

QUBO formulation

To formulate this problem as a QUBO, we introduce a set $X$ of $n$ binary variables $x_i\in\lbrace 0,1\rbrace$ ($0\leq i\leq n-1$), where item $i$ is selected if and only if $x_i=1$.

The above formulation can be rewritten as:

\[\begin{aligned} \text{Maximize:} & \sum_{i=0}^{n-1} v_ix_i \\ \text{Subject to:} & \sum_{i=0}^{n-1} w_ix_i \leq W \end{aligned}\]

PyQBPP program

The constraint can be expressed using the range operator provided by PyQBPP through qbpp.constrain(..., between=(lo, hi)). The resulting QUBO objective function is defined as:

\[\begin{aligned} f(X) &= -\sum_{i=0}^{n-1} v_ix_i + P\times (0\leq \sum_{i=0}^{n-1} w_ix_i \leq W) \end{aligned}\]

Since QUBO solvers minimize the objective function, the original maximization objective is negated. The constant $P$ is a sufficiently large penalty parameter to enforce the constraint.

The following PyQBPP program solves a knapsack problem with 10 items using the Exhaustive Solver:

import pyqbpp as qbpp

w = qbpp.array([10, 20, 30, 5, 8, 15, 12, 7, 17, 18])
v = qbpp.array([60, 100, 120, 60, 80, 150, 110, 70, 150, 160])
capacity = 50

x = qbpp.var("x", shape=len(w))

constraint = (0 <= qbpp.sum(w * x)) & (qbpp.same <= capacity)
objective = qbpp.sum(v * x)

f = -objective + 1000 * constraint
f.simplify_as_binary()

solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for idx, sol in enumerate(result.sols):
    print(f"[Solution {idx}]")
    print(f"Energy = {sol.energy}")
    print(f"Constraint = {sol(constraint.body)}")
    print(f"Objective = {sol(objective)}")
    for j in range(len(w)):
        if sol(x[j]) == 1:
            print(f"Item {j}: weight = {w[j]}, value = {v[j]}")

In this program, the expressions constraint and objective are constructed separately and combined into the final QUBO expression f using a penalty coefficient of 1000. The Exhaustive Solver is then applied to f to enumerate all optimal solutions.

The following output shows the optimal solutions, including the energy, constraint value, and objective value:

[Solution 0]
Energy = -480
Constraint = 50
Objective = 480
Item 3: weight = 5, value = 60
Item 5: weight = 15, value = 150
Item 6: weight = 12, value = 110
Item 9: weight = 18, value = 160
[Solution 1]
Energy = -480
Constraint = 50
Objective = 480
Item 3: weight = 5, value = 60
Item 4: weight = 8, value = 80
Item 6: weight = 12, value = 110
Item 7: weight = 7, value = 70
Item 9: weight = 18, value = 160

We can observe that this instance has two optimal solutions, both achieving a total value of 480 while exactly satisfying the capacity constraint.