Optimization Online


Exact Methods for Recursive Circle Packing

Ambros Gleixner(gleixner***at***zib.de)
Stephen Maher(maher***at***zib.de)
Benjamin Müller(benjamin.mueller***at***zib.de)
João Pedro Pedroso(jpp***at***ncc.up.pt)

Abstract: Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first exact method for solving RCPP, based on a Dantzig-Wolfe decomposition of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating all so-called one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We propose a branch-and-price algorithm to solve the reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes exact dual bounds, but often produces primal solutions better than computed by heuristics from the literature.

Keywords: mixed-integer nonlinear programming; Dantzig-Wolfe Decomposition; symmetry breaking; global optimization; recursive circle packing

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: urn:nbn:de:0297-zib-62039, Zuse Institute Berlin, February 2017

Download: [PDF]

Entry Submitted: 02/24/2017
Entry Accepted: 02/24/2017
Entry Last Modified: 02/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society