LAPSE:2019.1634
Published Article
LAPSE:2019.1634
Symmetry Detection for Quadratic Optimization Using Binary Layered Graphs
Georgia Kouyialis, Xiaoyu Wang, Ruth Misener
December 16, 2019
Symmetry in mathematical optimization may create multiple, equivalent solutions. In nonconvex optimization, symmetry can negatively affect algorithm performance, e.g., of branch-and-bound when symmetry induces many equivalent branches. This paper develops detection methods for symmetry groups in quadratically-constrained quadratic optimization problems. Representing the optimization problem with adjacency matrices, we use graph theory to transform the adjacency matrices into binary layered graphs. We enter the binary layered graphs into the software package nauty that generates important symmetric properties of the original problem. Symmetry pattern knowledge motivates a discretization pattern that we use to reduce computation time for an approximation of the point packing problem. This paper highlights the importance of detecting and classifying symmetry and shows that knowledge of this symmetry enables quick approximation of a highly symmetric optimization problem.
Keywords
quadratic optimization, quadratically-constrained quadratic optimization, symmetry
Suggested Citation
Kouyialis G, Wang X, Misener R. Symmetry Detection for Quadratic Optimization Using Binary Layered Graphs. (2019). LAPSE:2019.1634
Author Affiliations
Kouyialis G: Department of Computing, Imperial College London, London SW7 2AZ, UK
Wang X: Department of Computing, Imperial College London, London SW7 2AZ, UK
Misener R: Department of Computing, Imperial College London, London SW7 2AZ, UK [ORCID]
Journal Name
Processes
Volume
7
Issue
11
Article Number
E838
Year
2019
Publication Date
2019-11-09
Published Version
ISSN
2227-9717
Version Comments
Original Submission
Other Meta
PII: pr7110838, Publication Type: Journal Article
Record Map
Published Article

LAPSE:2019.1634
This Record
External Link

doi:10.3390/pr7110838
Publisher Version
Download
Files
[Download 1v1.pdf] (470 kB)
Dec 16, 2019
Main Article
License
CC BY 4.0
Meta
Record Statistics
Record Views
685
Version History
[v1] (Original Submission)
Dec 16, 2019
 
Verified by curator on
Dec 16, 2019
This Version Number
v1
Citations
Most Recent
This Version
URL Here
https://psecommunity.org/LAPSE:2019.1634
 
Original Submitter
Calvin Tsay
Links to Related Works
Directly Related to This Work
Publisher Version