Data Structures for Representing Symmetry in Quadratically Constrained Quadratic Programs
share
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.
READ FULL TEXT