Algorithms for automatic data editing

Article type: Research Article

Authors: Riera-Ledesma, Jorge^{; 1} | Salazar-González, Juan-José

Affiliations: DEIOC, Facultad de Matemáticas, Universidad de La Laguna, 38271 Tenerife, Spain. Tel.: +34 922 318184; Fax: +34 922 318170; E-mail: [email protected], [email protected]

Note: [1] Work supported by the EU funded project IST2000-25069 (CASC), by the Spanish projects TIC2002-10231-E and TIC2002-00895, “Ministerio de Ciencia y Tecnología”, and by “Instituto Canario de Estadística”.

Abstract: This paper concerns the optimization problem arising when a statistical agency must modify microdata to guarantee that the records satisfy a set of rules (called edits). Indeed, before using a collection of data records to infer statistical properties of some groups of responders, the agencies must check and possibly correct the consistence of the collected data. To this end, the edits must be tested on each record and whenever a record does not satisfy all the edits, then the agency must determine the fields in the record to be modified, as well as imputing the new values. Among all the possible solutions, the statistical agency is interested in finding those requiring a minimum number of modified fields, thus leading to a combinatorial optimization problem known as Editing-and-Imputation Problem. This paper presents an Integer Linear Programming model for the specific case in which all edits are linear constraints, and proposes a branch-and-cut algorithm for the exact solution. An extensive computational analysis shows the good performance of our proposal on randomly-generated and artificial instances. The algorithm is used in a new software (TEIDE) to be applied by the Statistical Office of Canary Islands (ISTAC).

DOI: 10.3233/SJU-2003-203-405

Journal: Statistical Journal of the United Nations Economic Commission for Europe, vol. 20, no. 3-4, pp. 255-264, 2003