4.4 Article

Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem

Journal

INFORMS JOURNAL ON COMPUTING
Volume 19, Issue 1, Pages 36-51

Publisher

INFORMS
DOI: 10.1287/ijoc.1060.0181

Keywords

programming; integer; algorithms; branch and bound; programming; integer; algorithms; cutting plane; production-scheduling; cutting stock

Ask authors/readers for more resources

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 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 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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.4
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available