Methods for improving the efficiency of Brute-force algorithm by the example of solving an Unbounded Knapsack Problem

Abstract

A universal method for the exact solution of discrete optimization problems, invariant to search conditions, is the exhaustive search algorithm (Brute Force Algorithm, BFA). Its wide use in practice is limited by the high computational complexity determined by the dimension of the search space. This determines the interest of researchers in finding approaches to limiting the number of considered solutions without losing its accuracy. The issue of increasing the efficiency of the brute force algorithm for solving discrete optimization problems is considered. On the example of the unbounded knapsack problem (Unbounded Knapsack Problem, UKP), we show the possibility of implementing a generator that ensures the exclusion of variants that do not satisfy the conditions of the problem, without calculating the criterion function. The feasibility of generators for multi-threaded BFA applications has also been evaluated. The effectiveness of the proposed approach is confirmed for both sequential and parallel implementations. The results of computational experiments coincide with theoretical calculations. A 4-thread application with an optimized generator provides more than 30-fold acceleration of calculations. The approach under study can be applied to other discrete optimization problems as well.