2026-04-17T17:46:29Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/822832025-07-24T18:13:18Zcom_2072_1033col_2072_452951

On the use of integer programming to pursue optimal microaggregation Spagnolo Arrizabalaga, Enrique Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa Consiglio Nazionale delle Ricerche. Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti” Gentile, Claudio Castro Pérez, Jordi Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Optimització Programming (Mathematics) Microaggregation Clustering Heuristics Integer Programming Column Generation Programació (Matemàtica) Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming CNR-IASI This document reports a research collaboration in CNR-IASI (Italy) until the 7th of January. Microaggregation is a method for perturbing data in order to avoid individual identification in microdata. In terms of optimization, it is a clustering problem which consists in joining individuals in clusters with a minimal size such that the total spread is minimized. For multivariate data, the problem is NP-Hard and there is no procedure guaranteeing optimality. This document reports the state of the art in this topic on heuristic clustering algorithms and Integer Programming. Besides, inspired by the use of Column Generation in an approximate model, the document proposes a scheme to solve microaggregation with optimality. The block of Column Generation has been deeply developed in polyhedral aspects for the Pricing Problem. A code of this first block has also been implemented with CPLEX and its results are reported too. At the current stage, the procedure achieves optimality in certain instances of data and, in any case, finds a lower bound on the spread in microaggregation. Those results are new contributions and encourage us to follow this line of research. 2016-01 Bachelor thesis https://hdl.handle.net/2117/82283 FME-1260 eng http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access application/pdf Universitat Politècnica de Catalunya