A linear programming algorithm to test for jamming in hard-sphere packings

Aleksandar Donev, Salvatore Torquato, Frank H. Stillinger, Robert Connelly

Research output: Contribution to journalArticlepeer-review

92 Scopus citations


Jamming in hard-particle packings has been the subject of considerable interest in recent years. In a paper by Torquato and Stillinger [J. Phys. Chem. B 105 (2001)], a classification scheme of jammed packings into hierarchical categories of locally, collectively and stricly jammed configurations has been proposed. They suggest that these jamming categories can be tested using numerical algorithms that analyze an equivalent contact network of the packing under applied displacements, but leave the design of such algorithms as a future task. In this work, we present a rigorous and practical algorithm to assess whether an ideal hard-sphere packing in two or three dimensions is jammed according to the aforementioned categories. The algorithm is based on linear programming and is applicable to regular as well as random packings of finite size with hard-wall and periodic boundary conditions. If the packing is not jammed, the algorithm yields representative multi-particle unjamming motions. Furthermore, we extend the jamming categories and the testing algorithm to packings with significant interparticle gaps. We describe in detail two variants of the proposed randomized linear programming approach to test for jamming in hard-sphere packings. The first algorithm treats ideal packings in which particles form perfect contacts. Another algorithm treats the case of jamming in packings with significant interparticle gaps. This extended algorithm allows one to explore more fully the nature of the feasible particle displacements. We have implemented the algorithms and applied them to ordered as well as random packings of circular disks and spheres with periodic boundary conditions. Some representative results for large disordered disk and sphere packings are given, but more robust and efficient implementations as well as further applications (e.g., nonspherical particles) are anticipated for the future.

Original languageEnglish (US)
Pages (from-to)139-166
Number of pages28
JournalJournal of Computational Physics
Issue number1
StatePublished - Jun 10 2004

All Science Journal Classification (ASJC) codes

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


  • Hard-sphere system
  • Jamming
  • Linear programming
  • Packings
  • Rigidity theory


Dive into the research topics of 'A linear programming algorithm to test for jamming in hard-sphere packings'. Together they form a unique fingerprint.

Cite this