Die kombinatorischen Verfahren von Balas

Zusammenfassung Zur Behandlung von Booleschen linearen Programmen der Form (P) Minimiere c′x unter den Restriktionen Ax≤b, xj ∈ {0,1} (1≤ j ≤ n) schlägt Balas ([64a], [65b]) kombinatorische Verfahren vor. Durch diese wird systematisch ein Teil der 2n verschiedenen n-Tupeln (x1,..., xn) erzeugt und dann so abgeprüft, daß implizit alle Elemente der Lösungsmenge geprüft werden (Partielle oder implizite Enumeration). Ausgehend von x(o)=0 erzeugen wir eine Folge von Vektoren x(s)∈Bn, die wir auf Zulässigkeit und Optimalität prüfen. Ein Vektor x(s) ist eindeutig durch die Indexmenge Js festgelegt, die durch die Beziehung $${{x}_{j}}^{{(s)}} = \left\{ {\begin{array}{*{20}{c}} 1 & {j \in {{J}_{s}}} \\ 0 & {j \notin {{J}_{s}}} \\ \end{array} } \right.$$ definiert wird. Die Vektoren können wir als Knoten eines Graphen deuten. So entspricht dem Vektor x(s)der Knoten s. Einer Kante (r, s) des Graphen entspricht das Paar (x(r), x(s)), wobei Jr⊂ Js gilt und Js\Jr genau ein Element besitzt. In diesem Falle verwenden wir die Sprechweise: x(r) ist Vorgänger von x(s), x(s) ist Nachfolger von x(r).