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
It can also be formulated as a network problem on a multi-graph with vertices and edges with and where traversal of a regular edge indicates that item is put in the knapsack and an edge indicates not selecting item . The edges are weighted with the item weights and profits and the edges in all have weight and profit equal to 0. The total weight of the path from 1 to vertex must be less than the knapsack capacity .
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
where are paths in a graph subject to the capacity constraint modeled as a disposable resource with edge consumption for regular edge otherwise 0 and bounds for all .
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}")