MinPerim
swMATH ID:  40493 
Software Authors:  Kallrath, Josef; Frey, Markus M. 
Description:  MinPerim: mixedinteger nonlinear pro gramming model. Packing circles into perimeterminimizing 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 nonoverlapping circles is minimized. The convex hull boundary is established by line segments and circular arcs. To tackle the problem, we derive a nonconvex mixedinteger nonlinear 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_s1089801807240.html 
Keywords:  global optimization; nonconvex nonlinear programming; circular packing problem; convex hull; perimeter minimization; nonoverlap constraints; computational geometry; isoperimetric inequality 
Related Software:  VOROPACKD; BARON; QuickhullDisk; GAMS; Knot Atlas; KnotPlot; Ipopt; Qhull; Quicksort; LINDO 
Cited in:  6 Documents 
Standard Articles
2 Publications describing the Software, including 2 Publications in zbMATH  Year 

Near optimal minimal convex hulls of disks. Zbl 1473.90129 Kallrath, Josef; Ryu, Joonghyun; Song, Chanyoung; Lee, Mokwon; Kim, DeokSoo 
2021

Packing circles into perimeterminimizing convex hulls. Zbl 1422.90045 Kallrath, Josef; Frey, Markus M. 
2019

all
top 5
Cited by 15 Authors
Cited in 4 Serials
3  Journal of Global Optimization 
1  Applied Mathematics and Computation 
1  Vietnam Journal of Mathematics 
1  Journal of Physics A: Mathematical and Theoretical 
all
top 5