Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition

Ambros Gleixner (), Stephen J. Maher (), Benjamin Müller () and João Pedro Pedroso ()
Additional contact information
Ambros Gleixner: Zuse Institute Berlin
Stephen J. Maher: Lancaster University
Benjamin Müller: Zuse Institute Berlin
João Pedro Pedroso: Universidade do Porto

Annals of Operations Research, 2020, vol. 284, issue 2, No 4, 527-555

Abstract: 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 dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.

Keywords: Mixed-integer nonlinear programming; Dantzig–Wolfe decomposition; Symmetry breaking; Global optimization; Recursive circle packing (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-3115-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-3115-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-3115-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().