Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition. (English) Zbl 07153648

Summary: 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.


65Kxx Numerical methods for mathematical programming, optimization and variational techniques
90Cxx Mathematical programming
49Mxx Numerical methods in optimal control
Full Text: DOI arXiv


[1] Achterberg, T. (2007). Constraint integer programming. Ph.D. thesis, Technische Universität Berlin. · Zbl 1430.90427
[2] Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, Me; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs, Mathematical Programming, 149, 1-2, 391-424 (2015) · Zbl 1307.90114
[3] Castillo, I., Kampas, F. J., & Pintér, J. D. (2008). Solving circle packing problems by global optimization: Numerical results and industrial applications. European Journal of Operational Research191(3), 786-802. http://EconPapers.repec.org/RePEc:eee:ejores:v:191:y:2008:i:3:p:786-802.
[4] COIN-OR: CppAD, a package for differentiation of CPP Algorithms. http://www.coin-or.org/CppAD. Accessed 2014.
[5] COIN-OR: Ipopt, Interior point optimizer. http://www.coin-or.org/Ipopt. Accessed 2016.
[6] Costa, Alberto; Hansen, Pierre; Liberti, Leo, On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square, Discrete Applied Mathematics, 161, 1-2, 96-106 (2013) · Zbl 1262.90143
[7] Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research8(1), 101-111. http://www.jstor.org/stable/167547. · Zbl 0093.32806
[8] Demaine, E. D., Fekete, S. P., & Lang, R. J. (2010). Circle packing for origami design is hard. arXiv preprint arXiv:1008.1224.
[9] Desaulniers, G.; Desrosiers, J.; Solomon, Mm, Column generation (2006), Berlin: Springer, Berlin
[10] Dror, M., Polygon plate-cutting with a given order, IIE Transactions, 31, 3, 271-274 (1999)
[11] Farley, Aa, A note on bounding a class of linear programming problems, including cutting stock problems, Operations Research, 38, 5, 922-923 (1990) · Zbl 0723.90052
[12] Fortz, B., Labbé, 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).
[13] Gamrath, G. (2010). Generic branch-cut-and-price. Master’s thesis.
[14] Gilmore, P.; Gomory, R., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[15] Gilmore, P.; Gomory, Re, Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 1, 94-120 (1965) · Zbl 0128.39601
[16] 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. arXiv:1501.02155.
[17] Hifi, M., & M’Hallah, R. (2009). A literature review on circle and sphere packing problems: Models and methodologies. Advances in Operations Research, 150, 624:1-150, 624:22. http://dblp.uni-trier.de/db/journals/advor/advor2009.html#HifiM09.
[18] ILOG, Inc: ILOG CPLEX: High-performance software for mathematical programming and optimization. See http://www.ilog.com/products/cplex/. Accessed 2016.
[19] Jans, R., Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints, INFORMS Journal on Computing, 21, 1, 123-136 (2009) · Zbl 1243.90147
[20] Kallrath, J., Cutting circles and polygons from area-minimizing rectangles, Journal of Global Optimization, 43, 2, 299-328 (2009) · Zbl 1169.90434
[21] Kallrath, J., Packing ellipsoids into volume-minimizing rectangular boxes, Journal of Global Optimization, 67, 151-185 (2015) · Zbl 1390.90444
[22] Kilinç, M., & Sahinidis, N. V. (2014). Solving MINLPs with BARON. Talk at MINLP 2014, Carnegie Mellon University, Pittsburgh, PA, USA. http://minlp.cheme.cmu.edu/2014/papers/kilinc.pdf.
[23] 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-291). Mathematisch Centrum. · Zbl 0438.05024
[24] Lübbecke, Me; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023 (2005) · Zbl 1165.90578
[25] MUMPS, Multifrontal Massively Parallel sparse direct Solver. http://mumps.enseeiht.fr. Accessed 2011.
[26] Muter, I.; Birbil, Si; Bülbül, K., Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows, Mathematical Programming, 142, 1, 47-82 (2013) · Zbl 1282.90098
[27] Pedroso, Jp; Cunha, S.; Tavares, Jn, Recursive circle packing problems, International Transactions in Operational Research, 23, 1-2, 355-368 (2016) · Zbl 1338.90351
[28] Pisinger, D.; Sigurd, M., The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, 2, 2, 154-167 (2005) · Zbl 1077.90057
[29] Ralphs, Tk; Galati, Mv, Decomposition in integer linear programming, Integer Programming: Theory and Practice, 3, 57-110 (2005)
[30] Sahinidis, Nv, Baron: A general purpose global optimization software package, Journal of Global Optimization, 8, 2, 201-205 (1996) · Zbl 0856.90104
[31] SCIP—Solving Constraint Integer Programs. http://scip.zib.de. Accessed 2017.
[32] Vance, Ph, Branch-and-price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications, 9, 3, 211-228 (1998) · Zbl 0897.90161
[33] Vance, Ph; Barnhart, C.; Johnson, El; Nemhauser, Gl, Solving binary cutting stock problems by column generation and branch-and-bound, Computational Optimization and Applications, 3, 2, 111-130 (1994) · Zbl 0801.90080
[34] Vanderbeck, F.; Wolsey, La, An exact algorithm for IP column generation, Operations Research Letters, 19, 4, 151-159 (1996) · Zbl 0873.90074
[35] Vanderbeck, François; Wolsey, Laurence A., Reformulation and Decomposition of Integer Programs, 50 Years of Integer Programming 1958-2008, 431-502 (2009), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1187.90207
[36] Vigerske, S. (2013). Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II.
[37] Wächter, A.; Biegler, Lt, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57 (2006) · Zbl 1134.90542
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.