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
| # | Question | Official answer |
|---|---|---|
| 6 | Which 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 enumerates single tours until it must. The search tree partitions the set of all tours: the root holds every tour, and each edge taken fixes one more city-to-city link, splitting a node's tour-set into subsets. 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 the 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?
Options:
| Option | Verdict |
|---|---|
| A — Root represents all possible tours | True: before any constraint is imposed, every permutation of cities is still a candidate |
| B — Root represents the shortest/optimal tour | False: if the root already isolated the optimum there would be nothing to search; the root cannot know which tour is best |
| C — Each node represents a set of tours | True: a node = all tours agreeing with the choices (edges fixed/forbidden) on the path from the root |
| D — Each node represents a single tour | False: single tours appear only at the leaves, after every city placement has been pinned down |
| E — Node costs monotonically INCREASE root to leaf | True: child sets ⊆ parent set, and a lower bound over a smaller set is ≥ the parent's bound |
| F — Node costs monotonically DECREASE root to leaf | False: it is exactly the opposite; decreasing bounds could never prune anything |
Answer: A, C, E
Why these three hold together
A–C describe the structure, E the arithmetic that makes pruning legal:
- Root = → A.
- Branching on "which city follows city 1" splits this set into disjoint subsets; deeper nodes carry tighter constraints but still many tours → C, not D.
- Bound(child) = min cost over a subset ≥ Bound(parent) = min over the superset → E, not F.
- Pruning rule "discard node if its bound ≥ cost of best complete tour found" is valid because of E: nothing inside a pruned subtree can beat the incumbent. B and F would invert this logic and break the algorithm.
Tricks & Tips
Answers: 6 A, C, E