Unit 7: Branch and Bound - Subjective Questions

Branch and Bound is a general algorithmic technique used to solve discrete and combinatorial optimization problems.

Its fundamental principles are:

• Branching: Divide the original problem into smaller subproblems represented by child nodes in a state-space tree.
• Bounding: Compute an optimistic bound on the best solution obtainable from each subproblem.
• Pruning: Discard a subproblem if its bound proves that it cannot improve the current best solution.
• Incumbent: Maintain the best feasible solution found so far.

For a maximization problem, a node with upper bound is pruned when , where is the value of the incumbent. For a minimization problem, a node with lower bound is pruned when , where is the incumbent cost.

The objective is to find an optimal solution without explicitly examining every possible solution.

A state-space tree represents all decisions that can be made while solving a problem.

• Root node: Represents the original problem before any decision has been made.
• Child node: Represents a subproblem formed by making one additional decision.
• Live node: A generated node whose children have not yet been explored and which may still lead to an optimal solution.
• E-node: The live node currently selected for expansion.
• Dead node: A node that will not be expanded because it is infeasible, non-promising, already solved, or completely explored.
• Solution node: A node corresponding to a complete feasible solution.

The algorithm repeatedly selects an E-node, branches from it, computes bounds for its children, and retains only promising children as live nodes.

A bounding function estimates the best objective value that can possibly be obtained from a node and all its descendants.

An effective bound should have the following properties:

• Admissibility: It must be optimistic. For maximization it must not underestimate the best attainable profit; for minimization it must not overestimate the least attainable cost.
• Tightness: It should be close to the actual optimum of the subproblem so that more nodes can be pruned.
• Efficiency: Its computation should be considerably cheaper than solving the subproblem exactly.
• Problem dependence: It should exploit the structure of the problem, often through a relaxation.
• Consistency where possible: Bounds should generally become no more optimistic as additional decisions are fixed.

There is a trade-off between tightness and computation time. A very weak bound causes excessive exploration, while an excessively expensive bound may eliminate the benefit of pruning.

The three methods differ mainly in how they select the next live node for expansion:

• FIFO Branch and Bound: Uses a queue and selects the oldest live node. It performs breadth-first exploration.
• LIFO Branch and Bound: Uses a stack and selects the most recently generated live node. It resembles depth-first exploration and usually requires less memory.
• Least-Cost Branch and Bound: Uses a priority queue and selects the live node with the most promising bound. For minimization, this is usually the node with the smallest lower bound; for maximization, it is usually the node with the largest upper bound.

Least-cost search often reaches a high-quality solution faster, but maintaining its priority queue adds overhead. All three methods can find the optimum when they use valid bounds and correct pruning rules.

Similarities:

• Both explore a state-space tree.
• Both construct solutions incrementally.
• Both prune subtrees that cannot contain a required solution.

Differences:

• Purpose: Backtracking is commonly used for feasibility and constraint-satisfaction problems, whereas Branch and Bound is primarily used for optimization.
• Pruning criterion: Backtracking prunes when a partial solution violates constraints. Branch and Bound additionally prunes by comparing an objective bound with the incumbent.
• Search order: Backtracking normally follows depth-first search. Branch and Bound may use FIFO, LIFO, or best-bound selection.
• Incumbent: Branch and Bound maintains the best feasible solution found so far; ordinary backtracking need not do so.
• Optimality: Branch and Bound proves optimality when no remaining live node can improve the incumbent.

Thus, Branch and Bound extends systematic tree search with objective-based bounds and optimality reasoning.

The general least-cost procedure is:

1. Create the root node and compute its lower bound.
2. Insert the root into a min-priority queue of live nodes.
3. Initialize the incumbent cost to unless a feasible solution is already known.
4. Remove the node with the smallest lower bound from the queue.
5. If its bound is at least the incumbent cost, prune it.
6. Otherwise, generate its children and process each child:
   • Discard it if it is infeasible.
   • If it is a complete feasible solution, update the incumbent when its cost is smaller.
   • If it is partial, calculate its lower bound and insert it only when the bound is smaller than the incumbent cost.
7. Continue until the queue is empty or its smallest bound is at least the incumbent cost.

When the algorithm terminates, the incumbent is optimal because every unexplored alternative has a lower bound no better than its cost.

A node can be made dead under the following conditions:

