The research interests of the optimisation study group lie in the algorithmic approach to NP-hard combinatorial optimisation tasks. Since no efficient algorithms are known and possibly do not exist for these problems, the question of efficient approximation methods arises from a practical point of view.
In a series of graph problems, it has been shown that with purely linear approaches, the set of permissible points in the problem can only be described very imprecisely, see for example “chromatic number” or “max cut”. The polyhedral approach requires either a piecemeal linear approximation or for the problem to be placed in a higher dimensional context. By contrast, “matrix relaxations” offer the option of handling quadratic terms directly. The admissible quantity, consisting of semi-definite matrices with rank one, is embedded into the cone of the semi-definite matrices.
The study group researches these matrix relaxations in connection with convex analysis. The main emphasis here is on linear optimisation tasks relating to the cone of the positive semi-definite matrices, so the non-linearity is only in the cone. A range of graph decomposition problems lead to these kinds of matrix relaxations. The algorithmic challenge lies in managing large instances, such as matrices of order 1000 and a variety of combinatorial constraints. To do so, sub-gradient methods and projection techniques are used in addition to standard methods in non-linear optimisation.
The relaxations researched and the solution methods developed for them are embedded into branch and bound procedures in order to contain precise algorithms to solve combinatorial optimisation problems. The website run by the study group, BiqMac (biqmac.aau.at), offers the option of exactly solving quadratic problems with 0-1 variables.
A further focus of the study group is on the development of active set methods, which cannot be applied to continuous quadratic convex (and recently also non-convex) optimisation problems with different constraint types.
