Skip to content

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

maxiIpixis.t. iIwixiQxiBiI \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)G(V,E) with V={1,,I+1}V = \{1, \dots, |I| + 1 \} vertices and 2[I2[I| edges E=ErEnE = E_r \cup E_n with Er={(1,2),,(I,I+1)}E_r = \{ (1, 2), \dots, (|I|, |I| +1)\} and En={(1,2),,(I,I+1)}E_n = \{ (1, 2), \dots, (|I|, |I| +1)\} where traversal of a regular edge (i,j)Er(i,j) \in E_r indicates that item ii is put in the knapsack and an edge (i,j)En(i,j) \in E_n indicates not selecting item ii. The edges (i,j)Er(i,j) \in E_r are weighted with the item weights wiw_i and profits pip_i and the edges in EnE_n all have weight and profit equal to 0. The total weight of the path from 1 to vertex I+1|I|+1 must be less than the knapsack capacity QQ.

An example graph with 3 items looks like

graph LR 1 --> 2 2 --> 3 3--> 4 1 -.-> 2 2 -.-> 3 3 -.-> 4

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

This corresponds to the network model

max(i,j)Epixijs.t. xij=pP(sp:s=(i,j)1)λp(i,j)E1pPλp1λpBpPxi,jB(i,j)E \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 pPp \in P are paths in a graph G(V,E)G(V,E) subject to the capacity constraint modeled as a disposable resource with edge consumption wiw_i for regular edge (i,j)(i,j) otherwise 0 and bounds [0,Q][0,Q] for all iVi \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)}")