The two-dimensional bin packing problem is the problem of orthogonally packing a given set of rectangels into the minimum number of two-dimensional rectangular bins. The problem is NP-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 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), where forward propagation is used to prune inferior arrangements of rectangles. Unsuccessful attempts to pack rectangles into a bin are canalized back to the master model as valid constraints. Hence, CSP is not only used 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. Computational results are reported showing, that we may solve quite large problems to optimality through the developed branch-and-price-and-cut algorithm.

The work is a practical study on merging techniques from MIP and CSP. Each solution techniques has its benefits and drawbacks, but decomposition techniques make it possible to use the techniques where most appropriate. Using failed attempts to solve a CSP problem to generate new valid inequalities leads to a tighter formulation of the MIP model, while the master MIP model makes it possible to define a pricing problem which can be solved through CSP.

This is joint work with Mikkel M. Sigurd.

Host: Jørgen Bang-Jensen