Efficient linear programming algorithm to generate the densest lattice sphere packings

Étienne Marcotte, Salvatore Torquato

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Finding the densest sphere packing in d-dimensional Euclidean space Rd is an outstanding fundamental problem with relevance in many fields, including the ground states of molecular systems, colloidal crystal structures, coding theory, discrete geometry, number theory, and biological systems. Numerically generating the densest sphere packings becomes very challenging in high dimensions due to an exponentially increasing number of possible sphere contacts and sphere configurations, even for the restricted problem of finding the densest lattice sphere packings. In this paper we apply the Torquato-Jiao packing algorithm, which is a method based on solving a sequence of linear programs, to robustly reproduce the densest known lattice sphere packings for dimensions 2 through 19. We show that the TJ algorithm is appreciably more efficient at solving these problems than previously published methods. Indeed, in some dimensions, the former procedure can be as much as three orders of magnitude faster at finding the optimal solutions than earlier ones. We also study the suboptimal local density-maxima solutions (inherent structures or "extreme" lattices) to gain insight about the nature of the topography of the "density" landscape.

Original languageEnglish (US)
Article number063303
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Issue number6
StatePublished - Jun 7 2013

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Efficient linear programming algorithm to generate the densest lattice sphere packings'. Together they form a unique fingerprint.

Cite this