Search
You are here: Articles
Articles

Published on 30 July 2019

EXPERIMENTAL ANALYSIS OF THE COMPOSITE VERSIONS EFFECTIVENESS OF THE IMPLICIT ENUMERATION METHODS FOR EXTREMAL PROBLEMS RAPID SOLUTIONS

V.O. Grоppen, A.А. Datiev, K.V. Panovskaya

Natural and man-made disasters in the mountains (avalanches, mudflows, dams, etc.) are characterized by rapid developments, leaving little time for decision-making. A number of problems arising in this case can be reduced to the mathematical models with discretely varying variables, the main tool for solving them are implicit enumeration methods. The composite modifications efficiency of dynamic programming and methods such as branches and boundaries in relation to the knapsack problem is experimentally investigated. All these algorithms combine the technologies of calculation of estimates inherent in the methods of branch type and boundaries and the principles of cutting off "unpromising" dynamic programming plans. The high efficiency of the proposed approaches is demonstrated experimentally and it is shown that the superiority of composite versions of implicit enumeration algorithms over traditional implementations of these methods increases with the growth of the knapsack problem dimension.

CityVladikavkaz
CountryRussia
UDC004.421.5
Issue2019, № 2 (Т. 11)
Key wordsglobally optimal solution, Boolean variables, composite algorithms, dynamic programming, branch and boundary type methods, experimental studies, knapsack problem.
Number of views (149)

Categories: Articles, Technical-and-Technological-Issues-of-SDMT

Tags: глобально оптимальное решение, булевы переменные, композитные алгоритмы, динамическое программирование, методы типа ветвей и границ, экспериментальные исследования, задача о ранце.

Print
SEARCH (ON AUTHORS OR ARTICLES)
Search the Issue

ISSN 1998-4502 (Print)                                                            ISSN 2499-975Х (Online)