TY - JOUR

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

AU - Brosch, Daniel

AU - de Klerk, Etienne

N1 - Funding Information:
This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 764759.
Funding Information:
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 764759 .
Publisher Copyright:
© 2020 The Author(s)

PY - 2022/5

Y1 - 2022/5

N2 - 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.

AB - 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.

KW - quadratic assignment problem

KW - semidefinitie programming

KW - discrete energy minimization

KW - symmetry reduction

U2 - 10.1016/j.disopt.2020.100612

DO - 10.1016/j.disopt.2020.100612

M3 - Article

SN - 1572-5286

VL - 44

JO - Discrete Optimization

JF - Discrete Optimization

IS - Part 2

M1 - 100612

ER -