Home > Research > Publications & Outputs > Price-and-verify

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition. / Gleixner, Ambros; Maher, Stephen; Muller, Benjamin et al.
In: Annals of Operational Research, Vol. 284, No. 2, 01.01.2020, p. 527-555.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Gleixner, A, Maher, S, Muller, B & Pedroso , JP 2020, 'Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition', Annals of Operational Research, vol. 284, no. 2, pp. 527-555. https://doi.org/10.1007/s10479-018-3115-5

APA

Gleixner, A., Maher, S., Muller, B., & Pedroso , J. P. (2020). Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition. Annals of Operational Research, 284(2), 527-555. https://doi.org/10.1007/s10479-018-3115-5

Vancouver

Gleixner A, Maher S, Muller B, Pedroso JP. Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition. Annals of Operational Research. 2020 Jan 1;284(2):527-555. Epub 2019 Dec 14. doi: 10.1007/s10479-018-3115-5

Author

Gleixner, Ambros ; Maher, Stephen ; Muller, Benjamin et al. / Price-and-verify : a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition. In: Annals of Operational Research. 2020 ; Vol. 284, No. 2. pp. 527-555.

Bibtex

@article{7f7d159253694f1f88b5149f5dfe83da,
title = "Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition",
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",
author = "Ambros Gleixner and Stephen Maher and Benjamin Muller and Pedroso, {Jo{\~a}o Pedro}",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/s10479-018-3115-5",
language = "English",
volume = "284",
pages = "527--555",
journal = "Annals of Operational Research",
publisher = "Springer",
number = "2",

}

RIS

TY - JOUR

T1 - Price-and-verify

T2 - a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition

AU - Gleixner, Ambros

AU - Maher, Stephen

AU - Muller, Benjamin

AU - Pedroso , João Pedro

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Mixed-integer nonlinear programming

KW - Dantzig–Wolfe decomposition

KW - Symmetry breaking

KW - Global optimization

KW - Recursive circle packing

U2 - 10.1007/s10479-018-3115-5

DO - 10.1007/s10479-018-3115-5

M3 - Journal article

VL - 284

SP - 527

EP - 555

JO - Annals of Operational Research

JF - Annals of Operational Research

IS - 2

ER -