Testmengen in der ganzzahligen Optimierung

Die Kenntnis von Testmengen ermöglicht es, ganzzahlige Optimierungsprobleme mittels eines primalen Optimierungsalgorithmus zu lösen. Testmengen sind durch folgende Eigenschaft charakterisiert: Eine zulässige Lösung

eines ganzzahligen Optimierungsproblems ist entweder optimal, oder es gibt ein Element

der Testmenge, so daß die Differenz

wieder zulässig ist und bezüglich der Zielfunktion einen besseren Wert liefert. Ist also eine zulässige Lösung gegeben, kann man iterativ durch Subtraktion von Testmengenelementen zur Optimallösung gelangen.

Conti und Traverso haben einen interessanten Zusammenhang zwischen ganzzahliger Optimierung und Gröbnerbasen in der kommutativen Algebra aufgezeigt. Dabei werden zulässige Lösungen einer bestimmten ganzen Familie von ganzzahligen Programmen in Beziehung zu einem Binomideal in einem Polynomring gesetzt. Bei geeigneter Wahl einer Monomordnung entspricht dann die reduzierte Gröbner-Basis dieses Ideals der minimalen Testmenge für die Problemfamilie. Theoretisch ergibt sich dadurch die Möglichkeit, mit Hilfe algebraischer Methoden ganzzahlige Optimierungsprobleme zu ösen: Erst wird mit dem Buchberger-Algorithmus die Testmenge ermittelt. Anschließend wird ausgehend von einer zulässigen Lösung eine Folge von Verbesserungsschritten ,,entlang`` Elementen der Testmenge ausgeführt, bis das Optimum erreicht ist.

Obwohl in dem betrachteten Fall die Gröbnerbasis nur zu Idealen mit recht spezieller Struktur berechnet werden muß, ist dieser Ansatz aufgrund der hohen Laufzeit des Buchberger Algorithmus und der potentiell gewaltigen Größe der Basis für Beispiele mit vielen Variablen sehr problematisch. Daher werden die algebraischen Methoden nicht als direkte Lösungsverfahren betrachtet. Statt dessen werden die Methoden der Computeralgebra im hier verfolgten Ansatz dazu eingesetzt, die minimalen Testmengen zu ganzzahligen Optimierungsproblemen zu berechnen, um anschließend aus den so gewonnenen Informationen Aussagen über die Struktur der Testmengen zu ermöglichen.

So ist es beispielsweise im Falle der Bestimmung einer Knotenüberdeckung minimalen Gewichts in einem Graphen gelungen, die Struktur der Testmenge vollständig zu beschreiben, und zwar unabhängig von der Tatsache, daß zu ihrer Berechnung aufwendige algebraische Methoden eingesetzt wurden.

Weiterhin wurde ein Vertex-Cover-Problem auf vollständigen Graphen betrachtet. Bei geeigneter Wahl der Monomordnung gilt in diesem Spezialfall der

Satz: Bis auf ein Element ist die reduzierte Gröbnerbasis genau die Menge aller Vektoren, die entweder negativ bzgl. der Monomordnung sind und das Gewicht um 1 erniedrigen, oder das Gewicht unverändert lassen und positiv bzgl. der Ordnung sind.

**Abbildung:** Typische Repräsentanten der minimalen Testmenge für den K8 graphisch dargestellt. Das linke Element und Elemente vom mittleren Typ senken das Gewicht einer Knotenüberdeckung, während die Elemente vom rechten Typ lediglich für eine Umverteilung der Gewichte stehen.
$\begin{figure}\par\centerline{\epsfig{file=optimierung/vollst_k8.eps,width = \linewidth}}\par\end{figure}$

Im Falle beliebiger Graphen kommt noch eine dritte Klasse von Elementen zur Testmenge hinzu, die die komplizierteren Adjazenz-Beziehungen zwischen Knoten mit veränderten Gewichten widerspiegelt.

Ziel ist es, bei schweren ganzzahligen Optimierungsproblemen eine - möglicherweise unvollständige - Beschreibung der Struktur der Testmenge anzugeben, deren Kenntnis dann in einer Verbesserungsheuristik genutzt werden kann.