Lecture: A class of new cutting planes for SDP relaxations of stable set and c...
Master data
Title: | A class of new cutting planes for SDP relaxations of stable set and colouring problems |
Description: | Stable set and colouring problems are fundamental combinatorial optimization problems. A standard method in combinatorial optimization is to write a problem as a linear problem with integer variables, and then to consider its relaxation in order to get bounds on the optimal solution. This research focuses on bounds which are obtained by semidefinite relaxations using semidefinite programming. A famous semidefinite relaxation for both stable set and colouring problems is the Lovász theta function. We consider tightening of the Lovász theta function which can be achieved by adding valid inequalities into the formulation. We combine the ideas of some of the existing inequalities and derive new cutting planes for both problems. Finally, we investigate the bounds obtained by adding the proposed inequalities. We compare our bounds with existing relaxations and present computational results. |
Keywords: |
Type: | Registered lecture |
Homepage: | http://www.airoconference.it/ods2023/ |
Event: | ODS 2023, International Conference on Optimization and Decision Science (Ischia) |
Date: | 06.09.2023 |
lecture status: | stattgefunden (Präsenz) |
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? |
|
working groups |
|
Cooperations
Research activities
Projects |
|
Publications | No related publications |
Events | No related events |
Lectures | No related lectures |