Dr. Angelika Wiegele,
Universität Klagenfurt

Solving Combinatorial Optimization Problems using the Bundle Method

Many real-world applications, although being non-linear, can be well described by linearized models. Therefore, Linear Programming (LP) became a widely studied and applied technique in many areas of science, industry and economy. Semidefinite Programming (SDP) is an extension of LP. A matrix-variable is optimized over the intersection of the cone of positive semidefinite matrices with an affine space. It turned out, that SDP can provide significantly stronger practical results than LP. Since then SDP turned out to be practical in a lot of different areas, like combinatorial optimization, control theory, engineering, and more recently in polynomial optimization.

Due to the numerous areas of applications, solving SDPs became a widely studied subject. Interior-Point Methods are the most popular algorithms nowadays, yet not applicable for large-scale SDPs. To solve large-scale SDPs, bundle methods turned out to be a useful tool.

In this talk I will state the basic concept of SDP. I will show how to apply SDP to approximate combinatorial optimization problems, focusing on the max-cut and max-k-cut problem. Via the SDP relaxations of these problems I will explain the methods for solving SDPs, in particular the bundle method.