Finding bounds on a data sensitivity scenario ILP problem

Question

This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem

As a recap, I was interested in finding the minimum number of cells that need to be suppressed to hide the values of certain cells. Now I'm also interested in finding upper and lower bounds for each cell. Take the following array:

\begin{array}{|c|c|c|c|c|c|} \hline & & & & & \text{Total}\\ \hline & X & X & 56 & 12 & 155\\ \hline & 32 & 93 & X & 37 & X\\ \hline & 54 & 75 & 12 & 13 & 154\\ \hline & 75 & X & 21 & 88 & X\\ \hline & 37& 26&X & 51 & X\\ \hline \text{Total} & X & X & 210 & 201 & 952 \\ \hline \end{array}

At this point, I'm no longer interested in suppressing cells but rather recovering cells. I want to set up an ILP to determine upper and lower bounds for each of the unknown cells, marked as $X$.

Does anyone have any ideas as to how I can go about this? I've been using the ILP in the previous post as something to work off of.

Answer 1

I assume the values are nonnegative; without some finite bounds like that, there is no minimum or maximum. For each cell $(i,j)$, let decision variable $z_{i,j} \ge 0$ be the value in that cell, with $z_{i,j}$ fixed for the known values. For each $X$-marked cell, you want to minimize or maximize the corresponding variable subject to linear constraints that enforce the row and column sums. Note that this is $2\cdot10=20$ separate problems.