Minimum energy configurations on a toric lattice as a quadratic assignment problem

Daniel Brosch, Etienne de Klerk

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)


We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.
Original languageEnglish
Article number100612
JournalDiscrete Optimization
Issue numberPart 2
Publication statusPublished - May 2022


  • quadratic assignment problem
  • semidefinitie programming
  • discrete energy minimization
  • symmetry reduction


Dive into the research topics of 'Minimum energy configurations on a toric lattice as a quadratic assignment problem'. Together they form a unique fingerprint.

Cite this