Modellierung

Die in der Literatur beschriebenen exakten Verfahren beruhen auf ganzzahliger linearer Programmierung. Sie sind nur für zweidimensionale Probleme verwendbar und stoßen bereits bei sehr kleinen Instanzen an ihre Grenzen. In unseren Untersuchungen entwickelten wir eine neue Art der Modellierung zulässiger Packungen. Es gelang uns zu zeigen, daß sich jede zulässige Anordnung durch einige einfache graphentheoretische Bedingungen charakterisieren läßt.

  

Abbildung: Eine zulässige Packung und die zugehörigen Graphen

Damit kann man die aus der Geometrie entstehenden Schwierigkeiten deutlich reduzieren und sich statt dessen auf die Behandlung der aus der Charakterisierung resultierenden Graphen konzentrieren. Ein Vorzug ist, daß zu einer Auswahl von Graphen normalerweise eine sehr große Zahl von zulässigen Packungen gehört, d.h. man nutzt bei einer Suche mittels Branch-&-Bound allein durch die Wahl dieser Datenstruktur bereits ein großes Maß an Symmetrien aus. Außerdem kommt einem die Tatsache zugute, daß die zu untersuchenden Graphen einige aus der klassischen Kombinatorik bekannte, algorithmisch besonders gutartige Eigenschaften haben.