If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

Question

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?

Let's take the Traveling Salesman Problem for example:

TSP Decision Problem (NP-Complete):
Input: Graph G, Budget b
Output: Does a route exist in G with a distance of at most b? (true/false)

TSP Optimization Problem (NP-Hard):
Input: Graph G
Output: What route in G has the shortest distance?

If one could find a polynomial time solution for the TSP Decision Problem wouldn't they also have a polynomial time solution for the TSP Optimization Problem?

Why? Binary search.

You can run your polynomial time solution for the TSP Decision Problem on G over and over with an input for b that increases, e.g. {1, 2, 4, 8, 16, 32, 64, 128, 256, ...}, until the algorithm returns false. Then you decrease b and slowly hone in on the correct answer.

Is this logic correct?

Answer 1

In this particular example, the following works: Let $A$ be the algorithm for deciding whether some graph $G$ has a TSP-route has a cost of at most $b$. We start by finding the optimal $b^\ast$ using $A$ and binary search on an appropriate range (say $[0, \sum_{e \in E(G)} w(e)]$) in polynomial time.

Following this, we start modifying the instance graph $G$ by setting edge weights to some large value so they will never be picked (e.g. $1 + b^\ast$) in a route of optimal cost $b^\ast$ and using $A$, we check whether the resulting graph still has a route of cost $b^\ast$. If that is the case, we keep the modification and otherwise we undo it. However, we now know that any such route (in the modified graph) must include the edge we messed with, so we store that. Successively applying this to all edges we will find at least one such edge per pass over $E(G)$ and after at most $|V(G)|$ passes, we will have found a TSP-route of cost $b^\ast$ consisting of the edges we stored.

Hence we call $A$ an polynomial ($O(|V(G)| \cdot |E(G)|)$, or if you want $O(|V(G)|^3$) amount of times (in the second step, the first one also takes polynomially many) and all of our other operations can also be easily done in polynomial time.

Therefore, we can solve the optimization problem in polynomial time if we have a polynomial-time algorithm for the decision variant.

This approach also works for other problems (with slight variations for the second part); in fact I am not aware of a problem where this general strategy fails. I am actually pretty sure that one can use it to recover an accepting path of a polynomially-bounded NTM which can then be used to solve optimization variants of all $\mathsf{NP}$-complete problems.