整数型テストカバー用線形計画式？次のように

Question

テストカバー問題を定義することができます。

我々はn疾患のセットと、私たちは、症状を確認するために行うことができますm一連のテストを持っていると仮定します。我々はまた、次のように与えられる：

• A[i][j]がi番目の疾患（1患者にj番目のテストを実行した結果を示すバイナリ値であるAn X n行列が陽性の結果を示し、 0は負の値を示します）。
• 実行テストのコストj,c_j;そして
• 任意の患者が持っていることを正確に1つの疾患

タスクを一意に最小限のコストでn疾患のそれぞれを識別することができる一連のテストを見つけることです。

---

この問題は、我々はそうでない場合は、当社のセットでテストj、および0を含めることを選択した場合x_j = 1目的関数\sum_{j=1}^{m} c_j x_jを、最小限にしたい整数線形プログラムとして処方することができます。

私の質問は：

この問題に対する線形制約のセットは何ですか？

ちなみに、私はこの問題がNP-hard（一般的な整数線形計画法）であると信じています。まあ

Answer 1

がTはその後、すべてjなど= 0 x_j

そのためAのj番目の列を削除した結果、マトリックスとすることを確認する必要があります2つの疾患を一意に区別できる一連のテストを選択することは、Tのすべての行が一意であることを保証することと同じです。

kとlの2行は、すべてjの場合には(T[k][j] XOR T[l][j]) = 0の場合にのみ同一であることに注意してください。

だから、私たちが望むの制約は、すべての1 <= k <= mと1 <= l <= 1なk != lそのため

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

です。

上記の制約は、係数(A[k][j] XOR A[l][j])をあらかじめ計算することができるので、線形であることに注意してください。

Answer 2

私が正しいだ場合、あなただけの

\sum_j x_j.A_ij >= 1 forall i