2017/12/14 by Georgia Kouyialis, Ruth Misener, Kouyialis, Georgia +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #VLSI and FPGA Design Techniques #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1712.05222
openalex publication_date 2017/12/14 · arxiv created 2019/01/20 · arxiv updated 2019/01/23 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
Symmetry in mathematical programming may lead to a multiplicity of solutions. In nonconvex optimisation, it can negatively affect the performance of the branch-and-bound algorithm. Symmetry may induce large search trees with multiple equivalent solutions, i.e. with the same optimal value. Dealing with symmetry requires detecting and classifying it first. This work develops methods for detecting groups of symmetry in the formulation of quadratically constrained quadratic optimisation problems via adjacency matrices. Using graph theory, we transform these matrices into Binary Layered Graphs (BLG) and enter them into the software package nauty. Nauty generates important symmetric properties of the original problem.