Improving Exact Methods for Solving 3D Cutting and Packing Problems

3D Cutting and Packing Problems consist of a set of boxes, which must be placed inside one or more larger cuboids, referred to as containers. The primary constraints associated with these problems concern non-overlapping and how the boxes to be placed must fit entirely inside the container. Additional constraints such as rotations may also be included. Different characteristic combinations give rise to different problem variants. This work considers a subset of these variants, known as output maximization problems. The tackled problems consist of a set of items to be placed inside a single container with the objective being to maximize the value of the placed boxes. Given their combinatorial nature, these problems are known to be challenging and, consequently, most research in the literature addresses them heuristically in hopes of generating good quality solutions within a short amount of time. The ambition of this work is to better clarify the difficulties of solving these problems with exact methods. Different improved techniques such as specialized branch and bound, MIP formulations and lazy constraints were tested and results demonstrate their performance on both instances from the literature and newly-generated benchmark instances compared against existing exact methods. These results further contribute towards gaining insight on solving these problems, technique improvements and development of new formulations.status: publishe