Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Solving the knapsack problem with branch and bound

The knapsack problem sits at the heart of combinatorial optimisation, where the task is to choose a subset of items that maximises total value while staying within a weight limit. When the item count is small enough to try every combination, brute force works, but for realistic inputs a more disciplined search is required. Branch and bound delivers exactly that discipline, turning an exponential search into something far faster without losing the guarantee of an optimal solution.

Computer science students at the University of Melbourne and UNSW routinely encounter this technique in algorithms and operations research units. The combination of theory, pseudocode, and a working implementation makes it one of the most satisfying classic problems to study, because the leap from naive recursion to an intelligent search tree is so clear.

Before diving into code, it helps to remind yourself of the standard 0/1 variant: each item can either be taken whole or left behind, and fractional knapsack is out of scope. The branches of the search tree correspond to deciding the fate of each item, and the clever trick lies in cutting branches that cannot possibly lead to a better answer than what has already been found.

Understanding the knapsack problem

In its classical 0/1 form, you are given a set of n items, each with a weight w_i and a value v_i, plus a capacity W. The goal is to maximise sum(v_i x_i) subject to sum(w_i x_i) ≤ W, where x_i ∈ {0, 1}. The problem is NP-hard, so no polynomial algorithm is known, but for n in the dozens or low hundreds branch and bound handles the workload comfortably.

Real-world constraints often add extra layers of complexity. A logistics planner in Port Hedland arranging iron ore shipments faces not only weight limits on a vessel but also crane availability windows. A wheat farmer near Wagga Wagga packing silos must respect both storage capacity and contamination rules for different grades. Many of these richer problems reduce to a core knapsack after simplifications, which is why mastering the basic version pays off in many directions.

The integer nature of the variables is what makes the problem hard. If items could be split, a greedy sort by value-to-weight ratio solves the fractional variant in O(n log n). The 0/1 rule means you must commit to whole items, which brings the combinatorial explosion that branch and bound is designed to tame.

The branch and bound paradigm

Branch and bound is a systematic search with three ingredients: a way to branch the search space into smaller subproblems, a relaxation that yields an upper bound on a subproblem's best achievable value, and a lower bound from a feasible solution. When the upper bound of a node cannot beat the current best known integer answer, that node is pruned, and the work it would have demanded is skipped.

The branching step for knapsack is beautifully simple. At a given node you pick an item that has not yet been decided and create two children: one where you include the item (subtract its weight from remaining capacity, add its value to the running total) and one where you exclude it. Repeating this builds a binary tree whose leaves correspond to every feasible subset.

The clever part is not the branching itself; it is how tightly you can bound each subproblem. A weak bound leaves the tree nearly fully explored, while a strong bound prunes aggressively. The next section looks at the most popular bound used in practice.

Linear relaxation and effective bounds

To compute an upper bound at any node, solve the linear programming relaxation: treat x_i as a continuous variable in [0, 1] and keep all other constraints. The optimal value of this LP is at least the optimal integer value of the subproblem, so it provides a valid ceiling. Solving an LP at every node sounds expensive, but for knapsack the structure permits a much simpler O(n) greedy computation.

Sort the remaining undecided items by their value-to-weight ratio. Fill the remaining capacity by taking items whole until one item would exceed it, then take a fractional slice of the next item. This greedy solution equals the LP optimum thanks to the greedy-optimality theorem for fractional knapsack, and it can be implemented with just a loop over the sorted items.

A lower bound is usually obtained from a constructive heuristic. A common choice is a depth-first enumeration that always takes the next item if it fits, followed by running the relaxed solution and rounding down at integration time. Better still, a local search can be applied to whatever integer solution the construction produces.

Constructing the search tree

A practical implementation orders nodes by their upper bound, an approach known as best-first or priority-queue search. Store unvisited nodes in a max-heap keyed on their relaxed value, and at each step pop the most promising node, branch, and push its children back onto the heap. This strategy reaches high-value solutions early, sharpening the lower bound quickly and accelerating pruning.

Depth-first search is an alternative that uses much less memory, often important when n is large and the priority queue would overflow. With a good variable ordering (high-ratio items first) and a tight greedy lower bound, depth-first branch and bound routinely solves instances with hundreds of items in well under a second on a workstation in Canberra or Brisbane.

A useful enhancement is to recompute bounds at every node from scratch using only the items that are still free to decide, rather than carrying forward stale figures. This small change often pays dividends and avoids subtle off-by-one errors that arise when an upper bound at depth d fails to reflect an item already committed at a shallower depth.

Pruning strategies and heuristic guidance

Beyond the LP relaxation, several pruning rules fall out of the model itself. If the remaining capacity is zero, no more items fit and the node can be evaluated directly. If the upper bound from the relaxation equals the running value plus the LP bonus and the bonus is precisely the value of items that could still be taken, the node may collapse to a single integer outcome.

Variable ordering also matters. Selecting the item with the highest value-to-weight ratio first typically produces smaller trees because high-value items get decided early, sharpening the bounds for the rest of the search. Conversely, fixing loose variables (those that are nearly always selected in the LP solution) in the right direction can shorten the tree dramatically.

Comparing optimisation paradigms can sharpen intuition. The boosting literature, including treatments of the understanding AdaBoost workflow, uses reweighting of examples to focus on hard cases. The principle is analogous: focus computational effort where the problem is hardest, and let easy parts sail through.

A Python implementation walkthrough

A clean implementation pairs a node class with two helpers: one that computes the relaxed upper bound and one that executes the greedy lower-bound heuristic. Each node stores depth, the running value, the remaining capacity, and a flag for whether the next item is forced to be excluded because of a parent's decision.

The main loop pops from a max-heap, checks the bound against the best-known integer solution, branches, and pushes children onto the heap. A simple heuristic called before the loop starts provides an initial lower bound, which is then updated whenever the search finds a better integer solution. This scaffolding is roughly fifty lines of Python and easy to extend with problem-specific constraints.

Supporting data structures can speed up repeated queries inside the relaxations. If you find yourself scanning sorted items to recompute totals, look at data structures for prefix sums such as the Fenwick tree range queries implementation, which lets you get cumulative weights in O(log n). Pairing it with proper caching prevents recomputation across closely related nodes.

Practical applications and practice exercises

The conceptual weight of the method carries well into industries far beyond academia. Australian freight dispatchers allocating containers at the Port of Melbourne, mining companies planning daily truck routes near Kalgoorlie, and hospital administrators in Adelaide scheduling elective surgeries under limited bed availability all face knapsack-like constraints at some point in their workflow.

When preparing for interviews or competitive programming, look for problems whose statement disguises a knapsack core. Hiring decisions with budget caps, meal planning with calorie limits, and capital budgeting with cash-flow constraints all reduce to the same shape. Training yourself to recognise the reduction is half the battle won.

For a refresher on the broader ecosystem of algorithms explored on this site, head over to the about page for an overview of topics covered and links to related readings. Reading across categories often reveals connections you would not find while staying inside a single track.

Guidelines for efficient branch and bound solvers