Data Structures for Representing Symmetry in Quadratically Constrained Quadratic Programs
File(s)1712.05222v2.pdf (330.1 KB)
Working paper
Author(s)
Kouyialis, G
Misener, R
Type
Working Paper
Abstract
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 paper develops several methods for detecting symmetry in quadratically constrained quadratic optimisation problems via adjacency matrices. Using graph theory, we transform these matrices into binary layered graphs and enter them into the software package nauty. Nauty generates important symmetric properties of the original problem.
Copyright Statement
© 2017 The Author(s)
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Identifier
http://arxiv.org/abs/1712.05222v2
Grant Number
EP/P008739/1
Subjects
math.OC
cs.DS