Vortrag: Lasserre Hierarchy versus Exact Subgraphs for Max-Cut and Stable-Set
Stammdaten
Titel: | Lasserre Hierarchy versus Exact Subgraphs for Max-Cut and Stable-Set |
Beschreibung: | Several hierarchies of semidefinite optimization relaxations for discrete problems were introduced in the last 30 years. The model of Lasserre (SIAM Journal on Optimization, 2002) is currently considered to be the strongest such hierarchy. Unfortunately, this hierarchy isnot easily accessible from a computational point of view. Already the first nontrivial level of this hierarchy leads to semidefinite problems with matrices of order(n+12)when starting from a binary problem in n variables. In contrast, the hierarchy based on exact subgraphs introduced by Adams et al (Information Systems and Operational Research 2015) has recently been shown to be quite an efficient tool to compute strong bounds for Max-Cut and Stable-Set (Gaar et al., Integer Programming and Combinatorial Optimization 2018). It operates on all levels in the space of n×n matrices.In this talk we investigate how these two models relate to each other. It turns out that the exact subgraph hierarchy may be interpreted as a weak form of the Lasserre hierarchy. We investigate enhancements for the exact subgraph hierarchy, which are derived from properties of the Lasserre hierarchy. We use the ’Semidefinite Matrix Completion Theory’ based on chordal graphs to get a computational handle on the Lasserre hierarchy. As a result, we strengthen the exact subgraph model by introducing additional semi definiteness constraints for matrices of small order to capture the power of the Lasserre hierarchy. Some preliminary computational experiments will be reported to demonstrate the potential of this approach. |
Schlagworte: | RICAM Conic and Copositive Optimization |
Typ: | Vortrag auf Einladung |
Homepage: | https://www.ricam.oeaw.ac.at/specsem/specsem2019/workshop6/ |
Veranstaltung: | RICAM Special Semester Optimization (Linz, Johann Radon Institute for Computational and Applied Mathematics) |
Datum: | 11.12.2019 |
Vortragsstatus: |
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Keynote-Speaker |
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
|
AT
|
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte | Keine verknüpften Projekte vorhanden |
Publikationen | Keine verknüpften Publikationen vorhanden |
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |