Vortrag: SDP Based Solution Methods for Binary Quadratic Problems
Stammdaten
Titel: | SDP Based Solution Methods for Binary Quadratic Problems |
Beschreibung: | Binary quadratic programs (BQP) with equality constraints have a convex quadratic function, linear equality constrains and binary variables. Many problems, like Max-Cut, kcluster, ... can be modeled as BQP. A wide range of solution techniques were proposed and studied in the past in order to solve the problem either to optimality or with heuristics. We present some approaches such as exact penalization methods, branch and bound and a bundle algorithm in combination with semidefinite relaxations. Then we see the possible combinationsbetweentheminordertoobtainpracticalresults. In this talk we explain some of the choices throughout the algorithms and we exploit their practical performance, relating it with computational time for some testbed examples. Furthermorewecompareourresultsforthebinaryquadraticproblem with other approaches, first for unconstrained problems and then to instances with equality constraints. |
Schlagworte: |
Typ: | Vortrag auf Einladung |
Homepage: | https://ismp2018.sciencesconf.org/ |
Veranstaltung: | ISMP 2018 (Bordeaux) |
Datum: | 02.07.2018 |
Vortragsstatus: |
Beteiligte
Nicolo Gusmeroli (intern) |
|
Angelika Wiegele (intern) |
|
Franz Rendl (intern) |
|
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
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 |