Packing in two and three dimensions

This dissertation investigates Multidimensional Packing Problems (MD-PPs): the Pallet Loading Problem (PLP), the Multidimensional Knapsack Problem (MD-KP), and the Multidimensional Bin Packing Problem (MD-BPP). In these problems, there is a set of items, with rectangular dimensions, and a set of large containers, or bins, also with rectangular dimensions. Items cannot overlap (share the same region in space), and, when packed, must be completely located within the bin. We develop new theory for PLP, and apply it to the construction of new bounds, heuristics, and an exact algorithm. The bounds verify that the heuristics optimally solve 99.999% of PLP instances with up to 100 items; in the instances that the heuristics fail to solve optimally, their best solution differs from the optimum by only one item. Using our new PLP theory, we implement algorithms to solve orthogonal non-guillotine MD-KP instances and are the first to obtain exact solutions for some instances from the literature. Using these MD-KP algorithms, we develop the first exact algorithm for the orthogonal nonguillotine MD-BPP and are the first to obtain exact solutions to several instances from the literature.