10.1 Definitionen

Ein kombinatorisches Optimierungsproblem kann als Tupel < S,f > ausgedrückt werden. S ist eine endliche oder abzählbare Menge von zulässigen Lösungen, die gewissen Randbedingungen genügen. Die Kostenfunktion f : S $\rightarrow$ $\mathbb {R}$ bewertet die zulässigen Lösungen. Ziel ist es, eine Lösung x_opt zu finden mit

f (x_opt) $$\leq$$ f (x)$$\mbox{ f\uml {u}r alle }$$x $$\in$$ S .

Beispiel ( 0/1 -Integer-Linear-Programming):

Gegeben: m × n -Matrix A , m × 1 -Vektor b , n × 1 -Vektor c .
Gesucht ist n × 1 -Vektor $\overline{x}$ $\in$ {0,1}ⁿ mit A$\overline{x}$ $\geq$ b , wobei f ($\overline{x}$) = c ^T$\overline{x}$ zu minimieren ist.
S ist die Menge aller 0/1 -Vektoren $\overline{x}$ , die A$\overline{x}$ $\geq$ b erfüllen. f ist die Funktion c ^T$\overline{x}$ .

Beispiel für eine 0/1 -Integer-Linear-Programming Instanz:

Daraus ergeben sich die Randbedingungen

Zu minimieren ist

Beispiel (8-Puzzle-Problem):

Gegeben ist ein 3 × 3 -Feld mit 8 beweglichen Plättchen, numeriert von 1 bis 8 . Durch eine Folge von Verschiebeoperationen soll die Startkonfiguration in eine Zielkonfiguration überführt werden. S ist die Menge aller Zugsequenzen, die vom Start zum Ziel führen. Die Kostenfunktion f ordnet einer Sequenz die Anzahl der beteiligten Züge zu.

Üblicherweise ist die Menge S so groß, daß sie nicht vollständig durchlaufen werden kann. Man formuliert daher das kombinatorische Optimierungsproblem als Suche in einem kantengewichteten Graphen, in dem ein kostengünstiger Weg von einem Startknoten zu einem von mehreren Zielknoten ermittelt werden muß. Der Graph heißt Zustandsraum, seine Knoten heißen Zustände. Knoten ohne Nachfolger heißen Terminalknoten. Knoten mit Nachfolgern heißen Nonterminalknoten.

Beim 8-Puzzle-Problem bildet die Startkonfiguration den Startknoten und die Zielkonfiguration den einzigen Zielknoten. Wird der Suchraum baumartig aufgespannt, so tritt der Zielknoten mehrfach auf. Die Kanten zwischen den Zuständen entsprechen den möglichen Zügen, sie sind bewertet mit 1 .