Vortrag: Efficiently Solving QUBO Problems
Stammdaten
Titel: | Efficiently Solving QUBO Problems |
Beschreibung: | Efficient solution approaches for quadratic unconstrained binary optimization (QUBO) problems are of great interest for several reasons. Firstly, the well-known maximum-cut problem admits a natural formulation as a QUBO problem. Secondly, other optimization problems like the graph bisection problem, the maximum independent set problem, linearly constrained binary quadratic problems, and many more can be reformulated as an instance of QUBO. Since linear programming based approaches perform poorly on dense problem instances, all state-of-the-art approaches involve semidefinite relaxations in this case. In this talk, we present a branch-and-cut solver for QUBO problems based on semidefinite programming. It uses the so-called mixing method, a low-rank coordinate descent method, as its main tool to tackle the occurring semidefinite programs. We discuss some new ideas implemented in the solver and provide numerical results showing that it outperforms the other existing semidefinite approaches. Moreover, it was a paradigm in recent years to tighten semidefinite relaxations by considering more and more valid inequalities. In contrast to this, we demonstrate that weaker relaxations can still be competitive when used in a branch-and-bound approach, even for medium-sized instances. |
Schlagworte: |
Typ: | Vortrag auf Einladung |
Homepage: | https://www.siam.org/conferences/cm/conference/op23 |
Veranstaltung: | SIAM Conference on Optimization (OP23) (Seattle, Washington) |
Datum: | 02.06.2023 |
Vortragsstatus: | stattgefunden (Präsenz) |
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 |
|
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte |
|
Publikationen | Keine verknüpften Publikationen vorhanden |
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |