Knapsack Problem

Knapsack Problem#

Here we show how to solve the knapsack problem using OpenJij, JijModeling,. This problem is also mentioned in 5.2. Knapsack with Integer Weights in Lucas, 2014, “Ising formulations of many NP problems”.

Overview of the Knapsack Problem#

The knapsack problem is the problem of finding the optimal solution in the following situations. 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.

In a cave, an 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 explorer only has a small knapsack. This knapsack can only hold up to 2 kg. The explorer wants to get as much value as possible for the treasure in this knapsack, so which treasures should he bring back?

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 making a list of costs \(\boldsymbol{v}\) and a list of weights \(\boldsymbol{w}\) for each luggage \(i\) to be put in the knapsack.

\[ \nonumber \boldsymbol{v} = \{v_0, v_1, \dots, v_i, \dots, v_{N-1}\} \]
\[ \nonumber \boldsymbol{w} = \{w_0, w_1, \dots, w_i, \dots, w_{N-1}\} \]

Let \(x_i\) further denote the binary variable that represents the \(i\)th package selected. It is \(x_i = 1\) when \(i\) is placed in the knapsack and \(x_i = 0\) when \(i\) is not. Finally, let \(W\) be the maximum capacity of the knapsack.
We want to maximize the total value of luggage we can put in the knapsack, and we express this as an objective function. Given the further constraint that the knapsack must be below the capacity limit, the knapsack problem can be expressed as the following expression:

(1)#\[ \max \ \sum_{i=0}^{N-1} v_i x_i \]
(2)#\[ \mathrm{s.t.} \quad \sum_{i=0}^{N-1} w_i x_i \leq W \]
(3)#\[ x_i \in \{0, 1\} \quad (\forall i \in \{0, 1, \dots, N-1\}) \]

Modeling by JijModeling#

Variables#

Let us define the variables \(\boldsymbol{v}, \boldsymbol{w}, N, W, x_i, i\) used in expressions (1), (2) and (3) as follows:

import jijmodeling as jm


# define variables
v = jm.Placeholder('v', ndim=1)
N = v.len_at(0, latex='N')
w = jm.Placeholder('w', shape=(N,))
W = jm.Placeholder('W')
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', (0, N))

v = jm.Placeholder('v', dim=1) declares a one-dimensional list of values of things to put in the knapsack, and the number of elements is N. N has set_latex() expression so that the representation changes (link). Using that N, we can guarantee that v and w have the same length by defining a one-dimensional list representing the weight of the items to put in the knapsack as w = jm.Placeholder('w', shape=(N)). W = jm.Placeholder('W') defines \(W\) to represent the knapsack capacity limit. x = jm.Binary('x', shape=(N)) defines a binary variable list x of the same length as v, w. Finally, i = jm.Element('i', (0, N)) defines the indices of \(v_i, w_i, x_i\), which are integers in the range \(0\leq i < N\).

Objective Function#

Expression (1) is implemented as an objective function. Note that we added a negative sign to make this a minimization problem. Let us create a problem and add an objective function to it. By Sum(i, formula), we can sum the expression part to the subscript i.

# set problem
problem = jm.Problem('Knapsack')    
# set objective function
obj = - jm.sum(i, v[i]*x[i])
problem += obj

Constraint#

Let us implement the constraint in expression (2) by using Constraint(constraint name, constraint expression). This gives the appropriate constraint name to the constraint expression.

# set total weight constraint
total_weight = jm.sum(i, w[i]*x[i])
problem += jm.Constraint('weight', total_weight<=W)
problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Knapsack} & & \\& & \min \quad \displaystyle - \sum_{i = 0}^{N - 1} v_{i} \cdot x_{i} & \\\text{{s.t.}} & & & \\ & \text{weight} & \displaystyle \sum_{i = 0}^{N - 1} w_{i} \cdot x_{i} \leq W & \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

Instance#

Let us set up an instance of the explorer story from earlier. The value of the treasure is normalized to $1000, and the weight of the treasure is also normalized to 100g.

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}

Create Instance#

instance = jm.Interpreter(instance_data).eval_problem(problem)

Solve by OpenJij’s SA#

import ommx_openjij_adapter as oj_ad

sampleset = oj_ad.OMMXOpenJijSAAdapter.sample(
    instance,
    num_reads=100,
    uniform_penalty_weight=1.0
)

Displaying the Solution#

sampleset.summary
objective feasible
sample_id
5 -14.0 True
6 -14.0 True
22 -14.0 True
31 -14.0 True
33 -14.0 True
... ... ...
26 -8.0 False
39 -8.0 False
64 -7.0 False
52 -5.0 False
93 -5.0 False

100 rows × 2 columns

From the result thus obtained, let us see which treasures we decide to put in the knapsack.

x_value = sampleset.best_feasible_unrelaxed().extract_decision_variables("x")
items = [i[0] for i, v in x_value.items() if v == 1]
print("Items: ", items)
print("Total value: ", sum(inst_v[items]))
print("Total weight: ", sum(inst_w[items]))

Items:  [1, 4, 5]
Total value:  14
Total weight:  18
Contents