Integer Linear Programming-Formulierung für Test Cover?

Question

Das Prüfhaube Problem kann wie folgt definiert werden:

Angenommen, wir eine Reihe von n Krankheiten und eine Reihe von m Tests haben wir durchführen können für die Symptome zu überprüfen. Wir sind auch die folgenden angegeben: A

• eine n x n Matrix, wo A[i][j] ein an einem Patienten mit dem i th-Krankheit (1 zeigt ein positives Ergebnis der Ausführung des j th Test, die das Ergebnis Binärwert ist, 0 bedeutet negativ);
• die Kosten für den Lauftest j, c_j; und dass
• jeder Patient wird genau eine Krankheit

Die Aufgabe ist es, eine Reihe von Tests zu finden, die jeden der den n Krankheiten zu minimal Kosten eindeutig identifizieren können.

---

Dieses Problem kann als Integer Linear-Programm formuliert werden, in denen wir die Zielfunktion \sum_{j=1}^{m} c_j x_j, wo x_j = 1, wenn wir Test wählen, um minimieren wollen j in unserem Set enthalten und ansonsten 0.

Meine Frage ist:

Was für dieses Problem der Satz von linearen Bedingungen ist?

Übrigens glaube ich, dieses Problem ist NP-schwer (wie Integer Linear Programming im Allgemeinen).

Answer 1

Lassen T die Matrix, die für alle j so dass x_j = 0.

aus Löschen der j ten Spalte von A führt, um sicherzustellen, müssen dann Die Auswahl einer Reihe von Tests, die zwei Krankheiten eindeutig unterscheiden können, ist gleichbedeutend damit sicherzustellen, dass jede Zeile von T eindeutig ist.

Beachten Sie, dass zwei Reihen k und l identisch sind, wenn und nur wenn (T[k][j] XOR T[l][j]) = 0 für alle j.

Also, die Zwänge wir wollen, sind

\sum_{j=1}^{m} x_j(A[k][j] XOR A[l][j]) >= 1

für alle 1 <= k <= m und 1 <= l <= 1 so dass k != l.

Beachten Sie, dass die obigen Einschränkungen linear sind, da wir den Koeffizienten (A[k][j] XOR A[l][j]) einfach vorberechnen können.

Answer 2

Nun, wenn ich richtig einfach

\sum_j x_j.A_ij >= 1 forall i