테스트 커버 용 선형 선형 프로그래밍 공식? 다음과 같이

Question

테스트 커버 문제는 정의 할 수 있습니다

우리가 n 질병의 세트와 우리가 증상을 확인하기 위해 수행 할 수있는 m 테스트 세트가 가정하자. , A[i][j]가 긍정적 인 결과를 나타내는 질환 일 상기 i (1 환자에 j 번째 테스트를 실행 한 결과를 나타내는 이진 값

• n X n 매트릭스 A : 우리는 다음과 같은 주어진다 0은 음수를 나타냄);
• 시험 주행 비용 j, c_j; 및
• 것을 어떤 환자는 정확히 하나 개의 질병

작업이 유일하게 최소의 비용으로하여 n 질병의 각각을 식별 할 수있는 일련의 테스트를 찾을 수 있습니다을해야합니다.

---

이 문제

우리가 목적 함수 \sum_{j=1}^{m} c_j x_j, x_j = 1 우리는 우리의 세트에서 테스트 j을 포함하도록 선택하는 경우, 0 그렇지 않으면를 최소화하려는 정수 선형 프로그램으로 제형 화 될 수있다.

내 질문은 :

이 문제에 대한 선형 제약의 설정은 무엇입니까?

덧붙여 말하자면,이 문제는 NP- 하드 (일반적으로 정수 선형 프로그래밍이 그렇듯이)라고 생각합니다.

Answer 1

이 T 그런 다음 모든 j 같은 0 = x_j 그

에 대한 A의 j 번째 열을 삭제하는 결과 행렬하자 확인해야 올바른 오전 글쎄 경우 두 가지 질병을 고유하게 구별 할 수있는 일련의 검사를 선택하는 것은 T의 모든 행이 고유하다는 것을 보장하는 것과 같습니다.

두 행 k과 l은 모두 j 인 경우에만 (T[k][j] XOR T[l][j]) = 0 인 경우에만 동일 함을 확인하십시오.

그래서, 우리가 원하는 제약

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

모든 1 <= k <= m에 대한

및 1 <= l <= 1 등이 k != l입니다.

계수 (A[k][j] XOR A[l][j])을 사전 계산할 수 있기 때문에 위의 제약 조건은 선형입니다.

Answer 2

난 그냥

\sum_j x_j.A_ij >= 1 forall i