We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of black-box search-to-decision reductions, which we call branch-and-bound reductions (in analogy with branch-and-bound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to $h_f : \mathcal{S} \to \mathbb{R}_{\geq 0}$ satisfying
$$
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot \min_{x \in S} f(x)
$$
for some $\gamma \geq 1$ and any subset $S$ in some allowed class of subsets $\mathcal{S}$ of the domain $D$. (When the goal is to maximize $f$, $h_f$ instead yields an approximation to the maximal value of $f$ over $S$.) We show tight upper and lower bounds on the number of queries~$q$ needed to find even a $\gamma'$-approximate minimizer (or maximizer) for quite large $\gamma'$ in a number of interesting settings, as follows.

- For arbitrary functions $f : \{0,1\}^n \to \mathbb{R}_{\geq 0}$, where $\mathcal{S}$ contains all subsets of the domain, we show that no branch-and-bound reduction can achieve $\gamma' \lesssim \gamma^{n/\log q}$, while a simple greedy approach achieves essentially $\gamma^{n/\log q}$.

- For a large class of MAX-CSPs, where $\mathcal{S} := \{ S_w\}$ contains each set of assignments to the variables induced by a partial assignment $w$, we show that no branch-and-bound reduction can do significantly better than essentially a random guess, even when the oracle $h_f$ guarantees an approximation factor of $\gamma \approx 1+\sqrt{\log(q)/n}$.

- For the Traveling Salesperson Problem (TSP), where $\mathcal{S} := \{S_p\}$ contains each set of tours extending a path $p$, we show that no branch-and-bound reduction can achieve $\gamma' \lesssim (\gamma-1) n/\log q$. We also prove a nearly matching upper bound in our model.

These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) We also note two alternative interpretation of our results. First, if we view $h_f$ as a data structure, then our results unconditionally rule out black-box search-to-decision reductions for certain data structure problems. Second, if we view $h_f$ as an efficiently computable heuristic, then our results show that any reasonably efficient branch-and-bound algorithm requires more guarantees from its heuristic than simply the approximation guarantee shown above.

Behind our results is a ``useless oracle lemma,'' which allows us to argue that under certain conditions the oracle $h_f$ is ``useless,'' and which might be of independent interest.

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying
\[
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot \min_{x \in S} f(x)
\]
for some $\gamma \geq 1$ and any subset $S$ in some allowed class of subsets $\mathcal{S}$ of the domain $D$. We show tight upper and lower bounds on the number of queries $q$ needed to find even a $\gamma'$-approximate minimizer for quite large $\gamma'$ in a number of interesting settings, as follows.

- For arbitrary functions $f : \{0,1\}^n \to \mathbb{R}_{\geq 0}$, where $\mathcal{S}$ contains all subsets of the domain, we show that no branch-and-bound algorithm can achieve $\gamma' \approx\gamma^{n/\log q}$, while a simple greedy algorithm achieves essentially $\gamma^{n/\log q}$.

- For a large class of MAX-CSPs, where $\mathcal{S} := \{ S_w\}$ contains each set of assignments to the variables induced by a partial assignment $w$, we show that no branch-and-bound algorithm can do significantly better than essentially a random guess, even for $\gamma \approx 1+\sqrt{\log(q)/n}$.

- For the Traveling Salesperson Problem (TSP), where $\mathcal{S} := \{S_p\}$ contains each set of tours extending a path $p$, we show that no branch-and-bound algorithm can achieve $\gamma' \approx (\gamma-1) n/\log q$. We also prove a nearly matching upper bound in our model.

Behind these results is a "useless oracle lemma," which allows us to argue that under certain conditions the heuristic $h_f$ is "useless," and which might be of independent interest.

We also note two alternative interpretations of our model and results. If we interpret the heuristic $h_f$ as an oracle for an approximate decision problem, then our results unconditionally rule out a large and natural class of approximate search-to-decision reductions (which we think of as "branch-and-bound" search-to-decision reductions). We therefore show an oracle model in which approximate search and decision are strongly separated. (In particular, our lower bound for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) By instead interpreting $h_f$ as a data structure, we see that our results unconditionally rule out black-box search-to-decision reductions for data structures.