Approximate Packing Circles in a Rectangular Container: Valid Inequalities and Nesting

Abstract

A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aimis to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem hasnumerous applications in logistics, including production and packing for the textile, apparel, naval, automobile,aerospace and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problemwhich is solved by heuristic techniques combined with the local search procedures. A new formulation is proposedbased on using a regular grid approximated the container and considering the nodes of the grid as potential positionsfor assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimizationproblem. The binary variables represent the assignment of centers to the nodes of the grid. The resulting binaryproblem is then solved by the commercial software. Two families of valid inequalities are proposed to strengtheningthe formulation. Nesting circles inside one another is also considered. Numerical results are presented to demonstratethe efficiency of the proposed approach.