Lösungsverfahren Für Das Standardproblem Eindimensionalen Zuschneidens

ISBN-13: 9783790810073 / Niemiecki / Miękka / 1997 / 224 str.

Thomas Gau

Opis

Der Verfasser setzt sich mit dem Standardproblem eindimensionalen Zuschneidens auseinander, und hier im besonderen mit Fragen der Vorteilhaftigkeit und der Beurteilung von Losungsverfahren sowohl fur den relaxierten als auch fur den ganzzahligen Fall. Ausgehend von alternativen Moglichkeiten der Modellierung und der Ausnutzung der Aquivalenz zum bekannteren Bin Packing Problem werden mehrere Dekompositionsheuristiken vorgeschlagen, durch deren kombinierten Einsatz es dem Verfasser gelungen ist, fur 11.959 der betrachteten 12.000 Probleminstanzen eine optimale, ganzzahlige Losung zu bestimmen. Des Weiteren wird das spaltenerzeugende Verfahren von Gilmore und Gomory, das wesentlicher Bestandteil dieser Dekompositionsheuristiken ist, erstmalig in derartiger Ausfuhrlichkeit analysiert und diskutiert."

Spis treści

1 Einführung.- 2 Das Standardproblem.- 3 Methodik der Analyse und Beurteilung von Lösungsverfahren.- 4 Ansätze zur Lösung des relaxierten Standardproblems.- 5 Ansätze zur Lösung des ganzzahligen Standardproblems.- 6 Zusammenfassung und Ausblick.- Anhang A: Fortran-Implementation des Problemgenerators CUTGEN1.- Anhang B: Ergebnisse für das spaltenerzeugende Verfahren.- Abbildungsverzeichnis.- Tab ellenverzeichnis.- Tafelverzeichnis.- Symbolverzeichnis.