Back to Search
Start Over
Minimum energy configurations on a toric lattice as a quadratic assignment problem
- Source :
- Discrete Optimization, 2020, 100612, ISSN 1572-5286
- Publication Year :
- 2019
-
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.
- Subjects :
- Mathematics - Optimization and Control
90C22, 90C10
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Optimization, 2020, 100612, ISSN 1572-5286
- Publication Type :
- Report
- Accession number :
- edsarx.1908.00872
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.disopt.2020.100612