MinPerim swMATH ID: 40493 Software Authors: Kallrath, Josef; Frey, Markus M. Description: MinPerim: mixed-integer non-linear pro- gramming model. Packing circles into perimeter-minimizing convex hulls. We present and solve a new computational geometry optimization problem in which a set of circles with given radii is to be arranged in unspecified area such that the length of the boundary, i.e., the perimeter, of the convex hull enclosing the non-overlapping circles is minimized. The convex hull boundary is established by line segments and circular arcs. To tackle the problem, we derive a non-convex mixed-integer non-linear programming formulation for this circle arrangement or packing problem. Moreover, we present some theoretical insights presenting a relaxed objective function for circles with equal radius leading to the same circle arrangement as for the original objective function. If we minimize only the sum of lengths of the line segments, for selected cases of up to 10 circles we obtain gaps smaller than (10^{-4}) using exttt{BARON} or exttt{LINDO} embedded in exttt{GAMS}, while for up to 75 circles we are able to approximate the optimal solution with a gap of at most (14 Homepage: https://ideas.repec.org/a/spr/jglopt/v73y2019i4d10.1007_s10898-018-0724-0.html Keywords: global optimization; non-convex nonlinear programming; circular packing problem; convex hull; perimeter minimization; non-overlap constraints; computational geometry; isoperimetric inequality Related Software: GAMS; QuickhullDisk; LINDO; BARON; VOROPACK-D; Quicksort; Qhull Cited in: 4 Publications Standard Articles 2 Publications describing the Software, including 2 Publications in zbMATH Year Near optimal minimal convex hulls of disks. Zbl 1473.90129Kallrath, Josef; Ryu, Joonghyun; Song, Chanyoung; Lee, Mokwon; Kim, Deok-Soo 2021 Packing circles into perimeter-minimizing convex hulls. Zbl 1422.90045Kallrath, Josef; Frey, Markus M. 2019 all top 5 Cited by 9 Authors 3 Kallrath, Josef 2 Frey, Markus M. 2 Kim, Deok-Soo 2 Ryu, Joonghyun 2 Song, Chanyoung 1 Hoàng, Nam-Dũng 1 Lee, Mokwon 1 Nguyen Kieu Linh 1 Phan Thanh An Cited in 3 Serials 2 Journal of Global Optimization 1 Applied Mathematics and Computation 1 Vietnam Journal of Mathematics Cited in 5 Fields 3 Operations research, mathematical programming (90-XX) 2 Convex and discrete geometry (52-XX) 1 Differential geometry (53-XX) 1 Numerical analysis (65-XX) 1 Computer science (68-XX) Citations by Year