Solving the cell suppression problem on tabular data with linear 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 2- and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protec ting sensitive data in a statistical table whose entries are linked by a ge neric system of linear constraints. This very general setting covers, among others, k-dimensional tables with marginals as well as the so-called hiera rchical and linked tables that are very often used nowadays for disseminati ng statistical data. In particular, we address the optimization problem kno wn 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 proce dure to find near-optimal solutions. Extensive computational results on a t est-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 l inked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors).