Publikation: Semidefinite Approaches to Ordering Pro...

Stammdaten
Titel: Semidefinite Approaches to Ordering Problems. PhD Thesis
Untertitel:
Kurzfassung: Ordering problems are a special class of combinatorial optimization problems, where weights are assigned to each ordering of n objects and the aim is to find an ordering of maximum weight. In this thesis we use semidefinite optimization for solving ordering problems with up to 100 objects to provable optimality|despite their theoretical difficulty. We present a systematic investigation of semidefinite optimization based relaxations extending and improving existing exact approaches to ordering problems. We consider problems where the cost function is either linear or quadratic in the relative positions of pairs of objects. That includes well-established combinatorial optimization problems like the Linear Ordering Problem, the minimum Linear Arrangement Problem, the Single Row Facility Layout Problem and Multi-level Crossing Minimization. We provide a theoretical and practical comparison of existing exact approaches based on linear, quadratic or semidefinite relaxations. Up to now there existed quite diverse exact approaches to the various ordering problems. A main goal of this thesis is to highlight their connections and to present a unifying approach by showing that the proposed semidefinite model can be successfully applied to all kinds of ordering problems. For tackling ordering problems of challenging size, we construct an algorithm that uses a method from nonsmooth optimization to approximately solve the proposed semidefinite relaxations and applies a rounding scheme to the approximate solutions to obtain (near-)optimal orderings. We show the efficiency of our algorithm by providing extensive computational results for a large variety of problem classes, solving many instances that have been considered in the literature for years to optimality for the first time. While the algorithm provides improved bounds for several classes of difficult instances with a linear cost function, it is clearly the method of choice for instances with quadratic cost structure.
Schlagworte:
Publikationstyp: Hochschulschrift (nicht publiziert) (Autorenschaft)
Erscheinungsdatum: 01.2012 (Print)
Titel der Serie: -
Bandnummer: -
Erstveröffentlichung: Ja
Gesamtseitenanzahl: 152 S.

Versionen
Keine Version vorhanden
Erscheinungsdatum: 01.2012
ISBN: -
ISSN: -
Homepage: -

AutorInnen
P. Hungerländer
Keine Daten vorhanden
*
Philipp Hungerländer
Philipp.Hungerlaender@aau.at
Forschungsaktivitäten
zur Visitenkarte
(intern)

Zuordnung
Organisation Adresse
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Verlag
Organisation Adresse
Alpen-Adria-Universität Klagenfurt (Eigenverlag)
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
  +43 463 2700-9200
  +43463 2700-9299
   uni@aau.at
http://www.aau.at
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Kategorisierung
Sachgebiete
  • 1121 - Operations Research (5347, 5919)
  • 5326 - Produktionsforschung
Forschungscluster Kein Forschungscluster ausgewählt
Peer Reviewed
  • Ja
Publikationsfokus
  • Science to Science (Qualitätsindikator: III)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Kooperationen
Keine Partnerorganisation ausgewählt

Beiträge der Publikation
Keine verknüpften Publikationen vorhanden