Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem

摘要

The two-dimensional bin-packing problem is the problem of orthogonally packing a given set of rectangles into a minimum number of two-dimensional rectangular bins. The problem is NT-hard and very difficult to solve in practice as no good mixed integer programming (MIP) formulation has been found for the packing problem. We propose an algorithm based on the well-known Dantzig-Wolfe decomposition where the master problem deals with the production constraints on the rectangles while the subproblem deals with the packing of rectangles into a single bin. The latter problem is solved as a constraint-satisfaction problem (CSP), which makes it possible to formulate a number of additional constraints that may be difficult to formulate as MIP models. This includes guillotine-cutting requirements, relative positions, fixed positions and irregular bins. The CSP approach uses forward propagation to prune inferior arrangements of rectangles. Unsuccessful attempts to pack rectangles into a bin are brought back to the master model as valid inequalities. Hence, CSP is used not only to solve the pricing problem but also to generate valid inequalities in a branch-and-cut system. Using delayed column-generation, we obtain lower bounds of very good quality in reasonable time. In all instances considered, we obtain similar or better bounds than previously published. Several instances with up to n = 100 rectangles are solved to optimality through the developed branch-and-price-and-cut algorithm.