Clustering of situations in solving applied optimization problems (on the examples of traveling salesman problem and distance matrix recovery)

Abstract

In discrete optimization problems, we apply algorithms based on extensions of the branch and bound method. These extensions consist in the joint work of several auxiliary heuristic algorithms, they can be referred to different, independent from each other, areas of artificial intelligence. Therefore, the relevance of the problems under consideration is provided by both subject areas and algorithms. In this paper, we investigate the possibility of using one of these auxiliary algorithms, so-called clustering of situations. As the subject areas, we consider two different discrete optimization problems: the traveling salesman problem in its classical formulation (we prefer to study its special cases obtained for the pseudogeometric version) and the problem of DNA distance matrix reconstruction. As a result of computational experiments, we obtained some regularities that allow us to create improved versions of the branch and bound algorithm – by connecting heuristics to it for clustering situations. The results obtained in computational experiments provide a rationale for the application of clustering situations in the development of algorithms using the branch and bound method. For example, for the traveling salesman problem, this application gives easily observable improvements in the algorithm, primarily for the pseudogeometric version.