ISBN 9783843910361

978-3-8439-1036-1, Reihe Mathematik

Sonja Mars
Mixed-Integer Semidefinite Programming with an Application to Truss Topology Design

294 Seiten, Dissertation Universität Erlangen-Nürnberg (2013), Softcover, A5

Zusammenfassung / Abstract

Mixed-integer semidefinite programming is an evolving field of research. Classical combinatorial optimization problems as well as various different applications can be modeled using semidefinite programs. One such application which can be modeled as semidefinite program (SDP) is the optimization of the topology of trusses.

Within a project of the Collaborative Research Center 805 - Control of Uncertainty in Load-Carrying Structures in Mechanical Engineering at TU Darmstadt active components need to be positioned in the truss. This positioning is done using binary variables and leads to mixed-integer semidefinite programs (MISDP).

We provide a code package for SCIP that uses the SDP solver DSDP and is able to solve general MISDPs. To the knowledge of the author, such a general solver was not available before. To demonstrate the generality of our software, we apply it to the Maximum Cut Problem and Truss Topology Design.

We introduce the required background from linear algebra and present different solving strategies for continuous SDPs. Moreover, we discuss the specific problems when solving SDPs within a branch-and-bound algorithm.

Ideas to speed up the branch-and-bound process for MISDPs are also presented.Furthermore, we state a method for approximating the semidefinite cone and comment on the implementation.

Both applications are introduced and different models for numerous extensions are shown. Finally we present very detailed computational results.