0-1 Knapsack Problem¶

Pick the items that gives the most value and fits in the knapsack. This may be formulated as a mixed integer programme like

$\begin{aligned} \max{ } & \sum_{i \in I} p_i x_i \\ \text{s.t. } & \sum_{i \in I} w_i x_i \leq Q \\ & x_i \in \mathbb{B} && i \in I \end{aligned}$

It can also be formulated as a network problem on a multi-graph $G(V,E)$ with $V = \{1, \dots, |I| + 1 \}$ vertices and $2[I|$ edges $E = E_r \cup E_n$ with $E_r = \{ (1, 2), \dots, (|I|, |I| +1)\}$ and $E_n = \{ (1, 2), \dots, (|I|, |I| +1)\}$ where traversal of a regular edge $(i,j) \in E_r$ indicates that item $i$ is put in the knapsack and an edge $(i,j) \in E_n$ indicates not selecting item $i$. The edges $(i,j) \in E_r$ are weighted with the item weights $w_i$ and profits $p_i$ and the edges in $E_n$ all have weight and profit equal to 0. The total weight of the path from 1 to vertex $|I|+1$ must be less than the knapsack capacity $Q$.

An example graph with 3 items looks like

The objective is to find a maximum profit path with accumulated weight less than the capacity.

This corresponds to the network model

$\begin{aligned} \max{ } & \sum_{(i,j) \in E} p_i x_{ij} \\ \text{s.t. } & x_{ij} = \sum_{p \in P} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big ) \lambda_p & & (i,j) \in E \\ & 1 \leq \sum_{p \in P} \lambda_p \leq 1 \\ & \lambda_p \in \mathbb{B} && p \in P \\ & x_{i,j} \in \mathbb{B} && (i,j) \in E \end{aligned}$

where $p \in P$ are paths in a graph $G(V,E)$ subject to the capacity constraint modeled as a disposable resource with edge consumption $w_i$ for regular edge $(i,j)$ otherwise 0 and bounds $[0,Q]$ for all $i \in V$.

Such models can be solved directly with the dynamic programming algorithm and when defining the model we need only to define the graph and the resource constraints, see the modeling section.

# 0-1 Knapsack problem

from flowty import Model

# profit and weight per item
p = [10, 13, 18, 31, 7, 15]
w = [11, 15, 20, 35, 10, 33]
c = 47

# multi-graph with edge 'pick'/'pick not' item
es = [
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (5, 6),
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (5, 6),
]

# zero profit and weight for 'pick not' edges
ps = [-x for x in p] + [0] * len(w)
ws = w + [0] * len(w)

m = Model()
# specify dynamic programming algorithm
m.setParam("Algorithm", "DP")

g = m.addGraph(obj=ps, edges=es, source=0, sink=6, L=1, U=1, type="B")

m.addResourceDisposable(
    graph=g, consumptionType="E", weight=ws, boundsType="V", lb=0, ub=c
)

status = m.optimize()
print(f"ObjectiveValue {round(m.objectiveValue)}")

# get the variable values
for var in m.vars:
    if var.x > 0:
        print(f"{var.name} = {round(var.x, 1)}")