Branch and Bound and Exact Search

State-space trees, upper/lower bounds, incumbent solution, pruning correctness, 0/1 knapsack, assignment problem, traveling salesperson, and practical limits of exact exponential algorithms.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The bound is optimistic — the fractional-knapsack value is never below the best integer completion — so pruning a node whose bound cannot beat the incumbent never discards the optimum. A good first incumbent (from a greedy solution) and good branching order make the pruning far more effective; in the worst case the search is still exponential, which is why exact methods have practical size limits.

#include <bits/stdc++.h>
using namespace std;

struct Item { int w, v; };
vector<Item> items; int cap; long long best = 0, nodes = 0;
// optimistic bound: fill remaining capacity greedily, allowing a fraction of the next item
double bound(size_t i, int w, long long v) {
    double b = double(v); int room = cap - w;
    for (; i < items.size() && items[i].w <= room; ++i) { room -= items[i].w; b += items[i].v; }
    if (i < items.size()) b += double(items[i].v) * room / items[i].w;
    return b;
}
void bnb(size_t i, int w, long long v) {
    ++nodes;
    best = max(best, v);                                     // incumbent
    if (i == items.size() || bound(i, w, v) <= double(best)) return;   // prune: cannot beat the incumbent
    if (w + items[i].w <= cap) bnb(i + 1, w + items[i].w, v + items[i].v);
    bnb(i + 1, w, v);
}

int main() {
    mt19937 rng(19); int n = 40;
    for (int i = 0; i < n; ++i) items.push_back({int(rng() % 90 + 10), int(rng() % 90 + 10)});
    cap = 500;
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) { return (long long)a.v * b.w > (long long)b.v * a.w; });   // by ratio, for the bound
    bnb(0, 0, 0);
    vector<long long> dp(cap + 1,
…

40 items, capacity 500: branch and bound 1058, DP 1058
search nodes visited: 137 of 2^40 = 1099511627776 possible

Quiz

? Why is it safe to prune a node whose bound ≤ the incumbent's value?
+ The bound is an upper bound on every completion of that node, so none can beat the incumbent :: Optimistic bounds make pruning correct.
- Because the node is deep :: Depth is irrelevant.
- It is not safe :: It is, with a valid bound.
- Because the incumbent is optimal :: It may not be yet.

? What happens if the “bound” can underestimate the best completion?
+ Pruning may discard the optimum, giving a wrong answer :: Bounds must be optimistic.
- The search gets faster and stays correct :: Not guaranteed correct.
- Nothing :: It matters.
- It becomes DP :: No.

? Branch and bound visited far fewer than 2⁴⁰ nodes here. What limits exact search in general?
+ Its worst case is still exponential; good bounds and orderings only help on many inputs :: Practical limits remain.
- Memory only :: Time grows too.
- Nothing :: Some inputs defeat pruning.
- The compiler :: No.