Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

We study the problem of protecting sensitive data in a statistical two-dime nsional table, when the non-sensitive table entries are made public along w ith the row and column totals. In particular, we address the NP-hard proble m known in the literature as the (secondary) cell suppression problem. We i ntroduce a new integer linear programming model and describe several new fa milies of additional inequalities used to strengthen the linear relaxation of the model. Exact and heuristic separation procedures are also proposed a nd embedded within a branch-and-cut algorithm for the exact solution of the problem. The algorithm makes use of an efficient heuristic procedure to fi nd near-optimal solutions. We report the exact solution of instances involv ing up to 250,000 cells and 10,000 sensitive cells, i.e., more than 3 order s of magnitude larger than those solved by previous techniques from the lit erature.