Unit 7: Branch and Bound

I. Orientation

Branch and Bound is a general exact optimization technique that searches a state-space tree while eliminating subtrees that cannot contain a better solution than the best one already known. Unlike exhaustive enumeration, it uses mathematically computed bounds to avoid exploring every candidate, but it still guarantees an optimal solution when its bounds and pruning rules are valid.

• Optimization setting: The method applies to discrete or combinatorial problems with an objective function to maximize or minimize, such as profit in 0/1 knapsack or tour cost in the travelling salesperson problem.
• State-space tree: Each node represents a partial solution; each branch represents a decision, such as including an item or selecting the next city.
• Branching: A problem is divided into smaller subproblems by fixing one or more decisions.
• Bounding: Each live node receives an optimistic estimate of the best objective value obtainable from its subtree.
  • For maximization, the bound is normally an upper bound.
  • For minimization, the bound is normally a lower bound.
• Incumbent: The best feasible solution found so far supplies a benchmark against which nodes are pruned.
• Pruning: A node is discarded if it is infeasible, already complete, or unable to improve the incumbent.
• Search discipline: Live nodes may be selected using FIFO, LIFO, or best-bound priority.
• Exactness: Pruning removes only subproblems that provably cannot produce a superior solution; therefore, the final incumbent is globally optimal.
• Worst-case behavior: The search may still examine exponentially many nodes, although effective bounds can greatly reduce practical work.

II. General Method — Systematic Optimization by Implicit Enumeration

A. General method

The general method repeatedly branches on unresolved decisions, computes bounds, and expands only nodes that remain capable of improving the incumbent.

• Node categories: The algorithm distinguishes nodes according to their search status.
  • A live node has been generated but not yet expanded.
  • An E-node is the live node currently being expanded.
  • A dead node will not be expanded because it is pruned or completely processed.
• Incumbent value: Let (z^) denote the objective value of the best feasible solution currently known. For maximization, larger values improve (z^); for minimization, smaller values improve it.
• Bound validity: Let (B(u)) be the optimistic bound for node (u).
  • In maximization, (B(u)) must be at least as large as the best feasible value attainable below (u).
  • In minimization, (B(u)) must be no larger than the best feasible cost attainable below (u).
• Maximization pruning rule: Node (u) is nonpromising when (B(u)\le z^*), because even its optimistic outcome cannot beat the incumbent.
• Minimization pruning rule: Node (u) is nonpromising when (B(u)\ge z^*).
• Generic procedure:

BRANCH-AND-BOUND(root):
    incumbent ← no feasible solution
    insert root into LIVE after computing its bound

    while LIVE is not empty:
        u ← select and remove a live node
        if u cannot improve incumbent:
            continue
        if u represents a complete feasible solution:
            update incumbent if u is better
            continue
        for each child v obtained by branching at u:
            if v is feasible:
                compute B(v)
                update incumbent if v supplies a better feasible solution
                if B(v) can still improve incumbent:
                    insert v into LIVE

    return incumbent

• Symbols and structures: (u) and (v) are state-space-tree nodes; (B(v)) is the bound of (v); LIVE stores generated promising nodes; incumbent stores the best complete feasible solution.
• Optimality at termination: When LIVE becomes empty, every unexplored subtree has either been proved inferior or infeasible, so no solution better than the incumbent remains.
• Search strategies:
  1. FIFO branch and bound: A queue expands nodes breadth-first. It is simple but may retain many nodes in memory.
  2. LIFO branch and bound: A stack performs depth-first search. It uses less memory and may find complete solutions early, but it does not prioritize strong bounds.
  3. Least-cost or best-bound search: A priority queue selects the most promising node—for example, the smallest lower bound in minimization. It often reduces expansions but has priority-queue overhead.
• Bound-quality trade-off: A tight bound causes more pruning but may be expensive to calculate; a weak bound is cheaper but leaves a larger search tree.

B. Applications and limitations

Branch and Bound is most useful when feasible solutions can be generated incrementally and optimistic bounds are substantially cheaper than complete enumeration.

• Typical applications: Concrete uses include integer programming, job scheduling, assignment, 0/1 knapsack, and travelling salesperson optimization.
• Feasibility pruning: A partial assignment violating a hard constraint can be killed immediately—for example, a knapsack node whose accumulated weight exceeds capacity (W).
• Dominance pruning: If one state is no better than another state with equal remaining choices, the dominated state can be discarded.
• Heuristic support: A quick heuristic may produce a strong initial incumbent; it does not affect exactness because only the validated bound controls pruning.
• Time complexity: With (n) binary decisions, the state-space tree can contain (2^{n+1}-1) nodes, giving exponential worst-case time.
• Space complexity: Best-first and breadth-first variants may store an exponential number of live nodes, whereas depth-first traversal usually stores only a path and pending siblings.
• Input sensitivity: Performance depends on decision ordering, bound tightness, and how quickly good feasible solutions are discovered.
• Correctness risk: An invalid optimistic bound may prune the subtree containing the true optimum; bounds must therefore favor unexplored possibilities rather than underestimate them in maximization or overestimate them in minimization.

III. 0/1 Knapsack — Maximizing Profit under Capacity

A. 0/1 knapsack problem

The 0/1 knapsack problem selects indivisible items to maximize total profit without exceeding a fixed weight capacity.

• Mathematical model: For (n) items, item (i) has profit (p_i), weight (w_i), and decision variable (x_i\in{0,1}).

