Optimização em redes na protecção de informação em tabelas estatísticas bidimensionais

Abstract

Nesta dissertação é estudado o problema de protecção de informação confidencial em tabelas bidimensionais de informação estatística. É utilizado o método de supressão que consiste em omitir das tabelas os valores das células confidenciais. Como são publicados os valores dos subtotais por linha e coluna, é geralmente necessário suprimir também informação não confidencial. As células não confidenciais suprimidas designam-se por supressões complementares. Associando uma penalidade à supressão complementar de uma célula, procura-se a solução que minimiza a penalidade total. Uma tabela pode ser representada através de uma rede bipartida não orientada cujos vértices representam as linhas e colunas e cujas arestas representam a informação suprimida. É apresentado o problema e feita uma descrição sucinta de diferentes abordagens referidas na literatura. Dada a dificuldade do problema, são propostos métodos heurísticos do tipo melhorativo para obtenção de soluções, que usam técnicas de optimização em redes. Os métodos heurísticos são testados em instâncias geradas aleatoriamente. Conclui-se que todas as heurísticas melhoram os resultados comparativamente com os métodos já existentes, conseguindo-se mesmo, para várias instâncias, encontrar a solução óptima.