Solving \( L_1\)-CTA in 3D tables by an interior-point method for primal block-angular problems.

*(English)*Zbl 1269.90149Summary: 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 |

##### Keywords:

interior-point methods; primal block-angular problems; preconditioned conjugate gradient; regularizations; large-scale computational optimization; statistical tabular data protection; controlled tabular adjustment
PDF
BibTeX
XML
Cite

\textit{J. Castro} and \textit{J. Cuesta}, Top 21, No. 1, 25--47 (2013; Zbl 1269.90149)

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.