• Infeasibility: The partial decisions violate a constraint, so no descendant can be feasible.
• Bound domination: For maximization, prune when ; for minimization, prune when , where the starred value is the incumbent.
• Complete solution: A complete feasible node needs no further expansion, although it may update the incumbent.
• Dominance: Prune a state when another state is at least as good in every relevant respect and better in at least one respect.

These rules preserve optimality because they remove only subtrees that are infeasible or mathematically unable to improve the incumbent. Provided the bound is valid, an optimal solution cannot be hidden inside a node eliminated by bound domination. When no promising live nodes remain, the incumbent must therefore be globally optimal.

For items, let item have profit , weight , and decision variable .

The mathematical formulation is:

subject to

Here, is the knapsack capacity.

In the Branch and Bound tree:

• Level corresponds to the decision about item .
• The left branch commonly represents , meaning the item is included.
• The right branch represents , meaning the item is excluded.
• A node stores its level, accumulated weight, accumulated profit, and upper bound.
• A node is infeasible if its accumulated weight exceeds .
• A feasible node is pruned when its upper bound is not greater than the incumbent profit.

The tree has up to leaves, but effective bounds can prevent exploration of most of them.

First arrange items in non-increasing order of profit-to-weight ratio:

Suppose a node has current profit , current weight , and the next undecided item is . Its remaining capacity is .

To calculate the bound:

1. Set .
2. Add undecided items completely, in ratio order, while they fit.
3. If the next item does not fit, add the fraction that fills the remaining capacity:

This is an upper bound because it relaxes to . Fractional selection may produce a profit unavailable to the 0/1 problem, so it cannot be smaller than the best integral profit obtainable below the node.

The profit-to-weight ratios are , , , and , so the given order is suitable.

• The root fractional bound is
  
• A feasible solution containing items and has weight and profit . Set the incumbent to .
• If item is excluded, the fractional bound is
  
  so that subtree is pruned.
• If item is included and item is excluded, the bound is
  
  Including item gives profit with four capacity units left. Item cannot fit, so this branch finishes at .
• If items and are included, their weight is and profit is . Item cannot be included because the weight would become . Excluding it permits item , producing profit , which cannot improve the incumbent.

All other promising branches are either infeasible or have bounds at most . Therefore, the optimal selection is

with total weight and maximum profit

A typical knapsack node stores:

• Level: Index of the last item for which a decision has been made.
• Profit: Total profit of included items.
• Weight: Total weight of included items.
• Bound: Fractional upper bound on the profit obtainable from the node.
• Selection information: Decisions or a parent reference used to reconstruct the chosen items.

For a node at level , two children decide item :

• Include child: Its weight becomes and profit becomes . It is rejected if the new weight exceeds .
• Exclude child: Its weight and profit remain and , but item is permanently omitted.

A feasible child's bound is computed, and it becomes live only if its bound is greater than the current best profit.

Sorting by non-increasing is required to solve the fractional relaxation greedily. Selecting the highest-ratio items first produces the maximum possible fractional profit for the remaining capacity and therefore a valid, relatively tight upper bound.

Sorting does not alter the feasible subsets or the optimal value of the 0/1 problem. It only changes:

• The order in which decisions appear in the state-space tree.
• The order used to compute the fractional bound.
• Potentially, the number of nodes explored.

The original item indices should be retained so that the final selection can be reported correctly. Using an arbitrary order for fractional filling may produce a value below the true relaxed optimum, which could make the purported upper bound invalid and lead to incorrect pruning.

• Current profit : Profit already obtained from items fixed as included on the path to node . It is a feasible partial value if the node's weight does not exceed capacity.
• Incumbent profit : Highest profit of any complete or completable feasible 0/1 selection discovered so far. It is a lower bound on the unknown maximum optimum.
• Upper bound : Optimistic estimate of the maximum profit any descendant of could obtain, commonly calculated through fractional knapsack.

For a maximization problem, the relationship for a node containing an optimal descendant is generally

If , the node cannot produce a better solution and is pruned. Whenever a feasible selection with profit greater than is found, the incumbent is updated.

Given cities and travel costs , the Travelling Salesperson Problem (TSP) asks for a minimum-cost Hamiltonian cycle that visits every city exactly once and returns to the starting city.

Using binary variables , the objective is

subject to every city having exactly one outgoing and one incoming selected edge, together with constraints that eliminate subtours.