maximize   Σ(i=1 to n) p_i x_i
subject to Σ(i=1 to n) w_i x_i ≤ W
           x_i ∈ {0,1}

• Symbol definitions: (W) is knapsack capacity; (x_i=1) includes item (i), while (x_i=0) excludes it; the two sums are total profit and total weight.
• Branching rule: At level (i), the left child commonly sets (x_i=1), while the right child sets (x_i=0). A complete root-to-leaf path fixes all (n) decisions.
• Item ordering: Items are sorted by nonincreasing profit density (p_i/w_i), which makes the fractional-knapsack upper bound as strong as possible for this relaxation.
• Upper bound: Starting from a node’s current profit and weight, add remaining items greedily by density; if the next item does not fit fully, add the fraction that fills the remaining capacity.
• Why the bound is valid: Fractional inclusion permits values (0\le x_i\le1), creating a relaxation whose optimum cannot be smaller than the integral 0/1 optimum.
• Promising test: For current best feasible profit (P^), expand node (u) only when (u) is weight-feasible and (B(u)>P^).
• Worked example: Let (W=16) and sorted items be ((p,w)=(40,2),(30,5),(50,10),(10,5)). At a node containing the first item, current profit is (40) and weight is (2). Item 2 fits, producing profit (70) and weight (7). Only (9) units remain, so (9/10) of item 3 contributes (45). Thus:

B(u) = 40 + 30 + (9/10)(50) = 115

• Interpretation: No legal 0/1 completion below this node can exceed profit (115). If the incumbent has profit at least (115), the node is safely pruned.

B. Applications and limitations

The knapsack formulation models all-or-nothing allocation, but Branch and Bound efficiency depends strongly on capacity and item structure.

• Applications: Examples include selecting projects under a budget, loading indivisible cargo, choosing advertisements within a time limit, and allocating memory to complete files.
• Early incumbent: Greedily packing whole items by (p_i/w_i) gives a feasible, though not necessarily optimal, profit that can strengthen initial pruning.
• Integrality distinction: The density-greedy rule solves fractional knapsack exactly but does not solve 0/1 knapsack exactly; here it supplies only an upper bound.
• Complexity: The full decision tree has (2^n) leaves, so worst-case running time remains (O(2^n)), excluding polynomial bound-computation factors.
• Weak-bound cases: If the fractional solution gains substantial value from splitting a high-profit item, its upper bound may greatly exceed every feasible integral completion.
• Alternative method: Dynamic programming can run in (O(nW)) time when integer capacity (W) is moderate, while Branch and Bound is not pseudo-polynomially tied to the numeric size of (W).

IV. Travelling Salesperson — Minimum-Cost Hamiltonian Tour

A. Travelling salesperson

The travelling salesperson problem seeks a minimum-cost tour that visits every city exactly once and returns to its starting city.

• Graph model: Given a weighted graph (G=(V,E)), each vertex is a city and edge cost (c_{ij}) is the travel cost from city (i) to city (j).
• Required solution: A tour is a Hamiltonian cycle, commonly written ((v_1,v_2,\ldots,v_n,v_1)), with cost:

C = Σ(i=1 to n-1) c[v_i, v_(i+1)] + c[v_n, v_1]

• Symbol definitions: (n=|V|) is the number of cities; (v_i) is the city in tour position (i); (c[a,b]) is the corresponding directed or undirected edge cost; (C) is total tour cost.
• Branching rule: A node represents a partial tour. Its children append one unvisited city, while infeasible repetitions and premature cycles are rejected.
• Incumbent: Any complete tour provides an upper bound (C^*) on the optimal minimum cost; a nearest-neighbor tour can supply the initial incumbent.
• Lower-bound principle: A partial tour’s committed edge costs are combined with an optimistic estimate of the edges still required to complete a cycle.
• Reduced-matrix bound: Place edge costs in a matrix, set forbidden edges to infinity, subtract each finite row minimum and then each finite column minimum. The total reductions form a lower bound.
• Matrix branching: Choosing edge ((i,j)) forbids other outgoing edges from (i), other incoming edges to (j), and any edge that would create a smaller cycle before all cities are included; the matrix is then reduced again.
• Pruning rule: If node (u) has lower bound (L(u)\ge C^*), no completion can improve the incumbent, so (u) becomes dead.
• Alternative bound: For symmetric TSP, the cost of a minimum spanning tree on unvisited cities, plus inexpensive connections to the partial tour’s endpoints, gives another valid lower bound.

B. Applications and limitations

The TSP model supports route and ordering decisions, although its factorial search space makes effective bounds essential.

• Applications: Concrete variants arise in vehicle routing, circuit-board drilling, robotic tool movement, warehouse picking, and sequencing DNA fragments by pairwise transition cost.
• Symmetry reduction: Fixing one starting city removes rotational duplicates; for symmetric costs, treating a tour and its reverse as equivalent removes another factor of two.
• Search size: Fixing the start leaves ((n-1)!) possible directed tours; symmetric TSP has ((n-1)!/2) distinct tours.
• Bound strength: Row-and-column reduction is inexpensive and useful for assignment-style reasoning, but it may permit disconnected subtours and thus underestimate the true tour cost substantially.
• Best-first behavior: Expanding the node with the smallest (L(u)) focuses on apparently cheapest completions, but storing its priority queue can require large memory.
• Exactness and scalability: Branch and Bound returns an optimal tour when allowed to finish, yet worst-case time remains exponential; large instances often require stronger relaxations, cutting constraints, or approximate heuristics.