Solving the Cell Suppression Problem on Tabular Data with Linear Constraints

Cell suppression is a widely used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2- and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting covers, among others, k-dimensional tables with marginals as well as the so-called hierarchical and linked tables that are very often used nowadays for disseminating statistical data. In particular, we address the optimization problem known in the literature as the (secondary) Cell Suppression Problem, in which the information loss due to suppression has to be minimized. We introduce a new integer linear programming model and outline an enumerative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computational results on a test-bed of 1,160 real-world and randomly generated instances are presented, showing the effectiveness of the approach. In particular, we were able to solve to proven optimality 4-dimensional tables with marginals as well as linked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors).