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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
DOIs
Publication statusE-pub ahead of print - Jan 2021

Keywords

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

Fingerprint 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