Speaker
Eduard Vatutin
(Southwest State University)
Description
There is a well known extensive class of optimization problems where parameters are discrete variables. They include problems from graphs theory, scheduling, operations research and so on. One part of them named as hard solved problems and forming a NP complexity class can’t be solved precisely for reasonable computing time therefore in practice for their solving heuristic methods are used. At this moment the most popular and widely used in practice is the set of the following methods [1]: greedy methods, methods of restricted enumeration (or brute force with restricted depth of analyzed combinatorial tree, restricted number of its branches and so on), methods of random and weighted (directed) search, bioinspired methods (for example, methods of ants or bees colony), simulated annealing method, genetic (evolutionary) methods. Their modifications are well known corresponding, for example, to early clipping of unpromising solutions (branch and bound strategy), supporting combinatorial returns for breaking the deadlocks, changing order of selecting elements during decisions forming, etc.
Complexity of practice implementation, computing time costs and quality of decisions differ significantly both for different methods and for different conditions of its using. The set of some methods demands smart tuning of its numerical parameters performed during meta-optimization that is computing time intensive procedure. It is interesting to compare the quality of decisions and selecting subset of methods that are characterized by high convergence rate and provides getting decisions with the best quality for minimum computing time costs.
To find out the most promising methods well known discrete problem of getting shortest path in graph was selected. Its optimal decision can be found for squared time with using Dijkstra algorithm that makes it convenient to compare the quality of decisions of different heuristic methods with known optimum. For this reason corresponding computing unit was developed including program implementations of listed above methods and their modifications. For each method that has tuning parameters meta-optimization was performed (at this moment this stage performed in automatic mode and needs some tens of hours of computing time). After this computing unit was deployed within volunteer computing project Gerasim@Home at BOINC platform. With its using from April 2014 to June 2014 and from February 2015 to June 2015 a series of computing experiments was organized which aim to investigation quality decisions of heuristic methods for samples with random graphs with number of vertices N≤500 and density 0≤d≤1 and with fixed number of iterations.
As a result of experimental data analysis a set of conclusions was formulated. First, in this problem zone dependence is much weaker comparing to getting separations problem [2] that had been investigated earlier. The experimental dependences look like hyperbole in (N, d) coordinates that is consistent with the theoretical concepts. For high density graphs well known heuristic methods without modifications provide sufficient quality of decisions, the most promising of them are ant colony optimization method and genetic method. By decreasing density of graphs ant colony optimization method provides the best quality of solutions with support of combinatorial returns. Many well known heuristic methods which are successfully used in practice do not demonstrated high quality of decisions in this area. For example, simulated annealing method provides rare probability in finding correct decisions (paths) due to difficulties during modification of correct decision with saving its correctness; bee colony optimization method has strong dependence of tuning parameters on coordinates (N, d) that does not allow to select universal set of values of tuning parameters and forces to perform computing time complex meta-optimization by each use.
Formulated recommendations can be expanded in future and may be used for solving more complex discrete combinatorial optimization problems that have practice significance. In addition, in the perspective of further researches it is necessary to investigate time costs analysis and convergence rate analysis for set of listed above heuristic methods. According to these results it is possible to work out more complex multistage methods improving the given characteristics.
The work was performed within the base part of the state assignments for the Southwest State University in 2014–2017 number 2246 and under support of President grant MK-9445.2016.8. The authors would like to thank all volunteers who took part in the calculation within the distributed computing project Gerasim@Home. The authors also wish to thank Anna Vayzbina for assistance in preparing the English version of the article.
Bibliography
1. Vatutin E.I., Titov V.S., Emelyanov S.G. Basics of discrete combinatorial optimization (in Russian). M.: ARGAMAC-MEDIA, 2016. 270 p.
2. Vatutin E.I. Logic multicontrollers design. Getting separations of parallel graph-schemes of algorithms (in Russian). Saarbrucken: Lambert Academic Publishing, 2011. 292 p.
Primary author
Eduard Vatutin
(Southwest State University)
Co-authors
Mr
Sergey Valyaev
(BOINC.ru portal)
Mr
Vitaly Titov
(Southwest State University)