In a Branch and Bound tree:

• The root represents the original cost matrix or an empty partial tour.
• A branch may include or exclude an edge, or choose the next city in a partial route.
• Each node stores fixed decisions, a partial route or reduced matrix, and a lower bound.
• Infeasible nodes and nodes whose lower bounds are at least the incumbent tour cost are pruned.
• A complete feasible Hamiltonian cycle can update the incumbent.

The method terminates when no live node can produce a cheaper tour.

Cost-matrix reduction proceeds as follows:

1. Place on diagonal entries to forbid travel from a city to itself.
2. For every row, subtract its smallest finite value from all finite entries in that row. Add all row minima to the bound.
3. For every column of the row-reduced matrix, subtract its smallest finite value. Add all column minima to the bound.

If the total amount subtracted is , then is a lower bound on the cost of a tour. Every tour selects one entry from each row and one from each column, so it must incur at least the minima that were subtracted.

At a child node, the cost of a selected edge and any additional row or column reductions are added to the parent's bound. Rows and columns made unavailable by fixed decisions are removed or set to . Additional entries may also be forbidden to prevent premature subtours.

The row minima are , , , and , giving a row-reduction total of

After row reduction, the matrix is

The column minima are , , , and . Therefore, the total root lower bound is

Consider the tour

Its cost is

A feasible tour has been found whose cost equals the global lower bound. No tour can cost less than the lower bound, so this tour is optimal and

Suppose a selected branch includes edge . The corresponding child is constructed by:

• Adding the relevant reduced edge cost to the parent's bound.
• Setting row to because city cannot have another outgoing edge.
• Setting column to because city cannot have another incoming edge.
• Setting entry to to prevent an immediate two-city cycle.
• Forbidding any edge that would close a subtour before all cities are included.
• Reducing the remaining matrix and adding the new reduction cost to the bound.

An exclusion child may instead set and reduce the matrix again.

A child is pruned when it is infeasible, forms a premature subtour, has no possible incoming or outgoing edge for some city, or has a lower bound at least equal to the incumbent tour cost.

If the subtour-elimination constraints are removed from the TSP formulation, the remaining problem is an assignment problem: each city must have exactly one incoming and one outgoing edge.

Every Hamiltonian tour is a feasible assignment, but an assignment may consist of several disjoint cycles. Therefore:

• The assignment feasible set is larger than the TSP feasible set.
• Its minimum cost cannot exceed the minimum TSP tour cost.
• Its objective value is consequently a valid lower bound for TSP.

A minimum assignment containing multiple cycles is not a valid tour. Branch and Bound must eliminate such subtours by branching, adding forbidden edges, or imposing subtour-elimination constraints. Stronger relaxations that exclude more subtours generally produce tighter lower bounds, although they also cost more to compute.

Branch and Bound improves practical performance through pruning but does not remove worst-case exponential complexity.

• 0/1 knapsack: A binary decision tree may contain leaves and total nodes. Computing a bound can add polynomial work per node, although incremental implementations reduce this overhead.
• TSP: Enumerating city permutations can require candidate tours. Matrix-based bounding may require up to or more work per expanded node.
• Space: Breadth-first or best-bound search may retain an exponential number of live nodes. Depth-first variants generally use polynomial-depth storage, although auxiliary incumbent and bound data are still required.

Actual performance depends on bound tightness, search order, quality of the initial incumbent, instance structure, and branching strategy. Thus, Branch and Bound has exponential worst-case behavior but can solve many practical instances far faster than exhaustive enumeration.

Important efficiency strategies include:

• Obtain a strong initial incumbent: Use a greedy heuristic or local search so that weak nodes can be pruned early.
• Use tight bounds: Apply informative relaxations, while balancing bound quality against computation cost.
• Choose promising nodes first: Best-bound search may quickly find high-quality solutions and prove optimality sooner.
• Branch intelligently: Select decisions likely to divide the feasible region effectively or expose infeasibility early.
• Order choices well: In knapsack, consider high profit-to-weight items first; in TSP, explore low-cost edges first.
• Apply dominance rules: Eliminate states that are no better than already processed states.
• Reuse computations: Update weights, profits, bounds, and reduced matrices incrementally.
• Control memory: Use depth-first or hybrid strategies when the live-node queue becomes too large.

These strategies change practical running time substantially, although they do not improve the general exponential worst-case bound.