2018/09/27 by Sergey Smirnov, Smirnov, Sergey A., Vladimir Voloshinov +2
Engineering · #Optimization and Packing Problems #Advanced Manufacturing and Logistics Optimization #Advanced Theoretical and Applied Studies in Material Sciences and Geometry
paper · pdf · doi:10.48550/arxiv.1809.10525
The article demonstrates rather general approach to problems of discrete\ngeometry: treat them as global optimization problems to be solved by one of\ngeneral purpose solver implementing branch-and-bound algorithm (B&B). This\napproach may be used for various types of problems, i.e. Tammes problems,\nThomson problems, search of minimal potential energy of micro-clusters, etc.\nHere we consider a problem of densest packing of equal circles in special\ngeometrical object, so called square flat torus \ℝ2/\ℤ2\nwith the induced metric. It is formulated as Mixed-Integer Nonlinear Problem\nwith linear and non-convex quadratic constraints.\n The open-source B&B-solver SCIP, http://scip.zib.de, and its parallel\nimplementation ParaSCIP, http://ug.zib.de, had been used in computing\nexperiments to find "very good" approximations of optimal arrangements. The\nmain result is a confirmation of the conjecture on optimal packing for N=9 that\nwas published in 2012 by O. Musin and A. Nikitenko. To do that, ParaSCIP took\nabout 2000 CPU*hours (16 hours x 128 CPUs) of cluster HPC4/HPC5, National\nResearch Centre "Kurchatov Institute", http://ckp.nrcki.ru\n