Knapsack Problem

Knapsack Problem#

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

What is the knapsack problem?#

The knapsack problem is the problem of finding the optimal solution in the following situation. Also, it is known as one of the most famous NP-hard integer programming problems.

Example#

As a concrete example of this problem, we consider the following story:

An explorer was exploring a cave. After walking in the cave for a while, he unexpectedly found some 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 had a small knapsack to carry these treasures. This knapsack can only hold 2 kg. The explorer wants the value of the treasures in this knapsack to be as valuable as possible. Which treasures should the explorer choose to bring back most efficiently?

Formulation#

We consider the generalization above problem. Let \(\{ 0, 1, \dots, i, \dots, N-1 \}\) be the set of items (treasures) to put in the knapsack. Lists of the cost \({v}\) and weight \({w}\) of each item \(i\) allow us to represent the problem.

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

Furthermore, we define a binary variable \(x_i\) that represents the selection of the \(i\)th item. This binary is 1 if we choose \(i\)th item to put into the knapsack, and 0 otherwise. Finally, we denote \(W\) to be the capacity of the knapsack.
We want to maximize the total cost of the item put into the knapsack. Therefore, let us express this requirement as an objective function. In addition, we should take into account the constraint for knapsack capacity limitation. Finally, the mathematical model of this problem is as follows.

\[ \max \quad \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} \]

Modeling by JijModeling#

We show an implementation of the above mathematical model in JijModeling. The knapsack problem is maximizing the objective function, thus, we set sense=jm.ProblemSense.MAXIMIZE.

import jijmodeling as jm

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

Next, we define variables for the mathematical model.

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

v represents a one-dimensional list of values of items, and w represents a one-dimensional list of weights of items. N is the number of items, and W is the knapsack capacity. We define a list of binary variables x corresponding to \(x_i\).

Objective function#

We implement an objective function Equation (1).

problem += jm.sum(v * x)

Constraint#

Next, we implement a constraint Equation (2).

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

Let’s display the implemented mathematical model in Jupyter Notebook to verify that it is correctly implemented.

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{weight}&\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[N;\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}\]

Prepare an instance#

We prepare an instance. Here, we generate 100 items randomly, and the capacity of the knapsack is set to 100.

import numpy as np
# set a list of values & weights 
inst_v = np.random.randint(5,30,100)
inst_w = inst_v + np.random.randint(-2,20,100)
# set maximum weight
inst_W = 100
instance_data = {'v': inst_v, 'w': inst_w, 'W': inst_W}

Solve by JijZeptSolver#

We solve this problem using jijzept_solver.

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

Visualize the solution#

Using the solution obtained, let’s show the sum of the value and weight of the selected items

df = solution.decision_variables_df
obj = solution.objective
indices = np.ravel(df[df["value"]==1]["subscripts"].to_list())
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:  [23 29 11 23  7 17]
Weights of chosen items:  [21 28  9 21  6 15]
Total value from objective:  110.0
Total weight:  100

The knapsack is as well packed as possible, and the items that are light and valuable are chosen to put in the knapsack.

Reference#

[1] Lucas, 2014, “Ising formulations of many NP problems”

Contents