Knapsack Problem

Knapsack Problem#

Here we explain how to solve 5.2. Knapsack with Integer Weights from Lucas, 2014, “Ising formulations of many NP problems” using OpenJij, JijModeling, and ommx-openjij-adapter.

Overview of the Knapsack Problem#

The knapsack problem is the problem of finding an optimal solution in situations like the following. It is known as one of the most famous NP-hard integer programming problems. First, let us consider an example.

Example#

As an example of this problem, consider the following story.

An explorer was exploring a cave. After walking through it for a while, the explorer unexpectedly discovered several treasures.

	Treasure A	Treasure B	Treasure C	Treasure D	Treasure E	Treasure F
Price	$5000	$7000	$2000	$1000	$4000	$3000
Weight	800g	1000g	600g	400g	500g	300g

Unfortunately, the only bag the explorer has that can carry the treasures is a small knapsack. This knapsack can hold only 2 kg. The explorer wants to maximize the value of the treasures packed into it. Which items should be chosen to bring back the most valuable set of treasures?

Generalizing the Problem#

To generalize this problem, assume that there is a set $\{ 0, 1, \dots, i, \dots, N-1\}$ of $N$ items to put in the knapsack and that each item has $i$ as its index.
We can represent the problem by defining a list of values $v$ and a list of weights $w$ for the items to be packed into the knapsack.

\[ \nonumber v = \{v_0, v_1, \dots, v_i, \dots, v_{N-1}\} \]

\[ \nonumber w = \{w_0, w_1, \dots, w_i, \dots, w_{N-1}\} \]

Next, let $x_i$ be a binary variable that represents whether item $i$ is selected. This variable satisfies $x_i = 1$ when item $i$ is put into the knapsack and $x_i = 0$ otherwise. Finally, let $W$ be the maximum capacity of the knapsack.
What we want to maximize is the total value of the items placed in the knapsack, which we express as the objective function. Together with the capacity constraint, the knapsack problem can be written as follows:

\[ \max \ \sum_{i=0}^{N-1} v_i x_i \tag{1} \]

\[ \mathrm{s.t.} \quad \sum_{i=0}^{N-1} w_i x_i \leq W \tag{2} \]

\[ x_i \in \{0, 1\} \quad (\forall i \in \{0, 1, \dots, N-1\}) \tag{3} \]

Formulation with JijModeling#

Next, we show how to formulate the above mathematical model using JijModeling. Since the knapsack problem is a maximization problem, we set sense=jm.ProblemSense.MAXIMIZE.

import jijmodeling as jm

problem = jm.Problem("Knapsack", sense=jm.ProblemSense.MAXIMIZE)

Next, let us define the variables and parameters that appear in the mathematical model. We define the variables $v, w, N, W, x_i$ used in the knapsack problem as follows:

v = problem.Float('v', ndim=1)
N = problem.DependentVar("N", v.len_at(0))
w = problem.Float('w', ndim=1)
W = problem.Float('W')
x = problem.BinaryVar('x', shape=(N,))

v defines the list of values $v_i$ for item $i$, w defines the list of weights $w_i$, N is the number of items, and W is the knapsack capacity. x defines the binary variables corresponding to $x_i$.

Objective Function#

The objective function in equation (1) can be formulated as follows:

problem += jm.sum(v * x)

jm.sum(...) can be used to express $\sum_i$.

Constraint#

The constraint in equation (2) can be formulated as follows:

problem += problem.Constraint("capacity", jm.sum(w * x) <= W)

problem.Constraint("capacity", ...) sets a constraint named “capacity”. More generally, Constraint(constraint_name, constraint_expression) lets you assign an appropriate name to a constraint expression.

Let us display the formulated mathematical model in the Jupyter Notebook.

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack}\\\displaystyle \max &\displaystyle \sum _{\vec{\imath }}{{{\left(v\cdot x\right)}}_{\vec{\imath }}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{capacity}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(w\cdot x\right)}}_{\vec{\imath }}}\leq W\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}v&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\w&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(v,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Creating an Instance#

Let us set up the instance of the explorer story from earlier. The values are normalized in units of $1000, and the weights are normalized in units of 100 g.

import numpy as np

# set a list of values & weights
inst_v = np.array([5, 7, 2, 1, 4, 3])
inst_w = np.array([8, 10, 6, 4, 5, 3])
# set maximum weight
inst_W = 20
instance_data = {"v": inst_v, "w": inst_w, "W": inst_W}

Running Optimization with OpenJij#

Let us solve the optimization problem using OpenJij’s simulated annealing.

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

instance = problem.eval(instance_data)

adapter = OMMXOpenJijSAAdapter(instance)
best_sample = adapter.sample(instance, num_reads=100).best_feasible_unrelaxed

Visualizing the Solution#

Using the obtained solution, let us display the values and weights of the packed items.

df = best_sample.decision_variables_df
obj = best_sample.objective
x_df = df[(df["name"] == "x") & (df["value"] > 0.5)]
indices = np.array([sub[0] for sub in x_df["subscripts"]])
sum_w = np.sum(inst_w[indices])

print("Values of chosen items: ", inst_v[indices])
print("Weights of chosen items: ", inst_w[indices])
print("Total value from objective: ", obj)
print("Total weight: ", sum_w)

Values of chosen items:  [7 4 3]
Weights of chosen items:  [10  5  3]
Total value from objective:  14.0
Total weight:  18