×

zbMATH — the first resource for mathematics

Solving \( L_1\)-CTA in 3D tables by an interior-point method for primal block-angular problems. (English) Zbl 1269.90149
Summary: The purpose of the field of statistical disclosure control is to avoid that confidential information could be derived from statistical data released by, mainly, national statistical agencies. Controlled tabular adjustment (CTA) is an emerging technique for the protection of statistical tabular data. Given a table with sensitive information, CTA looks for the closest safe table. In this work we focus on CTA for three-dimensional tables using the \( L_1\) norm for the distance between the original and protected tables. Three \( L_1\)-CTA models are presented, giving rise to six different primal block-angular structures of the constraint matrices. The resulting linear programming problems are solved by a specialized interior-point algorithm for this constraints structure which solves the normal equations by a combination of Cholesky factorization and preconditioned conjugate gradients (PCG). In the past, this algorithm was shown to be one of the most efficient approaches for some classes of block-angular problems. The effect of quadratic regularizations is also analyzed, showing that for three of the six primal block-angular structures the performance of PCG is guaranteed to improve. Computational results are reported for a set of large instances, which provide linear optimization problems of up to 50 million variables and 25 million constraints. The specialized interior-point algorithm is compared with the state-of-the-art barrier solver of the CPLEX 12.1 package, showing to be a more efficient choice for very large \( L_1\)-CTA instances.
MSC:
90C90 Applications of mathematical programming
90C06 Large-scale problems in mathematical programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C51 Interior-point methods
Software:
CPLEX; IPM; LIPSOL; OOPS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Castro J (2000) A specialized interior-point algorithm for multicommodity network flows. SIAM J Opt 10:852–877 · Zbl 0955.90087 · doi:10.1137/S1052623498341879
[2] Castro J (2005) Quadratic interior-point methods in statistical disclosure control. Comput Manag Sci 2:107–121 · Zbl 1147.90377 · doi:10.1007/s10287-004-0029-2
[3] Castro J (2006) Minimum-distance controlled perturbation methods for large-scale tabular data protection. Eur J Oper Res 171:39–52 · Zbl 1091.90088 · doi:10.1016/j.ejor.2004.08.034
[4] Castro J (2007a) An interior-point approach for primal block-angular problems. Comput Optim Appl 36:195–219 · Zbl 1148.90351 · doi:10.1007/s10589-006-9000-1
[5] Castro J (2007b) A shortest paths heuristic for statistical disclosure control in positive tables. INFORMS J Comput 19:520–533 · Zbl 06047469 · doi:10.1287/ijoc.1060.0185
[6] Castro J, Cuesta J (2011) Quadratic regularizations in an interior-point method for primal block-angular problems. Math Program. 130:415–445 · Zbl 1229.90086 · doi:10.1007/s10107-010-0341-2
[7] Domingo-Ferrer J, Magkos E (eds) (2010) Lecture notes in computer science. Privacy in statistical databases, vol 6344. Springer, Berlin · Zbl 1196.68006
[8] Domingo-Ferrer J, Saigin Y (eds) (2008) Lecture notes in computer science. Privacy in statistical databases, vol 5262. Springer, Berlin
[9] Dandekar RA, Cox LH (2002) Synthetic tabular data: an alternative to complementary cell suppression, manuscript. Energy Information Administration, US Department of Energy
[10] Gondzio J (1996) Multiple centrality corrections in a primal dual method for linear programming. Comput Optim Appl 6:137–156 · Zbl 0860.90084 · doi:10.1007/BF00249643
[11] Gondzio J, Sarkissian R (2003) Parallel interior-point solver for structured linear programs. Math Program 96:561–584 · Zbl 1023.90039 · doi:10.1007/s10107-003-0379-5
[12] González JA, Castro J (2011) A heuristic block coordinate descent approach for controlled tabular adjustment. Comput Oper Res 38:1826–1835 · Zbl 1215.90052 · doi:10.1016/j.cor.2011.02.008
[13] Hundepool A, Domingo-Ferrer J, Franconi L, Giessing S, Lenz R, Naylor J, Schulte–Nordholt E, Seri E, de Wolf PP (2010) Handbook on statistical disclosure control (v 1.2). Network of Excellence in the European Statistical System in the field of Statistical Disclosure Control. http://neon.vb.cbs.nl/casc/SDC_Handbook.pdf
[14] Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J Optim 2:575–601 · Zbl 0773.90047 · doi:10.1137/0802028
[15] Ng E, Peyton BW (1993) Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J Sci Comput 14:1034–1056 · Zbl 0785.65015 · doi:10.1137/0914063
[16] Wright SJ (1996) Primal-dual interior-point methods. Philadelphia, SIAM
[17] Zhang Y (1998) Solving large-scale linear programs by interior-point methods under the MATLAB environment. Optim Methods Softw 10:1–31 · Zbl 0916.90208 · doi:10.1080/10556789808805699
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.