IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v284y2020i2d10.1007_s10479-018-3115-5.html
   My bibliography  Save this article

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

Author

Listed:
  • Ambros Gleixner

    (Zuse Institute Berlin)

  • Stephen J. Maher

    (Lancaster University)

  • Benjamin Müller

    (Zuse Institute Berlin)

  • João Pedro Pedroso

    (Universidade do Porto)

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.

Suggested Citation

  • Ambros Gleixner & Stephen J. Maher & Benjamin Müller & João Pedro Pedroso, 2020. "Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition," Annals of Operations Research, Springer, vol. 284(2), pages 527-555, January.
  • Handle: RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-3115-5
    DOI: 10.1007/s10479-018-3115-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-3115-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10479-018-3115-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    2. Castillo, Ignacio & Kampas, Frank J. & Pintér, János D., 2008. "Solving circle packing problems by global optimization: Numerical results and industrial applications," European Journal of Operational Research, Elsevier, vol. 191(3), pages 786-802, December.
    3. Mhand Hifi & Rym M'Hallah, 2009. "A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies," Advances in Operations Research, Hindawi, vol. 2009, pages 1-22, July.
    4. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    5. A. A. Farley, 1990. "A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems," Operations Research, INFORMS, vol. 38(5), pages 922-923, October.
    6. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    7. VANDERBECK, François & WOLSEY, Laurence A., 2010. "Reformulation and decomposition of integer programs," LIDAM Reprints CORE 2188, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    9. Vanderbeck, F. & Wolsey, L. A., 1996. "An exact algorithm for IP column generation," LIDAM Reprints CORE 1242, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. P. C. Gilmore & R. E. Gomory, 1965. "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, INFORMS, vol. 13(1), pages 94-120, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    2. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    3. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    4. Gondzio, Jacek & González-Brevis, Pablo & Munari, Pedro, 2013. "New developments in the primal–dual column generation technique," European Journal of Operational Research, Elsevier, vol. 224(1), pages 41-51.
    5. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    6. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    7. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    8. C Alves & J M Valério de Carvalho, 2008. "New integer programming formulations and an exact algorithm for the ordered cutting stock problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1520-1531, November.
    9. Wuttke, David A. & Heese, H. Sebastian, 2018. "Two-dimensional cutting stock problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(1), pages 303-315.
    10. Syam Menon & Rakesh Gupta, 2008. "Optimal Broadcast Scheduling in Packet Radio Networks via Branch and Price," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 391-399, August.
    11. Tolou Esfandeh & Rajan Batta & Changhyun Kwon, 2018. "Time-Dependent Hazardous-Materials Network Design Problem," Transportation Science, INFORMS, vol. 52(2), pages 454-473, March.
    12. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    13. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    14. Puchinger, Jakob & Raidl, Gunther R., 2007. "Models and algorithms for three-stage two-dimensional bin packing," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1304-1327, December.
    15. Muter, İbrahim & Sezer, Zeynep, 2018. "Algorithms for the one-dimensional two-stage cutting stock problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 20-32.
    16. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    17. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    18. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    19. Osman Ou{g}uz, 2002. "Generalized Column Generation for Linear Programming," Management Science, INFORMS, vol. 48(3), pages 444-452, March.
    20. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-3115-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.