Analysis of the Effectiveness of a New Composite Method Joining Features of Implicit and Modular Enumeration Algorithms

A new method of searching for globally optimal solutions of discrete programming problems is proposed, which combines the components of search strategies by modular enumeration, backtracking, and dynamic programming. Analytical and experimental results of the analysis of its comparative efficiency in relation to backtracking search solving the knapsack problem are presented. It has been experimentally proven that, unlike the modular enumeration method and one of its varieties - the “meet in the middle” algorithm, the optimal number of modules of the proposed approach is not a constant, it increases with the number of variables of the problem being solved. Its high operational characteristics have been experimentally confirmed: a relatively low solution search time and low requirements for the amount of RAM. In the general case, we can say that the higher efficiency of this approach compared to the exhaustive or implicit enumeration methods increases with the complexity of the problem it solves.