Discrete optimization is a powerful tool for decision making under economic constraints, such as efficient use of
resources. There is no general way to solve such problems efficiently.
Classical methods often are based on Linear Programming theory. In the last years, it turned out that using
Semidefinite Programming (SDP) instead of Linear Programming (LP) may lead to significant improvements for
the solution of the underlying discrete optimization problem. There is a price to pay to obtain these stronger results.
Instead of working with vectors (LP case), SDP operates in the space of symmetric matrices.
The purpose of the project consisted in the following issues:
Modelling:
Investigate new possibilities to use SDP for the approximation of combinatorial optimization problems.
Algorithms:
Investigate the limits of interior-point methods in the context of SDP.
Large-Scale problems:
Explore algorithmic alternatives for large and sparse problem instances.
Significant progress was made in all three areas of investigation. The SDP approach was extended to graph
partition problems, leading to tight approximations for clustering problems in telecommunication. Secondly, SDP
modeling in combination with the `Bundle-Method` from non-smooth optimization produces the currently strongest
approximation results for the Quadratic Assignment Problem.
The scientific outcome of the project is documented in about 15 publications and 3 dissertations. The researchers of
the project used their knowledge gained during the work in the project to qualify for higher positions.
The project can be considered innovative, as there are currently many international scientific proposals dealing with
SDP, the present one being among the first in this area.