A Branch and Bound solver for the knapsack problem

[ Italian version | English Version | My web page ]

Problem statement

Maximum weight:

Value | Weight
v1 w1

Solution

Current best value: zcur = (none)

Possible branches: (none)

Show as tree

What's this?

This web page and scripts solve the Integer Linear Programming problem known as the "knapsack problem"

max v x
w x ≤ W_max
where x is the unknown vector of binary variables.

Imagine you are a thief at the Louvre (ok, you can think of less incriminating settings): you have to choose some items to steal and put in your knapsack. You can carry a maximum weight of W_max. You know the weight w_i and value v_i of every item i. Of course, you wish to maximize the total stolen value.
The x vector represents a candidate solution: if the x_i coordinate is a 1 you are taking the i-th item with you, otherwise it is set to 0.
The relaxed problem (x_i can be fractions: that is, you are allowed to break items and steal only some pieces) is easily solved: just pick up as many items as you can, ordered by "density" (d_i = v_i / w_i). You'll probably have to break the last item to fill the knapsack to its maximum capacity.

To solve the non-relaxed problem we can use a branch-and-bound algorithm (see Wikipedia for a general introduction). You can interactively choose the branch constraint (that is, which item to pick up). The scripts will automatically compute the relaxed solution. The web page will also automatically keep track of the best solution you got.
You can see the solution tree at any time (and grow it at will by branching on constraints).

Code organization

I tried to keep the interface code (interface.js) isolated from the general branch-and-bound solving algorithm (bb.js). Likewise, I tried to keep the "knapsack problem" specialization separated (knapsack.js).
This way, you can easily re-use the same interface to tackle other problems which can be solved by branch-and-bound. Or you could keep the problem code and build a completely different interface, and so on.

Page layout

The page has been designed to be usable even on small screens and on browsers lacking CSS support. Therefore, the page has a strictly vertical layout. You can also opt to disable the "tree-like" indenting, if that fits your screen better. On big screens only, there's an always visible block showing all the key solution parameters at a glance.
Data input is through a standard form.