The use of Construction Heuristics

In this post, we’ll develop a construction heuristic to build reasonable (start) solutions for the knapsack problem.

Why use Construction Heuristics?

Construction heuristics offer the advantage of quickly leading to acceptable solutions. Unlike more complex optimization algorithms, they are easy to implement and require less computational power. These heuristics are particularly well-suited for handling large problem instances where the search for an optimal solution is in most cases impossible.

How do they work?

Construction heuristics build a solution sequentially from scratch. Once a solution has been constructed, they stop. They are called “greedy”, when a part of the solution is determined in every single step without looking ahead and without undoing decisions that have been made.

Usually, we develop initial solutions to a given (hard) problem using a construction heuristic, then develop better solutions using local search, as described in detail in this post.

Develop a Knapsack Construction Heuristic

If you want to design a construction heuristic, it is best to think about how you would proceed if you wanted to develop the best possible solution to a problem from scratch. There are endless approaches and it often makes sense to try out many ideas. It is also important to know that every construction heuristic has weaknesses. It works well for certain problem instances and poorly for others.

To develop a construction heuristic for the knapsack problem, we consider how we can best pack a backpack with the highest value.

It often makes sense to sort the objects in a certain way first. Since in the standard knapsack problem we want to pack as much value as possible into the backpack, but the weight (capacity) is limited, it is best to sort the items according to value per weight in descending order.

Then, a good construction heuristc could just try to pack as many items that fit into our knapsack.

Turn The Concept Into Code

Let’s say, we have a list of weights and values, providing the knowledge about the items to pack our knapsack and the knapsack capacity. Then we could translate our heuristic as follows:

def construct_knapsack_solution(weights, values, capacity):
    '''
    Create a fair (initial) knapsack solution

    :param weights: Weights of the objects in the knapsack problem
    :param values: Values assigned to the knapsack items
    :param capacity: Capacity of the knapsack
    :return: an (initial) solution to start knapsack optimization with
    '''
    # enrich list with value/weight for each weight-value tupel
    enriched_list = [(idx, value / weight, weight, value) for idx, weight, value in
                     zip(range(len(weights)), weights, values)]
    # now sort list descending by its value/weight coefficient
    sorted_list = sorted(enriched_list, key=lambda x: x[1], reverse=True)
    # now fill knapsack starting from the most valuable item until 
    # no other item fits in
    current_capacity = 0
    current_value = 0
    init_sol = [0] * len(weights)
    for item in sorted_list:
        if capacity - current_capacity >= item[2]:
            init_sol[item[0]] = 1
            current_capacity += item[2]
            current_value += item[3]
    return init_sol, current_value

The heuristic returns the constructed solution as well as its objective value.

Test our Construction Heuristic

A few experiments will show how our new heuristic performs. Ideally, we would benchmark the heuristic against known problem instances for which the optimal solution is known. Due to the lack of available instances, a few manually verifiable instances will be provided here. Later, if desired, I will generate optimal instances using a MILP.

We’ll use the following Knapsack Problem Instance:

weights = [4, 12, 1, 2, 1]
values = [10, 4, 2, 2, 1]
capacity = 15

It is obvious, that the second item should not be packed (too early), since it has a low value and high weight. When invoking the construction heuristic with the instance above, we get the following output:

Solution:  [1, 0, 1, 1, 1] , Value:  15

We see, that the heuristic (accidentally found) the global optimum. 🙂 However, as said, you’ll never find a construction heuristic, which performs equally well on all kinds of problem instances.

A scenario where this heuristic might not be optimal could be if there are items of very high value but also very heavy weight, filling the backpack and neglecting the possibility of holding multiple lighter items of higher value overall. This heuristic could produce suboptimal solutions in such cases. Let’s construct such an instance:

weights = [8.1, 2, 2, 2, 2, 2]
values = [16.3, 4, 4, 4, 4, 4]
capacity = 10

If we pass this instance to the construction heuristic, it will provide the following solution:

Solution:  [1, 0, 0, 0, 0, 0] , Value:  16.3

Now this solution is almost 20% below the global optimum. The first item is immediately picked by the heuristic because of its attractive value/weight coeffitient. It then ‘blocks’ the heuristic from packing other items. However, if all other items would have been packed, we would end up with a fully packed knapsack and a value of 20.

The Complete Source

Below, you’ll find the source code for the entire Python program, also available on GitHub for your convenience.

def construct_knapsack_solution(weights, values, capacity):
    '''
    Create a fair (initial) knapsack solution

    :param weights: Weights of the objects in the knapsack problem
    :param values: Values assigned to the knapsack items
    :param capacity: Capacity of the knapsack
    :return: an (initial) solution to start knapsack optimization with
    '''
    # enrich list with value/weight for each weight-value tupel
    enriched_list = [(idx, value / weight, weight, value) for idx, weight, value in
                     zip(range(len(weights)), weights, values)]
    # now sort list descending by its value/weight coefficient
    sorted_list = sorted(enriched_list, key=lambda x: x[1], reverse=True)
    # now fill knapsack starting from the most valuable item until no other item fits in
    current_capacity = 0
    current_value = 0
    init_sol = [0] * len(weights)
    for item in sorted_list:
        if capacity - current_capacity >= item[2]:
            init_sol[item[0]] = 1
            current_capacity += item[2]
            current_value += item[3]
    return init_sol, current_value


# Main program
# Knapsack problem definition
weights = [4, 12, 1, 2, 1]
values = [10, 4, 2, 2, 1]
capacity = 15

init_sol, init_val = construct_knapsack_solution(weights, values, capacity)
print("Solution: ", init_sol, ", Value: ", init_val)