Modellierung von IF/THEN-Anweisungen in der linearen Programmierung

Question

Gegeben eine Menge boolescher Variablen X = {x0, x1, .... xn}, wobei jede Variable x \ in X zu einer Gruppe gehört G = {g0, g1,. .., g}, g \ subset X

Das Ziel des Problems ist die Anzahl der Variablen in X zu maximieren, die auf 1.

eingestellt werden Wie kann ich die Einschränkung in LP-Modell, das erfordert ALL die Variablen, die zur selben Gruppe g \ in G gehören, auf ENTWEDER 0 oder auf 1 gesetzt werden? Genauer gesagt können keine zwei booleschen Variablen aus einem g \ in G unterschiedliche Werte haben.

P.S: Das oben definierte Problem ist nur eine Vereinfachung des realen Problems, das neben der oben definierten zusätzliche Einschränkungen enthält.

Answer 1

Solche Einschränkungen sind nicht konvex und können daher nicht als LP formuliert werden. Es ist jedoch ein Fall von ILP (Integer LP), das ist NP Aufgabe, aber in der Praxis kann es für eine angemessene Anzahl von Variablen gelöst werden.

Sie können sogar ganz einfach die LP-Aufgabe auf ILP erweitern, indem Sie 0 <= x <= 1 eingrenzen und wenn das Optimum weder 0 noch 1 ist, lösen Sie zwei LPs, eine mit x auf 0, die andere auf 1 und wählen Sie die bessere . Sie wiederholen (recurse), bis alle Integer-Bedingungen erfüllt sind. (Für Details oder effizientere Wege nutzen Sie Google).

---

bearbeiten: Ihr spezielles Problem Zuordnung gegeben, warum would't Sie setzen einfach alle Variablen gleich 1? Das ist offensichtlich das Maximum, und für alle möglichen Gruppen gilt, dass keine zwei Werte unterschiedlich sind (da alle 1 sind).