Speaker
Eduard Vatutin
(Southwest State University)
Description
There is a fairly wide class of problems relating to discrete combinatorial optimization. Among them there are the problems of fundamental and applied orientation. The first one of them contains a number of problems on graphs, the problems of mathematical programming, operations research, etc. Many problems arise in the second direction of different fields of science (for example, trace interconnect for printed circuit boards and integrated circuits, economic planning, etc.) and can be reduced to problems of the first destinations with minor modifications.
Among a great deal of problems the most principal ones are within NP class which can’t be solved precisely using fast polynomial algorithms providing an optimal solution. For some problems with polynomial time complexity algorithms (for example, assignment problem solved by Hungarian algorithm) with increasing dimension the necessary costs of computing time also become prohibitive. The way out of this situation is the use of various heuristic methods that provide different quality of the obtained solutions and need different costs of computing time.
In light of recent development trends in computing and telecommunications the most actual direction is based on using parallel computing systems of different classes. Many iterative heuristic methods for solving combinatorial problems have good potential for parallelization that successfully allows their use in conjunction with parallel computing. A lot of iterative methods are weak binding that allows efficient use of grid systems with heterogeneous structure and weak communication subsystem.
Within voluntary distributed computing project Gerasim@home based on increasingly popular BOINC platform different computational experiments are produced aimed at finding out the optimal areas of applicability of various heuristics combinatorial optimization methods. Within the last two years calculations were performed which made it possible to determine the areas of applicability for a number of consecutive methods (S.I. Baranov method, method of parallel-sequential decomposition, method based on greedy adjacent strategy) to the problem of searching for separations of graph schemes of parallel algorithms arising during logical multicontrolles design. A strong dependence of solutions quality on the dimension of the problem and on the composition and strength of restrictions was shown. During the performed experiments borders of bend were obtained, which allowed to establish the boundaries of the insensitivity of different methods to different restrictions which made it possible to formulate a number of conclusions and recommendations for structural and parametric optimization of logic control systems. During the calculations within the project real performance made up about 2–2,5 TFLOPS that was provided by more than 1,300 volunteers from 69 countries, attracted more than 900 personal computers.
Currently the project studies a group of iterative methods, which include random and directed random searches, ant colony optimization and simulated annealing methods. These methods require at least by 1-2 orders more computing time costs because of the need to organize an iterative process. In addition, they have some specific features, for their studying the problem of finding the shortest path in a graph is used as a test one.
Work supported by the state assignment for the Southwest State University for 2014-2017, research number 2246, and by the scientific school НШ-2357.2014.8.
Primary author
Eduard Vatutin
(Southwest State University)
Co-author
Mr
Vitaly Titov
(Southwest State University)
