The Travelling Salesman Problem (TSP) is a fundamental task in combinatorial optimization. A special case of the TSP is Metric TSP, where the triangle inequality holds. Solutions of the TSP are generally used for costs minimization, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. Since the TSP is NP-hard, heuristic algorithms providing near optimal solutions will be considered. The objective of this article is to find a group of Pareto optimal heuristic algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. Classification of algorithms for Metric TSP is presented. Feasible heuristic algorithms and their prior estimates are described. The data structure and the details of the research methodology are provided. Finally, results and prospective research are discussed.
The Mixed Chinese Postman Problem (MCPP) is to find a minimum shortest tour of given graph or multigraph traversed each edge or arc at least once. The problem is NP-hard. However, mixed case of the problem has many potentially useful applications, including delivering of something, robot exploration, web site usability, etc. In this article, we propose to solve the problem using the graph transformation and solving well-known Asymmetric Travelling Salesman Problem (ATSP). The algorithm for transforming the MCPP in multigraph into ATSP is pointed out.
In the paper we obtain an upper bound for the complexity of solving the subset sum problem which is a particular case of the knapsack problem by one of the variants of the branch-and-bound method with an additional pruning rule based on the comparison of the maximum and minimum number of items that can be put into the knapsack. As auxiliary results, we establish various combinatorial properties of subproblems processed for solving the subset sum problem by the considered variant of the branch-and-bound method.
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.
The complexity of solving a particular travelling saleman problem is studied. Complexity is a number of nodes of the decision tree, when a particular problem is being solved by the branch and bound algorithm. A probability distribution of the logarithm of the complexity of a particular TSP is approximately normal. Parameters of the linear transformation of a sample of the logarithm of the complexity into a standard normally distributed sample are obtained by the method of least squares for the sample quantiles. The formulas for the parameters are also given.
In this paper, we consider a method of storage, analysis and visualizing of large trees with the amount of 100 million nodes and more resulting in solving optimization problems by branch and bound algorithm. The solution provides a method for the collection of primary data from solver, analysis and processing of this data, as well as their subsequent visualization. The paper describes the architecture and basic software modules of the proposed solution.
This article is devoted to the mathematical formulation and numerical study of the spatial model of stationary biological communities by U. Dickman and R. Low. The main idea of this model is to find a "projection" of the simulated biological process on certain characteristics, the dynamics of which can be written analytically. Such "characteristics" in the Dickman’s and Low’s model are the so-called "spatial moments". A system of integro-differential equations is described describing the spatial dynamics in this model. The problem of moment’s closure of the third spatial moment, which relieves the system of an infinite number of equations is posed. Examples of closures of the third moment are written out, two of which, the so-called asymmetric and symmetric closures of the second degree, are studied in more detail. The problem is posed with a linear integral equilibrium’s equation, which is obtained by using an asymmetric closure. The shortcomings of the obtained model are explained, in connection with its biological interpretation, and also with the application of this closure in the study of the two-species model. Next, we formulate a nonlinear problem that arises when a symmetric parametric closure of the second degree is used, and its numerical study is car.