ILP 문제로 데이터 민감도 시나리오 모델링
저는 선형 프로그래밍을 처음 접했고 최근에 해결 방법을 모르는 다음 연습을 보았습니다.
데이터를 게시 할 때 민감한 정보를 "억제"하는 것이 때때로 중요합니다. 다음 표를 고려하십시오.
\ begin {array} {| c | c | c | c |} \ hline & & & X & \\ \ hline X & & & & \\ \ hline & X & & \\ \ hline & X & X & \ \ \ hline & & & & X \\ \ hline \ end {array}
로 표시된 값 $X$ 데이터를 숨겨야하는 셀을 나타냅니다 (동일한 변수로 표시하더라도 이러한 셀의 값이 동일하지 않을 수 있음에 유의하십시오). $X$). 그러나 한 가지 문제가 있습니다. 행과 열의 합계도보고하려고합니다. 이것은 각각의 가치를 쉽게 도출 할 수 있음을 의미합니다.$X$방정식 시스템을 설정하고 풀기 만하면됩니다. 예를 들어 가장 왼쪽에있는$X$ 첫 번째 열의 값의 합계를 계산하고 계산 된 합계로 첫 번째 열의 합계를 빼서 셀.
이는 표시되지 않은 셀을 억제해야 할 수도 있음을 의미합니다. $X$ 의 내용을 보호하기 위해 $X$-표시된 세포. 나는 모든 것을 보호하기 위해 필요한 가장 적은 수의 억제를 선택할 정수 선형 계획법 문제를 공식화하고 싶습니다.$X$-표시된 세포. 따라서 각 행과 열에 두 개 이상의 억제 된 값이 있어야합니다.
나는 생각했다 $x_{ij}$ 같은 $1$ 만약 세포 $(i, j)$ 억제되고 $0$ 그렇지 않으면 전체 합계를 최소화하고 싶습니다. $x_{ij}$하지만 실제 제약 조건을 찾는 것은 정말 어렵습니다 (적어도 저에게는). 저는이 문제에 대해 몇 시간 동안 생각해 왔으며, 가장 어려운 부분은 일련의 제약 조건을 제시하는 것이라고 생각합니다. 나는 많은 공식의 예를 보았지만 아직 비슷한 것을 보지 못했습니다. 이 문제에 대한 도움을 주시면 감사하겠습니다.
답변
의사 결정 변수에서 필요한 제약은 모든 행에 대해 \ begin {align} \ sum_j x_ {i, j} & \ ge 2 && \ text {입니다.$i$ 포함하는 $X$} \\ \ sum_i x_ {i, j} & \ ge 2 && \ text {모든 열에 대해 $j$ 포함하는 $X$} \\ x_ {i, j} & = 1 && \ text {모두 용 $X$-표시된 셀} \ end {align}
억제가 성공하려면 0이 아닌 양의 "노이즈"가 억제 된 각 셀에 추가하여 행과 열 합계가 영향을받지 않도록 할 수 있습니다 (즉, 각 행의 노이즈 합계가 0이고, 유사하게 각 열의 노이즈). 억제 된 각 셀의 노이즈는 다른 셀의 노이즈와 다를 수 있으며, 행 / 열 합계를 0으로 만들려면 노이즈가 일부 셀에서는 음수이고 다른 셀에서는 양수 여야합니다. 0으로 억제되지 않은 모든 셀의 노이즈도 필요합니다. 따라서 두 세트의 이진 변수를 고려할 수 있습니다.$x_{rc}$ 과 $y_{rc}$, 어디 $x_{rc}=1$ 세포를 의미 $(r,c)$ 긍정적 인 소음이 있고 $y_{rc}=1$ 세포를 의미 $(r,c)$ 부정적인 소음이 있습니다 (그리고 $x_{rc}=0=y_{rc}$ 세포를 의미 $(r,c)$잡음이없고 억제되지 않음). 전체 공식은 운동으로 남겨집니다. :-)