Projekt: Semidefinite Relaxations of Ordering Pr...
Stammdaten
| Semidefinite Relaxations of Ordering Problems | |
| Beschreibung: | Bei Ordnungsproblemen wird jeder Ordnung von n Objekten ein Profit zugeordnet und es gilt die Ordnung mit maximalen Profit zu finden. In diesem Projekt betrachten wir Probleme mit linearer und quadratischer Kostenstruktur. Im linearen Fall hängt der Profit von der relativen Position von Objekt u zu Objekt v ab, wohingegen im quadratischen Fall die relativen Positionen von u zu v und r zu s berücksichtigt werden. Das lineare Ordnungsproblem wurde eingehend studiert und es gibt exakte, auf polyedrischen Relaxierungen basierende Lösungsmethoden. Das quadratische Ordnungsproblem scheint hingegen bisher weniger eingehend untersucht worden zu sein. Nichtsdestotrotz sind einige bekannte Probleme der kombinatorischen Optimierung, wie das lineare Anordnungsproblem, Mehrschichtenkreuzungsminimierung, eindimensionales Anlagenlayout und Betweenness, spezielle quadratische Ordnungsprobleme. In diesem Projekt untersuchen wir auf systematische Art und Weise die Anwendung semidefiniter Optimierungsmethoden auf das quadratische Ordnungsproblem. Dabei erweitern und verbessern wir bestehende Ansätze, führen detaillierte polyedrische Untersuchungen ausgewählter Polytope durch, arbeiten an einer effizienten Implementierung der SDP-Ansätze und versuchen neue, vielversprechende Anwendungen wie zum Beispiel Mehrschichtenvertikalitätsmaximierung oder Kreuzungsminimierung am Kreis zu entwickeln. |
| Schlagworte: | SDP-Relaxierungen, Ordnungsprobleme |
| Semidefinite Relaxations of Ordering Problems | |
| Beschreibung: | Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. In this project we consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on whether u is before v and r is before s. The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to have attracted similar attention. Nonetheless well established problems in combinatorial optimization like linear arrangement, multi-level crossing minimization, single-row facility layout and betweenness are special types of the quadratic ordering problem. In this project we work on a systematic investigation of semidefinite optimization based relaxations for the quadratic ordering problem, extending and improving existing approaches. We study the polyhedral structure of selected polytopes, work on an efficient implementation of our relaxations and try to find new promising applications like multi-level verticality maximization or radial crossing minimization. |
| Schlagworte: | SDP relaxations, Ordering problems |
| Kurztitel: | n.a. |
| Zeitraum: | 01.06.2009 - 01.01.2014 |
| Kontakt-Email: | philipp.hungerlaender@uni-klu.ac.at |
| Homepage: | - |
MitarbeiterInnen
| MitarbeiterInnen | Funktion | Zeitraum |
|---|---|---|
| Philipp Hungerländer (intern) |
|
|
Zuordnung
| Organisationseinheit | ||||
|---|---|---|---|---|
|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Kategorisierung
| Projekttyp | laufender Arbeitsschwerpunkt |
| Förderungstyp | Sonstiger |
| Forschungstyp |
|
| Sachgebiete | |
| Forschungscluster | Kein Forschungscluster ausgewählt |
| Genderrelevanz | 0% |
| Projektfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
| Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Finanzierung
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
| Projekte | Keine verknüpften Projekte vorhanden |
| Publikationen |
|
| Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
| Vorträge |
|