Exakte Algorithmen

Die Nützlichkeit der verschiedenen theoretischen Neuerungen auch im Zusammenspiel konnten wir durch eine Implementation des resultierenden Gesamtverfahrens zeigen. Für das zweidimensionale orthogonale Knapsackproblem konnte die maximale Anzahl der Objekte in einer exakt gelösten Instanz von 22 auf 80, und die maximale Anzahl verschiedener Objektgrößen von 15 auf 40 gesteigert werden. Diese Zahlen geben keine singulären Extremfälle wieder, sondern beziehen sich auf ganze Klassen nichttrivialer Testinstanzen. Nach unserem Wissen haben wir erstmalig experimentelle Resultate für das dreidimensionale orthogonale Knapsackproblem veröffentlicht.
Bei einem geringen Anteil kleiner Quader konnten hier ebenso große Instanzen bearbeitet werden wie im zweidimensionalen Fall.