{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:28:36Z","timestamp":1762298916848,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,12,14]],"date-time":"2018-12-14T00:00:00Z","timestamp":1544745600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s10479-018-3115-5","type":"journal-article","created":{"date-parts":[[2018,12,14]],"date-time":"2018-12-14T08:09:17Z","timestamp":1544774957000},"page":"527-555","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Price-and-verify: a new algorithm for recursive circle packing using Dantzig\u2013Wolfe decomposition"],"prefix":"10.1007","volume":"284","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0391-5903","authenticated-orcid":false,"given":"Ambros","family":"Gleixner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen J.","family":"Maher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4463-2873","authenticated-orcid":false,"given":"Benjamin","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1298-7191","authenticated-orcid":false,"given":"Jo\u00e3o Pedro","family":"Pedroso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,14]]},"reference":[{"key":"3115_CR1","unstructured":"Achterberg, T. (2007). Constraint integer programming. Ph.D. thesis, Technische Universit\u00e4t Berlin."},{"issue":"1\u20132","key":"3115_CR2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10107-014-0761-5","volume":"149","author":"M Bergner","year":"2015","unstructured":"Bergner, M., Caprara, A., Ceselli, A., Furini, F., L\u00fcbbecke, M. E., Malaguti, E., et al. (2015). Automatic Dantzig\u2013Wolfe reformulation of mixed integer programs. Mathematical Programming, 149(1\u20132), 391\u2013424.","journal-title":"Mathematical Programming"},{"key":"3115_CR3","unstructured":"Castillo, I., Kampas, F. J., & Pint\u00e9r, J. D. (2008). Solving circle packing problems by global optimization: Numerical results and industrial applications. European Journal of Operational Research191(3), 786\u2013802. \nhttp:\/\/EconPapers.repec.org\/RePEc:eee:ejores:v:191:y:2008:i:3:p:786-802\n\n."},{"key":"3115_CR4","unstructured":"COIN-OR: CppAD, a package for differentiation of CPP Algorithms. \nhttp:\/\/www.coin-or.org\/CppAD\n\n. Accessed 2014."},{"key":"3115_CR5","unstructured":"COIN-OR: Ipopt, Interior point optimizer. \nhttp:\/\/www.coin-or.org\/Ipopt\n\n. Accessed 2016."},{"issue":"1-2","key":"3115_CR6","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.dam.2012.07.020","volume":"161","author":"Alberto Costa","year":"2013","unstructured":"Costa, A., Hansen, P., & Liberti, L. (2013). On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square. Discrete Applied Mathematics, 161(1\u20132), 96\u2013106. \nhttps:\/\/doi.org\/10.1016\/j.dam.2012.07.020\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X12002855\n\n.","journal-title":"Discrete Applied Mathematics"},{"key":"3115_CR7","doi-asserted-by":"crossref","unstructured":"Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research8(1), 101\u2013111. \nhttp:\/\/www.jstor.org\/stable\/167547\n\n.","DOI":"10.1287\/opre.8.1.101"},{"key":"3115_CR8","unstructured":"Demaine, E. D., Fekete, S. P., & Lang, R. J. (2010). Circle packing for origami design is hard. arXiv preprint \narXiv:1008.1224\n\n."},{"key":"3115_CR9","volume-title":"Column generation","author":"G Desaulniers","year":"2006","unstructured":"Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2006). Column generation (Vol. 5). Berlin: Springer."},{"issue":"3","key":"3115_CR10","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1023\/A:1007606007369","volume":"31","author":"M Dror","year":"1999","unstructured":"Dror, M. (1999). Polygon plate-cutting with a given order. IIE Transactions, 31(3), 271\u2013274. \nhttps:\/\/doi.org\/10.1023\/A:1007606007369\n\n.","journal-title":"IIE Transactions"},{"issue":"5","key":"3115_CR11","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1287\/opre.38.5.922","volume":"38","author":"AA Farley","year":"1990","unstructured":"Farley, A. A. (1990). A note on bounding a class of linear programming problems, including cutting stock problems. Operations Research, 38(5), 922\u2013923. \nhttps:\/\/doi.org\/10.1287\/opre.38.5.922\n\n.","journal-title":"Operations Research"},{"key":"3115_CR12","unstructured":"Fortz, B., Labb\u00e9, M., & Poss, M. (2010). A branch-and-cut-and-price framework for convex MINLP applied to a stochastic network design problem. In Workshop on mixed integer nonlinear programming (p. 131)."},{"key":"3115_CR13","unstructured":"Gamrath, G. (2010). Generic branch-cut-and-price. Master\u2019s thesis."},{"key":"3115_CR14","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"P Gilmore","year":"1961","unstructured":"Gilmore, P., & Gomory, R. (1961). A linear programming approach to the cutting stock problem. Operations Research, 9, 849\u2013859.","journal-title":"Operations Research"},{"issue":"1","key":"3115_CR15","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1287\/opre.13.1.94","volume":"13","author":"P Gilmore","year":"1965","unstructured":"Gilmore, P., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1), 94\u2013120.","journal-title":"Operations Research"},{"key":"3115_CR16","unstructured":"Hales, T. C., Adams, M., Bauer, G., Dang, D. T., Harrison, J., Hoang, T. L., Kaliszyk, C., Magron, V., McLaughlin, S., Nguyen, T. T., Nguyen, T. Q., Nipkow, T., Obua, S., Pleso, J., Rute, J., Solovyev, A., Ta, A. H. T., Tran, T. N., Trieu, D. T., Urban, J., Vu, K. K., & Zumkeller, R. (2015). A formal proof of the Kepler conjecture. \narXiv:1501.02155\n\n."},{"key":"3115_CR17","unstructured":"Hifi, M., & M\u2019Hallah, R. (2009). A literature review on circle and sphere packing problems: Models and methodologies. Advances in Operations Research, 150, 624:1\u2013150, 624:22. \nhttp:\/\/dblp.uni-trier.de\/db\/journals\/advor\/advor2009.html#HifiM09\n\n."},{"key":"3115_CR18","unstructured":"ILOG, Inc: ILOG CPLEX: High-performance software for mathematical programming and optimization. See \nhttp:\/\/www.ilog.com\/products\/cplex\/\n\n. Accessed 2016."},{"issue":"1","key":"3115_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1287\/ijoc.1080.0283","volume":"21","author":"R Jans","year":"2009","unstructured":"Jans, R. (2009). Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints. INFORMS Journal on Computing, 21(1), 123\u2013136.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"3115_CR20","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10898-007-9274-6","volume":"43","author":"J Kallrath","year":"2009","unstructured":"Kallrath, J. (2009). Cutting circles and polygons from area-minimizing rectangles. Journal of Global Optimization, 43(2), 299\u2013328. \nhttps:\/\/doi.org\/10.1007\/s10898-007-9274-6\n\n.","journal-title":"Journal of Global Optimization"},{"key":"3115_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s10898-015-0348-6","volume":"67","author":"J Kallrath","year":"2015","unstructured":"Kallrath, J. (2015). Packing ellipsoids into volume-minimizing rectangular boxes. Journal of Global Optimization, 67, 151\u2013185. \nhttps:\/\/doi.org\/10.1007\/s10898-015-0348-6\n\n.","journal-title":"Journal of Global Optimization"},{"key":"3115_CR22","unstructured":"Kilin\u00e7, M., & Sahinidis, N. V. (2014). Solving MINLPs with BARON. Talk at MINLP 2014, Carnegie Mellon University, Pittsburgh, PA, USA. \nhttp:\/\/minlp.cheme.cmu.edu\/2014\/papers\/kilinc.pdf\n\n."},{"key":"3115_CR23","unstructured":"Lenstra, J. K., & Kan, A. H. G. R. (1979). Complexity of packing, covering and partitioning problems. In A. Schrijver (Ed.), Packing and covering in combinatorics (pp. 275\u2013291). Mathematisch Centrum."},{"issue":"6","key":"3115_CR24","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007\u20131023.","journal-title":"Operations Research"},{"key":"3115_CR25","unstructured":"MUMPS, Multifrontal Massively Parallel sparse direct Solver. \nhttp:\/\/mumps.enseeiht.fr\n\n. Accessed 2011."},{"issue":"1","key":"3115_CR26","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10107-012-0561-8","volume":"142","author":"I Muter","year":"2013","unstructured":"Muter, I., Birbil, S. I., & B\u00fclb\u00fcl, K. (2013). Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. Mathematical Programming, 142(1), 47\u201382. \nhttps:\/\/doi.org\/10.1007\/s10107-012-0561-8\n\n.","journal-title":"Mathematical Programming"},{"issue":"1\u20132","key":"3115_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1111\/itor.12107","volume":"23","author":"JP Pedroso","year":"2016","unstructured":"Pedroso, J. P., Cunha, S., & Tavares, J. N. (2016). Recursive circle packing problems. International Transactions in Operational Research, 23(1\u20132), 355\u2013368. \nhttps:\/\/doi.org\/10.1111\/itor.12107\n\n.","journal-title":"International Transactions in Operational Research"},{"issue":"2","key":"3115_CR28","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.disopt.2005.01.002","volume":"2","author":"D Pisinger","year":"2005","unstructured":"Pisinger, D., & Sigurd, M. (2005). The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optimization, 2(2), 154\u2013167. \nhttps:\/\/doi.org\/10.1016\/j.disopt.2005.01.002\n\n.","journal-title":"Discrete Optimization"},{"key":"3115_CR29","first-page":"57","volume":"3","author":"TK Ralphs","year":"2005","unstructured":"Ralphs, T. K., & Galati, M. V. (2005). Decomposition in integer linear programming. Integer Programming: Theory and Practice, 3, 57\u2013110.","journal-title":"Integer Programming: Theory and Practice"},{"issue":"2","key":"3115_CR30","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00138693","volume":"8","author":"NV Sahinidis","year":"1996","unstructured":"Sahinidis, N. V. (1996). Baron: A general purpose global optimization software package. Journal of Global Optimization, 8(2), 201\u2013205. \nhttps:\/\/doi.org\/10.1007\/BF00138693\n\n.","journal-title":"Journal of Global Optimization"},{"key":"3115_CR31","unstructured":"SCIP\u2014Solving Constraint Integer Programs. \nhttp:\/\/scip.zib.de\n\n. Accessed 2017."},{"issue":"3","key":"3115_CR32","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1023\/A:1018346107246","volume":"9","author":"PH Vance","year":"1998","unstructured":"Vance, P. H. (1998). Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications, 9(3), 211\u2013228. \nhttps:\/\/doi.org\/10.1023\/A:1018346107246\n\n.","journal-title":"Computational Optimization and Applications"},{"issue":"2","key":"3115_CR33","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01300970","volume":"3","author":"PH Vance","year":"1994","unstructured":"Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, G. L. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2), 111\u2013130. \nhttps:\/\/doi.org\/10.1007\/BF01300970\n\n.","journal-title":"Computational Optimization and Applications"},{"issue":"4","key":"3115_CR34","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0167-6377(96)00033-8","volume":"19","author":"F Vanderbeck","year":"1996","unstructured":"Vanderbeck, F., & Wolsey, L. A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19(4), 151\u2013159. \nhttps:\/\/doi.org\/10.1016\/0167-6377(96)00033-8\n\n.","journal-title":"Operations Research Letters"},{"key":"3115_CR35","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-68279-0_13","volume-title":"50 Years of Integer Programming 1958-2008","author":"Fran\u00e7ois Vanderbeck","year":"2009","unstructured":"Vanderbeck, F., & Wolsey, L. A. (2010). Reformulation and decomposition of integer programs (pp. 431\u2013502). Springer, Berlin. \nhttps:\/\/doi.org\/10.1007\/978-3-540-68279-0_13\n\n."},{"key":"3115_CR36","unstructured":"Vigerske, S. (2013). Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. thesis, Humboldt-Universit\u00e4t zu Berlin, Mathematisch-Naturwissenschaftliche Fakult\u00e4t II."},{"issue":"1","key":"3115_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1), 25\u201357. \nhttps:\/\/doi.org\/10.1007\/s10107-004-0559-y\n\n.","journal-title":"Mathematical Programming"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-3115-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-018-3115-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-018-3115-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T07:55:48Z","timestamp":1577951748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-018-3115-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,14]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["3115"],"URL":"https:\/\/doi.org\/10.1007\/s10479-018-3115-5","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2018,12,14]]},"assertion":[{"value":"14 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}