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

Citations by Year