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

A new integer linear programming model is introduced and several new families of additional inequalities used to strengthen the linear relaxation of the model are described and embedded within a branch-and-cut algorithm for the exact solution of the cell suppression problem.

Abstract

We study the problem of protecting sensitive data in a statistical two-dimensional table, when the non-sensitive table entries are made public along with the row and column totals. In particular, we address the NP-hard problem known in the literature as the (secondary) cell suppression problem. We introduce a new integer linear programming model and describe several new families of additional inequalities used to strengthen the linear relaxation of the model. Exact and heuristic separation procedures are also proposed and embedded within a branch-and-cut algorithm for the exact solution of the problem. The algorithm makes use of an efficient heuristic procedure to find near-optimal solutions. We report the exact solution of instances involving up to 250,000 cells and 10,000 sensitive cells, i.e., more than 3 orders of magnitude larger than those solved by previous techniques from the literature. © Springer-Verlag 1999.