Q6 — SEARCH FOR OPTIMAL SOLUTION

In TSP Branch-and-Bound the root is every tour at once, each node is a set of tours, and bounds only ever grow on the way down.

The Question

#QuestionOfficial answer
6Which of the following are true about the Branch-and-Bound method (discussed in the lecture) that is used for finding optimal tours for the Traveling Salesman Problem?A, C, E

The Topic in 60 Seconds

TSP Branch-and-Bound never commits to single tours until it must. The search tree partitions the set of all tours: the root holds every tour, and each branch taken fixes one more city-to-city link. A node's cost is a lower bound over all tours inside its set — so as you descend and sets shrink, the bound can only rise toward true tour lengths.

Deep-dive: browse the Concepts section for Branch-and-Bound.

Solutions

6 — True statements about lecture-style BnB for optimal TSP tours?

OptionVerdict
A — Root represents all possible toursTrue: before any constraint is imposed, every permutation of cities is still a candidate
B — Root represents the shortest/optimal tourFalse: if the root already isolated the optimum there would be nothing to search
C — Each node represents a set of toursTrue: a node = all tours agreeing with the edge choices on the path from the root
D — Each node represents a single tourFalse: single tours appear only at the leaves, after every city placement is pinned down
E — Node costs monotonically INCREASE root to leafTrue: child sets ⊆ parent set; a lower bound over a smaller set is ≥ the parent's bound
F — Node costs monotonically DECREASE root to leafFalse: exactly backwards; decreasing bounds could never prune anything

Answer: A, C, E

Why these three hold together

  1. Root = {\{ all (n−1)!(n-1)! tours }\} → A, and not B (the search exists precisely because the optimum is not known up front).
  2. Branching on "which city follows city ii" splits a tour-set into disjoint subsets; deeper nodes still contain many tours → C, not D.
  3. Bound(child)=min⁡\text{Bound}(\text{child}) = \min over a subset ≥Bound(parent)=min⁡\ge \text{Bound}(\text{parent}) = \min over the superset → E, not F.
  4. Pruning ("discard node if bound ≥ cost of best complete tour so far") is legal because of E: nothing inside a pruned subtree can beat the incumbent.

Tricks & Tips

Answers: 6 A, C, E