On the Hardness of Almost All Subset Sum Problems by Ordinary Branch-and-Bound

Abstract

Given $n$ positive integers $a_1,a_2,\dots ,a_n$, and a positive integer right hand side $\beta$, we consider the feasibility version of the subset sum problem which is the problem of determining whether a subset of $a_1,a_2,\dots ,a_n$ adds up to $\beta$. We show that if the right hand side $\beta$ is chosen as $\lfloor r{\sum }_{j=1}^n{a}_j\rfloor$ for a constant $0<r<1$ and if the $a_j$'s are independentand identically distributed from a discrete uniform distribution taking values $1,2,\dots ,\lfloor 10^{n/2}\rfloor$, then the probability that the instance of the subset sum problem generated requires the creation of an exponential number of branch-and-bound nodes when one branches on the individual variables in any order goes to $1$ as $n$ goes to infinity.

arXiv comment5 pages