Geodesic
Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm
Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 1, pp. 72-85

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. The concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. The vertices of this graph are all feasible solutions of a 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 type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. The main motivation in these works is the thesis that the class of direct type algorithms is wide 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, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. Thus, the class of direct type algorithms is not so wide as previously assumed.
Keywords: branch and bound, traveling salesman problem, linear decision tree, clique number, direct type algorithm. 
@article{MAIS_2020_27_1_a5,
     author = {A. N. Maksimenko},
     title = {Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {72--85},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a5/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2020
SP  - 72
EP  - 85
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a5/
LA  - ru
ID  - MAIS_2020_27_1_a5
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm
%J Modelirovanie i analiz informacionnyh sistem
%D 2020
%P 72-85
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a5/
%G ru
%F MAIS_2020_27_1_a5
A. N. Maksimenko. Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm. Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 1, pp. 72-85. http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a5/