Lecture: SDP Based Solution Methods for Binary Quadratic Problems
Master data
Title: | SDP Based Solution Methods for Binary Quadratic Problems |
Description: | 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. |
Keywords: |
Type: | Invited speaker |
Homepage: | https://ismp2018.sciencesconf.org/ |
Event: | ISMP 2018 (Bordeaux) |
Date: | 02.07.2018 |
lecture status: |
Participants
Nicolo Gusmeroli (internal) |
|
Angelika Wiegele (internal) |
|
Franz Rendl (internal) |
|
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 |
Focus of lecture |
Classification raster of the assigned organisational units:
|
Group of participants |
|
Published? |
|
Keynote speaker |
|
working groups | No working group selected |
Cooperations
Research activities
Projects |
|
Publications | No related publications |
Events | No related events |
Lectures | No related lectures |