Minimum energy configurations on a toric lattice as a quadratic assignment problem
arXiv:1908.00872 · doi:10.1016/j.disopt.2020.100612
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, Draisma and Van Leeuwaarden [ SIAM Journal on Discrete Mathematics, 27(3):1295--1312, 2013]. The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Parrilo and Permenter [Mathematical Programming, 181:51--84, 2020] to make computation of the SDP bounds possible.
References in corpus (4)
- On semidefinite programming relaxations of the traveling salesman problem
- Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
- Repulsive particles on a two-dimensional lattice
- Dimension reduction for semidefinite programs via Jordan algebras