I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive information. Consider the following table:
\begin{array}{|c|c|c|c|} \hline & & & X & \\ \hline X & & & & \\ \hline & X & & \\ \hline & X & X & \\ \hline & & & & X\\ \hline \end{array}
Values marked with an $X$ indicate cells whose data need to be suppressed (note that the values of these cells might not be the same even though I'm indicating them with the same variable $X$). However, there is one problem: we want to also report the sum of the rows and columns. This means that one could easily derive the value of each of the $X$'d cells by just setting up a system of equations and solving. For example, you could easily derive the leftmost $X$ cell by just computing the sum of the values in the first column and subtracting the first column's sum by the computed sum.
This means that it might be necessary to suppress cells that are not marked by $X$ in order to protect the contents of the $X$-marked cells. I want to formulate an integer linear programming problem that will choose the smallest number of suppressions needed in order to protect all of the $X$-marked cells. So it will be necessary to have at least two suppressed values in each row and column.
I thought about having $x_{ij}$ equal $1$ if the cell $(i, j)$ is suppressed and $0$ otherwise so we want to minimize the sum over all $x_{ij}$'s, but then coming up with the actual constraints is really hard (at least for me). I've thought about this problem for a few hours now, and I think the hardest part about it is coming up with a set of constraints. I've looked at lots of examples of formulations, but I haven't come across anything similar yet. I would appreciate any help with this problem.