4  KnapSac

4.1 Introduction

In integer linear optimization, we consider a weight capacity for a bag, along with lists of item weights and values The goal of the Knapsack problem is to maximize the value of items placed in the bag without exceeding its weight capacity.

More formally : let \(b \in \Bbb N, w_{1},...,w_{n} \in \Bbb N^n, v_{1},...,v_{n} \in \Bbb N^n\)
We want to determine \(\max_i \{\sum_{i=1}^{n} v_{i}x_{i}\,|\,\sum_{i=1}^{n} w_{i}x_{i} < b, x_{i} \in \{0,1\}, i = 1,..,n\}\)

4.2 Algorithm

4.2.1 Upper bound

    sort the items of the bag by value/weight
    upper_bound = 0
    weight_available = weight capacity of the bag
    for each element in the bag:
        if element weight > weight available:
            return upper_bound + element value * weight_available/element weight
        else:
            weight_available -= element weight
            upper_bound += element value

4.2.2 Lower bound

    sort the items of the bag by value/weight
    upper_bound = 0
    weight_available = weight capacity of the bag
    for each element in the bag:
        if element weight < weight available:
            weight_available -= element weight
            upper_bound += element value
    return lower_bound

4.2.3 Branch and bound

    if there there are no items in the bag return 0
    if upper_bound == lower_bound return upper_bound
    if weight_capacity of the bag >= weight of the first item in the bag
        value1 = value of the first item in the bag + branch and bound on the bag
        (weight_capacity - weight of the first item, items values[1:], items weights[1:])
        if value1 == upper_bound return upper_bound
    value2 branch and bound on the bag wihtouth the first item
    return the max between value1 and value2

4.2.4 Dynamic programming

    S = [0,0]
    for each element int the bag:
        for each pair in S:
            if(element weight + pair weight < weight capacity of the bag):
                add element + pair to S
        delete redundant elements
    return the max of the values in S

4.2.5 Dynamic programming with adaptative scale

    S = [0,0]
    for each element int the bag:
        for each pair in S:
            if(element weight + pair weight < weight capacity of the bag):
                add element value/mu + pair value,element weight + pair weight to S
        delete redundant elements
    return the max of the values in S

4.3 Code

To find the solution to the KnapSack problem, create a KnapSack :

KnapSack(weight_capacity,array of items weight, array of items value)

Then choose a solving algorithm between :

• lower_bound (gives you a lower bound to the knapsack solution)
• upper_bound (gives you an upper bound to the knapsack solution)
• solve_branch_and_bound (gives you the exact solution to the knapsack)
• solve_dynamic_prog (gives you the exact solution to the knapsack)
• solve_dynamic_prog_scale_change (gives you a lower bound very close to the solution for large Knapsack problems)

4.3.1 Examples

ks = KnapSack(3,[1,1,1,2],[3,2,1,1])

ks.lower_bound() : 6
ks.upper bound() : 6.0
ks.solve_branch_and_bound() : 6
ks.solve_dynamic_prog() : 6
ks.solve_dynamic_prog_scale_change() : 4

You can make solve_dynamic_prog_scale_change run faster and use less memory by passing a larger mu as parameter

ks = KnapSack(3,[1,1,1,2],[8,7,3,1])

ks.lower_bound() : 18
ks.upper bound() : 18.0
ks.solve_branch_and_bound() : 18
ks.solve_dynamic_prog() : 18
ks.solve_dynamic_prog_scale_change() : 16

Tests with benchmark

TestKnapSack.benchmark_time(ks)

Times
    Lower Bound       : 0.000007 seconds
    Upper Bound       : 0.000013 seconds
    Dynamic           : 0.000019 seconds
    Branch and Bound  : 0.000019 seconds
    Dynamic Adaptative: 0.000023 seconds

TestKnapSack.benchmark_precision(ks)

Results
    Dynamic            : 18, 100% of the solution , or 0 away from the solution
    Branch and Bound   : 18, 100% of the solution , or 0 away from the solution
    Upper Bound        : 18.0, 100% of the solution , or 0.0 away from the solution
    Lower Bound        : 18, 100% of the solution , or 0 away from the solution
    Dynamic Adaptative : 16, 89% of the solution , or -2 away from the solution