Robust algorithm to generate a diverse class of dense disordered and ordered sphere packings via linear programming

S. Torquato, Y. Jiao

Research output: Contribution to journalArticlepeer-review

89 Scopus citations


We have formulated the problem of generating dense packings of nonoverlapping, nontiling nonspherical particles within an adaptive fundamental cell subject to periodic boundary conditions as an optimization problem called the adaptive-shrinking cell (ASC) formulation. Because the objective function and impenetrability constraints can be exactly linearized for sphere packings with a size distribution in d -dimensional Euclidean space Rd, it is most suitable and natural to solve the corresponding ASC optimization problem using sequential-linear-programming (SLP) techniques. We implement an SLP solution to produce robustly a wide spectrum of jammed sphere packings in Rd for d=2, 3, 4, 5, and 6 with a diversity of disorder and densities up to the respective maximal densities. A novel feature of this deterministic algorithm is that it can produce a broad range of inherent structures (locally maximally dense and mechanically stable packings), besides the usual disordered ones (such as the maximally random jammed state), with very small computational cost compared to that of the best known packing algorithms by tuning the radius of the influence sphere. For example, in three dimensions, we show that it can produce with high probability a variety of strictly jammed packings with a packing density anywhere in the wide range [0.6, 0.7408...], where π/√ 18 =0.7408... corresponds to the density of the densest packing. We also apply the algorithm to generate various disordered packings as well as the maximally dense packings for d=2, 4, 5, and 6. Our jammed sphere packings are characterized and compared to the corresponding packings generated by the well-known Lubachevsky-Stillinger (LS) molecular-dynamics packing algorithm. Compared to the LS procedure, our SLP protocol is able to ensure that the final packings are truly jammed, produces disordered jammed packings with anomalously low densities, and is appreciably more robust and computationally faster at generating maximally dense packings, especially as the space dimension increases.

Original languageEnglish (US)
Article number061302
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Issue number6
StatePublished - Dec 10 2010

All Science Journal Classification (ASJC) codes

  • Condensed Matter Physics
  • Statistical and Nonlinear Physics
  • Statistics and Probability


Dive into the research topics of 'Robust algorithm to generate a diverse class of dense disordered and ordered sphere packings via linear programming'. Together they form a unique fingerprint.

Cite this