Branch and Bound: Best-First / DFS Relaxation Bounds for Combinatorial Optimization

1. Optimality Pruning via Admissible Relaxations

While backtracking targets feasibility (finding one or all valid configurations), Branch and Bound (B&B) targets combinatorial optimization: $\min_{x \in \mathcal{F}} f(x)$ (or $\max$). B&B maintains two quantities:

1. The Incumbent ($z^*$): The objective value of the best feasible complete solution found so far (initialized to $+\infty$ for minimization, or seeded via a fast greedy heuristic).
2. The Admissible Bound ($B(u)$): For any partial state (subproblem) $u$, we solve a relaxed problem $\mathcal{R}(u) \supseteq \mathcal{F}(u)$ that drops hard integrality or degree constraints so it can be solved in polynomial time.

2. Classic Relaxations & Search Strategies (DFS vs. Best-First)

• 0/1 Knapsack Upper Bound (Dantzig's LP Relaxation / Fractional Knapsack): Sort items by value-to-weight density $v_i / w_i$ descending. At node $u$ (having decided items $0..i-1$ with remaining capacity $C_{rem}$ and current value $V_{curr}$), greedily pack whole items $i, i+1, \dots$ until an item $k$ does not fit, then add the fractional slice $C_{rem} \cdot (v_k / w_k)$. This takes $O(\log N)$ time with prefix sums + binary search (or $O(N)$ linearly) and gives the exact Linear Programming relaxation upper bound $UB(u)$.
• Metric / General TSP Lower Bound:
  • Row/Column Matrix Reduction: Subtract the minimum of each uncovered row and column from the cost matrix; the sum of subtracted minimums is a valid lower bound on completing the tour.
  • Held-Karp 1-Tree Relaxation: Remove vertex $1$, compute a Minimum Spanning Tree (MST) on vertices $\{2..n\}$ plus the two cheapest edges incident to vertex $1$. Every Hamiltonian cycle is a 1-tree, so $\text{cost}(\text{1-Tree}) \le \text{OPT}_{\text{TSP}}$.
• Best-First (Least-Cost) vs. Depth-First B&B:
  • Best-First B&B: Expands the active node with the best bound $B(u)$ using a priority queue. Expands the minimum number of nodes with $B(u) < \text{OPT}$, but requires $O(|\text{Tree}|)$ heap memory and only finds complete solutions near the end.
  • DFS + Greedy Seeding: Uses $O(d)$ stack memory, updates the incumbent $z^*$ rapidly by exploring the greedy branch first, and avoids priority queue allocations.

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <vector>

struct KnapsackItem {
    long long weight;
    long long value;
};

// Exact 0/1 Knapsack via DFS Branch-and-Bound with O(log N) Fractional LP Upper Bound
long long knapsack_branch_and_bound(std::vector<KnapsackItem> items, long long capacity) {
    // 1. Sort items by value/weight ratio descending (cross-multiply to avoid float imprecision)
    std::sort(items.begin(), items.end(), [](const KnapsackItem& a, const KnapsackItem& b) {
        return static_cast<__int128>(a.value) * b.weight > static_cast<__int128>(b.value) * a.weight;
    });

    const int n = static_cast<int>(items.size());
    std::vector<long long> pref_w(n + 1, 0), pref_v(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref_w[i + 1] = pref_w[i] + items[i].weight;
        pref_v[i + 1] = pref_v[i] + items[i].value;
    }

    // O(log N) Dantzig Fractional Knapsack Upper Bound from index idx
    auto fractional_upper_bound = [&](int idx, long long curr_w, long long curr_v) -> double {
        long long rem_w = capacity - curr_w;
        long long target_pref_w = pref_w[idx] + rem_w;
        auto it = std::upper_bound(pref_w.begin() + idx, pref_w.end(), target_pref_w);
        int split = static_cast<int>(it - pref_w.begin()) - 1;

        double bound = static_cast<double>(curr_v + (pref_v[split] - pref_v[idx]));
        long long leftover_w = rem_w - (pref_w[split] - pref_w[idx]);
        if (split < n && leftover_w > 0) {
            bound += static_cast<double>(leftover_w) * items[split].value / items[split].weight;
        }
        return bound;
    };

    long long best_val = 0;

    auto dfs = [&](auto& self, int idx, long long curr_w, long long curr_v) -> void {
        if (curr_v > best_val) best_val = curr_v;
        if (idx == n) return;

        // Admissible Pruning: Since all values are integers, floor(UB) <= best_val cannot beat best_val
        if (static_cast<long long>(fractional_upper_bound(idx, curr_w, curr_v)) <= best_val) {
            return;
        }

        // Branch 1 (Greedy-First): Include items[idx] if it fits to raise best_val early
        if (curr_w + items[idx].weight <= capacity) {
            self(self, idx + 1, curr_w + items[idx].weight, curr_v + items[idx].value);
        }
        // Branch 2: Exclude items[idx] (re-check bound since best_val may have increased in Branch 1!)
        if (static_cast<long long>(fractional_upper_bound(idx + 1, curr_w, curr_v)) > best_val) {
            self(self, idx + 1, curr_w, curr_v);
        }
    };

    dfs(dfs, 0, 0, 0);
    return best_val;
}