Publication: A Bundle Approach for SDPs with Exact S...
Master data
Title: | A Bundle Approach for SDPs with Exact Subgraph Constraints |
Subtitle: | |
Abstract: | The ‘exact subgraph’ approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into two independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach. |
Keywords: | Semidefinite programming, Relaxation hierarchy, Max-Cut, Stable set, Coloring |
Publication type: | Article in Proceedings (Authorship) |
Publication date: | 13.04.2019 (Print) |
Published by: |
IPCO 2019: Integer Programming and Combinatorial Optimization
IPCO 2019: Integer Programming and Combinatorial Optimization
(
Springer;
)
to publication |
Title of the series: | Lecture Notes in Computer Science |
Volume number: | 11480 |
First publication: | Yes |
Version: | - |
Page: | pp. 205 - 218 |
Cover: |
|
Versionen
Keine Version vorhanden |
Publication date: | |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1007/978-3-030-17953-3_16 |
Homepage: | - |
Open access |
|
Publication date: | 13.04.2019 |
ISBN: |
|
ISSN: | - |
Homepage: | https://link.springer.com/chapter/10.1007/978-3-030-17953-3_16 |
Authors
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Peer reviewed |
|
Publication focus |
Classification raster of the assigned organisational units:
|
working groups | No working group selected |
Cooperations
Research activities
Projects: |
|
Publications: | No related publications |
Events: | No related events |
Lectures: |
|