Knapsack Problem

Knapsack Problem#

Here we show how to solve the knapsack problem using OpenJij, JijModeling, and JijModeling Transpiler. 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', dim=1)
N = v.shape[0].set_latex('N')
w = jm.Placeholder('w', shape=(N,))
W = jm.Placeholder('W')
x = jm.Binary('x', shape=(N,))
i = jm.Element('i', (0, N))

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 import jijmodeling as jm
      4 # define variables
      5 v = jm.Placeholder('v', dim=1)

ModuleNotFoundError: No module named 'jijmodeling'

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{alignat*}{4}\text{Problem} & \text{: Knapsack} \\\min & \quad - \sum_{ i = 0 }^{ N - 1 } v_{i} \cdot x_{i} \\\text{s.t.} & \\& \text{weight} :\\ &\quad \quad \sum_{ i = 0 }^{ N - 1 } w_{i} \cdot x_{i} \leq W,\\[8pt]& x_{i_{0}} \in \{0, 1\}\end{alignat*}

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.

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

Undetermined Multiplier#

This knapsack problem has one constraint, and we need to set the weight of that constraint. We will set it to match the name we gave in the Constraint part earlier using a dictionary type.

# set multipliers
lam1 = 1.0
multipliers = {'weight': lam1}

Conversion to PyQUBO by JijModeling Transpiler#

JijModeling has executed all the implementations so far. By converting this to PyQUBO, it is possible to perform combinatorial optimization calculations using OpenJij and other solvers.

from jijmodeling.transpiler.pyqubo import to_pyqubo

# convert to pyqubo
pyq_model, pyq_chache = to_pyqubo(problem, instance_data, {})
qubo, bias = pyq_model.compile().to_qubo(feed_dict=multipliers)

The PyQUBO model is created by to_pyqubo with the problem created by JijModeling and the instance_data we set to a value as arguments. Next, we compile it into a QUBO model that can be computed by OpenJij or other solver.

Optimization by OpenJij#

This time, we will use OpenJij’s simulated annealing to solve the optimization problem. We set the SASampler and input the QUBO into that sampler to get the result of the calculation.

import openjij as oj
# set sampler
sampler = oj.SASampler(num_reads=100)
# solve problem
response = sampler.sample_qubo(qubo)

Decoding and Displaying the Solution#

Decode the returned results to facilitate analysis.

# decode solution
result = pyq_chache.decode(response)

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

indices, _, _ = result.lowest().record.solution['x'][0]
inst_w = instance_data['w']
sum_w = 0
for i in indices[0]:
    sum_w += inst_w[i]
print('Indices of x = 1: ', indices[0])
print('Value of objective function: ', result.lowest()[0].evaluation.objective)
print('Value of constraint term: ', result.lowest()[0].evaluation.constraint_violations['weight'])
print('Total weight: ', sum_w)

Indices of x = 1:  [1, 4, 5]
Value of objective function:  [-14.0]
Value of constraint term:  [0.0]
Total weight:  18

The value of the objective function multiplied by the minus sign is the total value of the treasure in the knapsack. result.evaluation.constraint_violations[constraint name] shows how many of its constraints are not satisfied.