Models and algorithms for optimizing cell suppression in tabular data withlinear constraints

Cell suppression is a widely used technique for protecting sensitive inform ation in statistical data presented in tabular form. Previous works on the subject mainly concentrate on two- and three-dimensional tables whose entri es are subject to marginal totals. In this article we address the problem o f protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting cover s, among others, k-dimensianal tables with marginals, as well as hierarchic al and linked tables. In particular, we address the optimization problem kn own in the literature as the (complementary or secondary) cell suppression problem, in which the information loss due to suppression must be minimized . We introduce a new integer linear programming model and outline an enumer ative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computationa l results on a test bed of 1,160 real world and randomly generated instance s are presented, showing the effectiveness of the approach. In particular, we were able to solve to proven optimality four-dimensional tables with mar ginals as well as linked tables. To our knowledge, tables of this kind have never been solved optimally by previous authors.