3
$\begingroup$

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.

Improve this question
$\endgroup$
1
$\begingroup$

With your decision variables, some necessary constraints are \begin{align} \sum_j x_{i,j} &\ge 2 &&\text{for all rows $i$ that contain an $X$}\\ \sum_i x_{i,j} &\ge 2 &&\text{for all columns $j$ that contain an $X$}\\ x_{i,j} &=1 &&\text{for all $X$-marked cells} \end{align}

Improve this answer
$\endgroup$
4
  • $\begingroup$ On the necessity side, I don't think you need the constraints for rows/columns with no X cells in them. On the sufficiency side, what about the matrix $$ \left[\begin{array}{cccc} X & X\\ X & X\\ & & X & X\\ X & & X & X \end{array}\right] $$ which meets your criteria? I think the noise in the lower left cell has to be zero to balance the row/column sums. $\endgroup$
    – prubin
    Sep 28 '20 at 13:10
  • $\begingroup$ Agreed on both counts. $\endgroup$
    – RobPratt
    Sep 28 '20 at 14:45
  • $\begingroup$ @RobPratt Thanks for the explanation. I posted a follow-up question regarding this problem here: or.stackexchange.com/questions/4979/… $\endgroup$
    – user4156
    Oct 5 '20 at 21:30
  • $\begingroup$ @prubin’s answer deserves the check mark. $\endgroup$
    – RobPratt
    Oct 6 '20 at 0:05
3
$\begingroup$

For the suppression to be successful, what you need is that there some nonzero amount of "noise" you can add to each suppressed cell such that the row and column sums are unaffected (meaning the sum of the noise in each row is zero, and similarly for the noise in each column). The noise in each suppressed cell may be different from the noise in any other cell, and clearly noise will need to be negative in some cells and positive in others to get row/column sums to zero out. You also need the noise in any cell that is not suppressed to be zero. So you might consider two sets of binary variables, say $x_{rc}$ and $y_{rc}$, where $x_{rc}=1$ means cell $(r,c)$ has positive noise and $y_{rc}=1$ means cell $(r,c)$ has negative noise (and $x_{rc}=0=y_{rc}$ means cell $(r,c)$ has zero noise and is not suppressed). The full formulation is left as an exercise. :-)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. When you mean "positive noise" and "negative noise", I assume you mean adding a positive value to that cell and adding a negative value to the other cell? Is the following formulation complete? We want to minimize $\sum_r \sum_c x_{rc} + y_{rc}$ subject to $\sum_{r} x_{rc} - y_{rc} = 0$ for each column $c$ and $\sum_{c} x_{rc} - y_{rc} = 0$ for each fixed row $r$? Also, we require $x_{ij}, y_{i, j} \in \{0, 1\}$? $\endgroup$
    – user4156
    Sep 26 '20 at 22:26
  • $\begingroup$ Actually, I had in mind that the amount of noise in each cell would be a continuous variable, positive if the corresponding $x$ is 1, negative if the corresponding $y$ is 1, and zero if $x$ and $y$ are both zero. Total noise in each row or column would be zero. Either $x$ or $y$ (but not both) would have to be 1 in a cell required to be suppressed. $\endgroup$
    – prubin
    Sep 27 '20 at 18:39
  • $\begingroup$ Rob's answer is (much) simpler, assuming he can show that for any set of binaries satisfying those constraints, there is a corresponding set of values (all nonzero) that sum to zero in every row and column. I would not be shocked if that were true, but I'm not seeing an obvious proof. $\endgroup$
    – prubin
    Sep 27 '20 at 19:00
  • $\begingroup$ The constraints ensure that the $X$-marked cells appear in a union of cycles in the corresponding complete bipartite graph in which each matrix entry corresponds to an edge. Alternately adding and subtracting a constant along the edges in each cycle preserves both the row sums and the column sums but perturbs the matrix entry values, so no $X$-marked value can be deduced. $\endgroup$
    – RobPratt
    Sep 27 '20 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy