On computing small variable disjunction branch-and-bound trees

This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and-bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjunctions: We show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2 1/5n in time O(2δn) with δ<15, unless the strong exponential time hypothesis fails. Similarly, for any ε>0, no polynomial time 2(1/2-ε)n-approximation is possible, unless P=NP. We also show that computing the size of a smallest branch-and-bound tree exactly is #P-hard. Similar results hold for estimating the size of the tree produced by branching rules like most-infeasible branching. Finally, we discuss that finding small branch-and-bound trees generalizes finding short treelike resolution refutations, and thus non-automatizability results transfer from this setting.