On computing small variable disjunction branch-and-bound trees
研究了最小分支定界树的计算问题，给出了变量分支下指数级下界，并证明了近似计算最小树大小的难度，除非强指数时间假设失败或P=NP。
Abstract 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 $$\smash {2^{\frac{1}{5}n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mpadded> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>5</mml:mn> </mml:mfrac> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mpadded> </mml:math> in time $$O(2^{\delta n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> with $$\delta <\tfrac{1}{5}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo><</mml:mo> <mml:mstyle> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>5</mml:mn> </mml:mfrac> </mml:mstyle> </mml:mrow> </mml:math> , unless the strong exponential time hypothesis fails. Similarly, for any $$\varepsilon > 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , no polynomial time $$\smash {2^{(\frac{1}{2} - \varepsilon )n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mpadded> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mpadded> </mml:math> -approximation is possible, unless $$\text {P} = \text {NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>P</mml:mtext> <mml:mo>=</mml:mo> <mml:mtext>NP</mml:mtext> </mml:mrow> </mml:math> . We also show that computing the size of a smallest branch-and-bound tree exactly is $${\#P} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>#</mml:mo> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> -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.