Algorithms

Previous: What affects performance

Next: Parallel programming

Material for the lesson

Video: Algorithms are good
Video: Dr Jones on Branch & Bound
Video: MaxAlign example
Powerpoint: Algorithms
Example: MaxAlign
Web service: MaxAlign web service
PDF: Branch and Bound
Example: B&B example
Video: What is expected in exercises

Exercises

In the file knapsack.lst you find 100 different items with varying size and value.
Make a program that selects the subset of items that can be in your knapsack and has the biggest value. This is a combinatorial maximization problem.
The size of your knapsack is 342. You can start with selecting among the first 20 items on the list for testing. The problem grows exponentially larger with the number of items, so do be careful how many you select from.

The exercise can be done on your laptop. Computerome is not needed, but can be used.
Using the first 20 items on the list the result is
Items: 13
Combined size: 341.7
Combined value: 1704.8

This is known as "The Knapsack Problem" and is typically solved using the Branch and Bound paradigm.
https://en.wikipedia.org/wiki/Knapsack_problem

Challenge: Done right, this can be solved for the entire list in less than 1/10 second, done wrong you can wait years for the program to finish.

To help you understand the core of the "branch" part of the algorithm that goes through the search tree, run this python code. It is here for your understanding, not for performance. Once you understand the principle, you can adapt the code to your problem.

#!/usr/bin/env python3

maxsize = 100
problem = 'XXXX'
bestproblem = ''
bestvalue = 0
stack = [problem]

while len(stack) > 0:
    problem = stack.pop()
    # Calculate bound/estimate and constraint of choices
    # This is not done for you - calculate your own
    estimate = 0
    size = 45
    # if bound/estimate is worse than any previous found solution, discard
    if estimate < bestvalue:
        continue
    # Are constraints exceeded, discard
    if size > maxsize:
        continue
    # Still not solved, then split the problem
    if 'X' in problem:
        nextx = problem.find('X')
        stack.append(problem[:nextx] + '1' + problem[nextx+1:])
        stack.append(problem[:nextx] + '0' + problem[nextx+1:])
    # Solved, is the better than any solution so far?
    elif estimate > bestvalue:
        bestvalue = estimate
        bestproblem = problem
    # What is going on with the stack???
    print(stack)