?
Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма
Вестник Пермского университета. Серия: Математика. Механика. Информатика. 2016. Т. 4. № 35. С. 68-75.
Chusovliankin A., Morozenko V. V.
In this paper the new "anti-greedy" algorithm for the Traveling Salesman Problem is under investigation. The idea of "anti-greedy" algorithm is consequent elimination of the longest edges from graph according to two rules: every node of the graph should have two incident edges as a minimum; the graph should not have cycles with less than n edges. This algorithm finds out more exact solutions than famous polynomial algorithms, especially for non-Euclidean graphs.
V. V. Galatenko, Lebedev A. E., Nechaev I. N. et al., Bulletin of Experimental Biology and Medicine 2014 Vol. 156 No. 5 P. 706-709
The paper presents a formalized statement of the problem of selecting parameters and construction of a genomic classifier for medical test systemswith mathematical methods of machine learning without the use of biological and medical knowledge. A method is proposed to solve this problem. The results of testing the method using microarray datasets containing information on genome-wide transcriptome of the samples of estrogen positive breast ...
Added: October 28, 2015
Zhukova G., Ulyanov M., Fomichev M., Автоматика и телемеханика 2019 № 11 С. 155-172
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin-Kernighan-Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 10, 2019
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Added: March 22, 2020
Fomichev M., Ulyanov M., Головешкин В. А. et al., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
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 ...
Added: August 19, 2017
Maria K. Gordenko, Avdoshin S. M., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6-11
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 ...
Added: June 1, 2017
Chusovliankin A., Morozenko V. V., Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления 2016 № 20 С. 13-25
The optimal schedule, on the one hand, is a practical necessity to conserve resources, for example, problem in the multiprocessor computing systems. On the other hand, many of the scheduling problems are NP-hard and can not be solved exactly in polynomial time. Flow shop scheduling problem is the one of the most famous optimization problem. ...
Added: January 26, 2017
Ulyanov M., Fomichev M., Информационные технологии 2019 Т. 25 № 10 С. 590-595
The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in ...
Added: February 16, 2020
M.K. Gordenko, S.M. Avdoshin, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 107-122
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which ...
Added: September 27, 2017
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
Ulyanov M., Fomichev M., Головешкин В. А. et al., 2017 Т. 13 № 1 С. 19-24
The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions ...
Added: September 26, 2017
Voloshinov V., Smirnov S., Sukhoroslov O. V., Procedia Computer Science 2017 Vol. 108 P. 1532-1541
This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent ...
Added: August 30, 2018
Larisa Komosko, Mikhail Batsyn, Pablo San Segundo . et al., Journal of Combinatorial Optimization 2016 No. 4 P. 1665-1677
In this paper a fast greedy sequential heuristic for the vertex colouring problem is presented. The suggested algorithm builds the same colouring of the graph as the well-known greedy sequential heuristic in which on every step the current vertex is coloured in the minimum possible colour. Our main contributions include introduction of a special matrix ...
Added: July 13, 2015
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev et al., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296-1310
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Zhukova G., Ulyanov M., Fomichev M., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054-2067
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 24, 2019
Ekaterina N. Beresneva (Chirkova), Sergey M. Avdoshin, International Journal of Open Information Technologies 2017 Vol. 5 No. 5 P. 16-24
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 ...
Added: May 29, 2017
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46
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 ...
Added: November 5, 2016
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
Galatenko V. V., Лебедев А. Е., Нечаев И. Н. et al., Бюллетень экспериментальной биологии и медицины 2013 Т. 156 № 11 С. 654-660
В работе приводится формализованная постановка задачи об отборе параметров и построении классификатора для геномной медицинской тест–системы математическими методами машинного обучения без использования специальных биологических и медицинских знаний. Предлагается метод решения данной задачи и обсуждаются результаты апробации этого метода на мирочиповом наборе данных, содержащем информацию о полногеномном транскриптоме образцов эстрогенположительных опухолей молочной железы. Апробация показала, что ...
Added: October 28, 2015
Ulyanov M., Zhukova G., Fomichev M. et al., Автоматика и телемеханика 2018 № 7 С. 149-166
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Komosko L. F., Batsyn M. V., Информационные технологии 2015 № 7 С. 488-494
Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors. The graph coloring problem has a wide variety of applications including timetabling ...
Added: July 13, 2015
М. : Издательский центр «Российский государственный гуманитарный университет», 2019
Сборник включает 27 докладов международной конференции по компьютерной лингвистике и интеллектуальным технологиям «Диалог 2019», не вошедшие в ежегодник «Компьютерная лингвистика и интеллектуальные технологии», но рекомендованные Программным Комитетом к представлению на конференции. Для специалистов в области теоретической и прикладной лингвистики и интеллектуальных технологий. ...
Added: December 10, 2019
Karpov V. E., Karpova I. P., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Work solutions are proposed for problems of leader definition and role distribution in homogeneous groups of robots. It is shown that transition from a swarm to a collective of robots with hierarchical organization is possible using exclusively local interaction. The local revoting algorithm is central to the procedure for choice of leader while redistribution of roles can ...
Added: March 14, 2015
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. et al., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Added: January 27, 2014
Chuprikov P., Nikolenko S. I., Davydow A. et al., IEEE Transactions on Networking 2018 Vol. 26 No. 1 P. 342-355
Modern network elements are increasingly required to deal with heterogeneous traffic. Recent works consider processing policies for buffers that hold packets with different processing requirements (number of processing cycles needed before a packet can be transmitted out) but uniform value, aiming to maximize the throughput, i.e., the number of transmitted packets. Other developments deal with ...
Added: March 14, 2018