Resource characteristics of ways to organize a decision tree in the branch-andboundmethod for the traveling salesmen problem

Business Informatics. 2015. No. 4 (34). P. 38–46.

Ulyanov M.V., Fomichev M.I.

The resource efficiency of different implementations of the branch-and-bound method for the classical traveling salesman problem depends, inter alia, on ways to organize a search decision tree generated by this method. The classic «time-memory» dilemma is realized herein either by an option of storing reduced matrices at the points of the decision tree, which leads to reduction in the complexity with additional capacity cost, or matrix recalculation for the current node, which leads to an increase in complexity while saving memory. The subject of this paper is an experimental study of temporal characteristics of solving the traveling salesman problem by the branch-and-bound method to identify a real reduction of span time using additional memory in a selected structure of a decision tree. The ultimate objective of the research is to formulate recommendations for implementing the method in practical problems encountered in logistics and business informatics. On the basis of experimental data, this paper shows that both considered options of the classic algorithm for the traveling salesman problem by the branch-and-bound method generate software implementations with an exponential dependence on the execution time of the input length. The experimental results permit us to suggest that the applicability of an additional memory capacity of no more than 1 GB results in a significant (up to five times) reduction of the time span. The estimate of the resulting trend makes it possible to recommend practical application of the software implementation of the branch-and-bound algorithm with storage of matrices - with a really available 16 GB random-access memory and with limitation of the expected average computation time of about one minute on modern personal computers whereby problems having a dimension no more than 70 can be solved exactly.

Keywords: экспериментальное исследование, branch and bounds method, метод ветвей и границ, experimental research, data structure, структуры данных, задача коммивояжера, Traveling Salesman Problem, time and memory efficiency, временная и емкостная эффективность