Data Structures for Representing Symmetry in Quadratically Constrained Quadratic Programs

File Description SizeFormat 
1712.05222v2.pdfWorking paper330.1 kBAdobe PDFView/Open
Title: Data Structures for Representing Symmetry in Quadratically Constrained Quadratic Programs
Authors: Kouyialis, G
Misener, R
Item 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.
URI: http://hdl.handle.net/10044/1/55485
Copyright Statement: © 2017 The Author(s)
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/P008739/1
Keywords: math.OC
cs.DS
Appears in Collections:Faculty of Engineering
Computing



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx