The Branch-and-Bound Algorithm for the Traveling Salesman Problem is Not a Direct Algorithm

This article considers the concept of a linear separation direct algorithm introduced by V.A. Bondarenko in 1983. The concept of a direct algorithm is defined using the solution graph of a combinatorial optimization problem. The vertices of this graph are all feasible solutions of the problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct algorithms is that their complexity is bounded from below by the clique number of the solution graph. In 2015-2018, there were five articles published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. The thesis that the class of direct algorithms is broad and includes many classical combinatorial algorithms, including the branch-and-bound algorithm for the traveling salesman problem proposed by J.D.C. Little, K.G. Murty, D.W. Sweeney, and C. Karel in 1963, was the main motivation for these articles. We show that this algorithm is not a direct algorithm. Earlier, in 2014, the author of this article showed that the Hungarian algorithm for the assignment problem is not a direct algorithm. Therefore, the class of direct algorithms is not as broad as previously assumed.