Penalty Methods in Discrete Optimization : on the Maximum Number of Threshold Parameters

Dörnfelder, Martin GND

In der Arbeit geht es um die Erzeugung von Alternativlösungen mit der einfachen Penalty-Methode und der Mutual-Penalty-Methode für Kürzeste-Wege-Probleme , bewertete Matroide und minimale Spannbäume. Es ist bekannt, dass zu allen Alternativen ein konvexes Intervall von Penalty-Parametern angegeben werden kann, für das die Alternative optimal ist. Die Parameter, bei denen ein Optimalitäts-Intervall endet und ein anderes beginnt, heißen Sprungstellen. Für die einfache Penalty Methode und das Kürzeste-Wege-Problem wird für beliebige Graphen (sogar Multigraphen) mit n Knoten bewiesen, dass die maximale Anzahl der Sprungstellen quadratisch in n ist. Für bewertete Matroide ergibt sich eine Struktur-Monotonie. Mit dieser Struktur-Monotonie wird gezeigt, dass die maximale Anzahl der Sprungstellen eines bewerteten Matroids genau dessen Rang entspricht. Damit gibt es beim MST-Problem auf Graphen mit n Knoten maximal n-1 Sprungstellen. Bei der Mutual-Penalty-Methode stellt sich heraus, dass bei bewerteten Matroiden und dem Kürzeste-Wege-Problem nur Elemente bestraft werden können, die auch in der optimalen Lösung enthalten waren. Bei den bewerteten Matroiden kann sogar gezeigt werden, dass alle Elemente der optimalen Lösungen auch in allen erzeugten Alternativen auftreten und dass wieder eine Struktur-Monotonie gilt. Damit erhält man wieder den Rang des Matroids als maximale Anzahl der Sprungstellen. Bei dem Kürzeste-Wege-Problem zeigt sich, dass bei jeder neuen Alternative bestimmte Teilwege erstmals unbestraft auftreten. Mit dieser Eigenschaft ergibt sich, dass die maximale Anzahl der Sprungstellen wieder quadratisch in n ist. Ein großer Nachteil der Mutual-Penalty-Methode war bisher der große Aufwand der zum Erzeugen von Alternativen notwendig war. Wir geben hier für die bewerteten Matroide und das Kürzeste-Wege-Problem Algorithmen an, die asymptotisch genauso schnell sind, wie die entsprechenden Standard-Algorithmen zum Erzeugen einer einzelnen Lösung.

Zitieren

Zitierform:

Dörnfelder, Martin: Penalty Methods in Discrete Optimization. on the Maximum Number of Threshold Parameters. 2010.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export