M.~Mesyagutov, G. Scheithauer, G.~Belov
New Constraint Programming Approaches for 3D Orthogonal Packing
We consider the 3D orthogonal feasibility problem (OPP-3). Given a set of rectangular items, OPP-3 is to decide whether all items can be orthogonally packed into the given rectangular container. The problem is considered without items rotation. We propose an approach based on the ideas of the known recent constraint programming (CP) approaches for OPP-2 and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules.
(Preprint MATH-NM-01-2012, TU Dresden, January. 2012)