Branch and Bound · Algorithms (DAA)

Branch and bound (B&B) is used for optimisation problems (find the best solution, not all solutions). Like backtracking, it explores a state-space tree, but at every node it computes a bound — the best value any solution in that subtree could possibly achieve. If the bound is no better than the best complete solution found so far, the whole subtree is pruned.

	Backtracking	Branch and bound
Problem type	decision / find all solutions	optimisation
Search order	depth-first	FIFO (BFS), LIFO (DFS) or least-cost (best-first)
Pruning	when a constraint fails	when the bound cannot beat the best so far
Examples	N-Queens, Sudoku	0/1 knapsack, TSP, job assignment

Search strategies

FIFO B&B — live nodes in a queue (breadth-first).
LIFO B&B — live nodes in a stack (depth-first).
Least-cost (LC) B&B — live nodes in a priority queue, always expanding the most promising node first. Usually the fastest to reach the optimum.

0/1 knapsack with B&B

At each node, decide whether to include the next item. The upper bound of a node is its current value plus the value obtainable by filling the remaining capacity fractionally with the remaining items (sorted by value/weight). Since the fractional relaxation is never worse than the real 0/1 answer, it is a valid optimistic bound.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Item { int w, v; };
struct Node { int level, value, weight; double bound; };
vector<Item> items;
int W;

double bound(const Node &u) {
    if (u.weight >= W) return 0;
    double b = u.value;
    int w = u.weight, j = u.level + 1;
    for (; j < (int)items.size() && w + items[j].w <= W; j++) { w += items[j].w; b += items[j].v; }
    if (j < (int)items.size()) b += (W - w) * (double)items[j].v / items[j].w;   // fractional fill
    return b;
}

int main() {
    items = {{2, 40}, {5, 30}, {10, 50}, {5, 10}};   // (weight, value)
    W = 16;
    sort(items.begin(), items.end(), [](Item a, Item b) { return a.v * b.w > b.v * a.w; });
    auto cmp = [](const Node &a, const Node &b) { return a.bound < b.bound; };
    priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);   // least-cost: largest bound first
    Node root{-1, 0, 0, 0};
    root.bound = bound(root);
    pq.push(root);
    int best = 0, expanded = 0;
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (u.bound <= best || u.level == (int)items.size() - 1) continue;   // prune
        expanded++;
        Node take{u.level + 1, u.value + items[u.level + 1].v, u.weight + items[u.level + 1].w, 0};
        if (take.weight <= W && take.value > best) best = take.value;
        take.bound = bound(take);
        if (take.weight <= W && take.bound > best) pq.push(take);
        Node skip{u.level + 1, u.value, u.weight, 0};
        skip.bound = bound(skip);
        if (skip.bound > best) pq.push(skip);
    }
    cout << "best value = " << best << " (nodes expanded: " << expanded << ")" << endl;
    return 0;
}

Output

best value = 90 (nodes expanded: 5)

Try it Yourself

Travelling salesperson problem (TSP)

Visit every city exactly once and return home with the minimum total distance. Brute force checks (n − 1)! tours. B&B builds tours city by city and bounds each partial tour with a lower bound — for example, the cost so far plus, for every unvisited city, half the sum of its two cheapest edges, or the reduced-cost-matrix bound used in many textbooks. Partial tours whose bound already exceeds the best tour found are pruned.

TSP is NP-hard: B&B makes it practical for moderate sizes, but no polynomial algorithm is known. A DP solution (Held–Karp) runs in O(n² · 2ⁿ), far better than O(n!).

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int n = 4;
int dist[4][4] = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
int best = INT_MAX;
vector<int> path, bestPath;
vector<bool> used(4, false);

void tsp(int city, int cost) {
    if (cost >= best) return;                         // bound: cannot beat the best tour
    if ((int)path.size() == n) {
        if (cost + dist[city][0] < best) { best = cost + dist[city][0]; bestPath = path; }
        return;
    }
    for (int next = 0; next < n; next++)
        if (!used[next]) {
            used[next] = true; path.push_back(next);
            tsp(next, cost + dist[city][next]);
            used[next] = false; path.pop_back();
        }
}

int main() {
    used[0] = true; path = {0};
    tsp(0, 0);
    cout << "shortest tour: " << best << " via";
    for (int c : bestPath) cout << " " << c;
    cout << " 0" << endl;
    return 0;
}

Output

shortest tour: 80 via 0 1 3 2 0

Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

1
When does branch and bound prune a node?
2
Which live-node structure does least-cost B&B use?
3
In knapsack B&B, the upper bound is computed using...
4
What is the brute-force complexity of TSP on n cities?

#Search strategies

#0/1 knapsack with B&B

#Travelling salesperson problem (TSP)

Test yourself

Search strategies

0/1 knapsack with B&B

Travelling salesperson problem (TSP)