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.

Fetching data

To fetch the benchmark data using fetch_knapsack check out the examples.

# 0-1 Knapsack problem
import flowty
import fetch_knapsack

name, n, c, P, W, z, x = fetch_knapsack.fetch("small", instance="knapPI_1_50_1000_1")

# Construct multi-graph
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
P = [-p for p in P] + [0] * len(W)
W = W + [0] * len(W)

model = flowty.Model()
model.setParam("Algorithm", "DP")

g = model.addGraph(obj=P, edges=E, source=0, sink=n, L=1, U=1, type="B")

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

status = model.optimize()

# get the variable values
#
if (
    status == flowty.OptimizationStatus.Optimal
    or status == flowty.OptimizationStatus.Feasible
):
    for path in model.solutions[0].paths:
        print(f"Path {path.idx}")
        for var in path.vars:
            print(f" {var.name}")