Published on 30 July 2019
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.
Categories: Articles, Technical-and-Technological-Issues-of-SDMT
Tags: глобально оптимальное решение, булевы переменные, композитные алгоритмы, динамическое программирование, методы типа ветвей и границ, экспериментальные исследования, задача о ранце.
ISSN 1998-4502 (Print) ISSN 2499-975Х (Online)