Decomposition Methods for Recursive Circle Packing

Speaker: 

Stephen Maher

Affiliation: 

Lancaster University

Date: 

Thu, 19/10/2017 - 11:00am

Venue: 

RC-4082, The Red Centre, UNSW

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.

Photo of Stephen Maher

To be confimed.

School Seminar Series: