418 – Current Research and Evaluation Topics in the American Community Survey

Improving LP Performance in Cell Suppression Process

at U.S. Census Bureau

Since 1992, the Economic Census has used cell suppression to protect sensitive information. The disclosure process that suppresses sensitive cells uses a network flow model (MCF) to ensure minimal information loses. However, the answer is often not optimal because the model does not handle large complex table structures very well. Linear Programming (LP) is an alternative methodology that may overcome the limitations of MCF.

A typical LP sets constraints in a multi dimensional grid with one targeted entry (the primary cell) and finds a suppression pattern to protect that target. The cell suppression process completes after solving an LP for each of the primary cells. This is a simple sequential approach. The number of constraints is determined by the size and complexity of the tables being published. The performance depends on both the number of constraints and variables and the number of primary cells. There are two problems of simple sequential approach (1-LP). The first, even if the execution time for each target is fast enough, the time spent on the whole process can be unsupportable. The second, while each LP is optimal it is not optimal globally. This research addresses the first issue; several targets are formulated in one LP such that the computing time for one LP remains small while the whole processing time is reduced. We will explore this partial simultaneous LP (m-LP): how the number of targets in one LP reduces the overall processing time and find the best such number in the trade off with oversuppression. We will also determine how the order of targets to be processed enhances/compromises the objective, i.e., the number of suppressed cells and/or total suppressed value. We will make some comparisons with results from the existing 1-LP program. This research addresses the speed problem LP had and has quantified the amount of oversuppression for selected data.