Finding the optimum cost of a traveling salesman solution

Question

I'm working on this problem:

TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, 
if such a tour exists.

TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.

Now, the first thing that jumps to mind is that if I knew the cost of the optimal solution, I could just set b to that and voila. And, wouldn't you know it, elsewhere in my book it contains a hint for this very problem:

How do we find the optimum cost? Easy: by binary search.

I think I might be misunderstanding something very badly here. Binary search is meant to find the position of a given item in a sorted list. How exactly could that help me find the optimal cost? I'm genuinely confused. The authors don't elaborate any further, unfortunately.

The only other thing I might think of to solve this problem is to prove that they both reduce to another problem that is NP-complete, which I may end up doing, but still... this bugs me.

Answer 1

Assume that you have some lower bound l (e.g. 0) and upper bound u (e.g. the sum of all the edge weights). First, attempt to find a solution of total cost <= (l+u)/2. If you succeed, try again for a lower value: (3l+u)/4; if not, try for a higher value: (l+3u)/4.

I would call this a bisection method (Wikipedia) rather than binary search, but the idea is the same. We want to search some range for the optimal value, so we start in the middle and move up if we're too low and down if we're too high.