Branch-and-bound Method and Dynamic Programming Algorithms for Pseudo-polynomial Problems

This paper analyzed the branch and bound methods and the dynamic programming method using the example of the knapsack 0-1 problem. The modern state-of-the-art algorithms Minknap and Expknap were considered. An approach was also developed that allows you to combine the branch and bound method with dynamic programming methods and add caching of intermediate solutions for the branch and bound methods. This modification has been applied to the basic branch and bound method as well as the modern Expknap algorithm. Numerical experiments carried out on well-known benchmarks, as well as on randomly generated data, using 19 generation classes, show the effectiveness of the described algorithms. For specific parameters of the problem, it was established which of the proposed algorithms is the most optimal. In particular, with the help of modifications, it was possible to allow the Expknap algorithm to solve problems from certain classes that previously could not be solved in the allotted time.