Detailansicht
Heuristische Lösung gemischt-ganzzahliger Optimierungsprobleme
Bettina Hofbauer
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Hermann Schichl
DOI
10.25365/thesis.27797
URN
urn:nbn:at:at-ubw:1-29833.13053.927170-0
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit beschäftigen wir uns mit gemischt-ganzzahligen Optimierungsproblemen, die zur Klasse der NP-schweren Probleme gehören. Solche Probleme finden eine Vielzahl an Anwendungsmöglichkeiten in der Praxis, sind aber häufig nur sehr schwer zu lösen. Bei großen gemischt-ganzzahligen Optimierungsproblemen stellt sich oft bereits das Finden eines zulässigen Punktes als Herausforderung dar. Die Optimalität zu beweisen ist, mit den heutigen Algorithmen, teilweise gar nicht in vertretbarer Zeit möglich. Wir wollen uns daher auf heuristische Lösungsansätze konzentrieren, die nur zulässige Punkte erzeugen, jedoch lediglich beschränkte Aussagen über die Qualität der Punkte liefern. Dennoch werden wir auch kurz auf exakte Methoden eingehen, die Optimalität gewährleisten können. Unser Hauptaugenmerk werden wir auf die Feasibility Pump, einer Heuristik zur Findung zulässiger Punkte von gemischt-ganzzahligen Optimierungsproblemen, legen. Dieser von Fischetti et al. (2005) entwickelte Algorithmus, konnte sowohl mit Geschwindigkeit als auch der Qualität der gefundenen Punkte überzeugen. Eigene Implementationen sind bei der Druckversion als CD beigelegt.
Schlagwörter
Schlagwörter
(Deutsch)
gemischt-ganzahlige Optimierung MIP MINLP exakte Methoden heuristische Methoden Feasibility Pump
Autor*innen
Bettina Hofbauer
Haupttitel (Deutsch)
Heuristische Lösung gemischt-ganzzahliger Optimierungsprobleme
Publikationsjahr
2013
Umfangsangabe
62 S. : graph. Darst.
Sprache
Deutsch
Beurteiler*in
Hermann Schichl
Klassifikation
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC11095746
Utheses ID
24838
Studienkennzahl
UA | 405 | | |