Decomposition Methods for Recursive Circle Packing

Abstract: 

Packing rings into a minimum number of rectangles is an optimization problem that appears naturally in the logistics operations of the tube industry. Considering each rectangle as a transportation container, minimal transportation costs are given by recursively packing rings into the smallest number of rectangles. No exact solution methods exist for the recursive circle packing problem (RCPP)---a more difficult variant of the circle packing problem---with the best heuristic algorithms only able to find solutions for small instances. A cutting stock formulation of the RCPP is described that reduces the difficulty of the problem that arises due to the recursive nature. An exact column generation algorithm is developed by applying a Dantzig-Wolfe reformulation to the cutting stock formulation of the RCPP. The exact column generation algorithm is demonstrated to outperform previous heuristic approches by providing improved upper bound solutions and strong lower bounds for a large collection of test instances.

Stephen is currently a research fellow in the Lancaster University Management School, United Kingdom, where he currently holds fellowship awarded by the EPSRC. Prior to Lancaster, Stephen was located at the Zuse Institute Berlin as a member of the development team for the mixed integer programming solver SCIP. This direction of research, using and developing SCIP, originated from his PhD studies at UNSW under the supervision of Professor Gary Froyland. Stephen was awarded his PhD in 2014.