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
from or_datasets import pisinger

bunch = pisinger.fetch_knapsack("small", instance="knapPI_1_50_1000_1")
name, n, c, p, w, z, x = bunch["instance"]

E = [(i, i + 1) for i in range(n)] + [(i, i + 1) for i in range(n)]

# zero profit and weight for 'pick not' edges
# signs are flipped for maximization
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=E, source=0, sink=n, L=1, U=1, type="B")

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

status = m.optimize()