Using the Branch and Bound Method to Solve the Optimal Packaging Problem

This article is devoted to the theoretical study of the properties of discrete optimization problems, as well as methods of their effective implementation on modern multiprocessor computing systems and the experimental study of sequential and parallel variants of the dynamic programming algorithm for solving the optimal packaging problem. The developed approaches are focused on application in automation and control system of technological processes and productions to increase their efficiency. The optimal packing problem is one of the NP-hard combinatorial problems. The method of branch and bound has been developed and implemented in software for the classical problem of packing boxes, which is used in solving many practical problems, in particular, the problem of cutting the material, which is used in the process control system. The serial and parallel algorithms are implemented in C++ using the multithreading support provided by the C++ 11 standard.