IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v62y2014i4p891-909.html
   My bibliography  Save this article

Perspective Reformulations of the CTA Problem with L 2 Distances

Author

Listed:
  • Jordi Castro

    (Department of Statistics and Operations Research, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Catalonia, Spain)

  • Antonio Frangioni

    (Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy)

  • Claudio Gentile

    (Istituto di Analisi dei Sistemi ed Informatica, C.N.R., Viale Manzoni 30, 00185 Rome, Italy)

Abstract

Any institution that disseminates data in aggregated form has the duty to ensure that individual confidential information is not disclosed, either by not releasing data or by perturbing the released data while maintaining data utility. Controlled tabular adjustment (CTA) is a promising technique of the second type where a protected table that is close to the original one in some chosen distance is constructed. The choice of the specific distance shows a trade-off: although the Euclidean distance has been shown (and is confirmed here) to produce tables with greater “utility,” it gives rise to mixed integer quadratic problems (MIQPs) with pairs of linked semi-continuous variables that are more difficult to solve than the mixed integer linear problems corresponding to linear norms. We provide a novel analysis of perspective reformulations (PRs) for this special structure; in particular, we devise a projected PR (P 2 R), which is piecewise-conic but simplifies to a (nonseparable) MIQP when the instance is symmetric. We then compare different formulations of the CTA problem, showing that the ones based on P 2 R most often obtain better computational results.

Suggested Citation

  • Jordi Castro & Antonio Frangioni & Claudio Gentile, 2014. "Perspective Reformulations of the CTA Problem with L 2 Distances," Operations Research, INFORMS, vol. 62(4), pages 891-909, August.
    • Handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:891-909
    DOI: 10.1287/opre.2014.1293
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2014.1293
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2014.1293?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michael Bacharach, 1966. "Matrix Rounding Problems," Management Science, INFORMS, vol. 12(9), pages 732-742, May.
    2. Castro, Jordi, 2006. "Minimum-distance controlled perturbation methods for large-scale tabular data protection," European Journal of Operational Research, Elsevier, vol. 171(1), pages 39-52, May.
    3. Matteo Fischetti & Juan José Salazar, 2001. "Solving the Cell Suppression Problem on Tabular Data with Linear Constraints," Management Science, INFORMS, vol. 47(7), pages 1008-1027, July.
    4. Antonio Frangioni & Claudio Gentile & Enrico Grande & Andrea Pacifici, 2011. "Projected Perspective Reformulations with Applications in Design Problems," Operations Research, INFORMS, vol. 59(5), pages 1225-1232, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Castro, Jordi, 2012. "Recent advances in optimization techniques for statistical tabular data protection," European Journal of Operational Research, Elsevier, vol. 216(2), pages 257-269.
    2. Castro, Jordi, 2006. "Minimum-distance controlled perturbation methods for large-scale tabular data protection," European Journal of Operational Research, Elsevier, vol. 171(1), pages 39-52, May.
    3. Sedeño-Noda, A. & González-Dávila, E. & González-Martín, C. & González-Yanes, A., 2009. "Preemptive benchmarking problem: An approach for official statistics in small areas," European Journal of Operational Research, Elsevier, vol. 196(1), pages 360-369, July.
    4. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    5. Zhang, Sumei & Guldmann, Jean-Michel, 2009. "Estimating suppressed data in regional economic databases: A goal-programming approach," European Journal of Operational Research, Elsevier, vol. 192(2), pages 521-537, January.
    6. Juan-José Salazar-González, 2005. "A Unified Mathematical Programming Framework for Different Statistical Disclosure Limitation Methods," Operations Research, INFORMS, vol. 53(5), pages 819-829, October.
    7. Sage, Andrew J. & Wright, Stephen E., 2016. "Obtaining cell counts for contingency tables from rounded conditional frequencies," European Journal of Operational Research, Elsevier, vol. 250(1), pages 91-100.
    8. Antonio Frangioni & Fabio Furini & Claudio Gentile, 2016. "Approximated perspective relaxations: a project and lift approach," Computational Optimization and Applications, Springer, vol. 63(3), pages 705-735, April.
    9. Kevin C. Furman & Nicolas W. Sawaya & Ignacio E. Grossmann, 2020. "A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function," Computational Optimization and Applications, Springer, vol. 76(2), pages 589-614, June.
    10. Haibing Lu & Jaideep Vaidya & Vijayalakshmi Atluri & Yingjiu Li, 2015. "Statistical Database Auditing Without Query Denial Threat," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 20-34, February.
    11. Nilay Noyan & Gábor Rudolf, 2015. "Kusuoka representations of coherent risk measures in general probability spaces," Annals of Operations Research, Springer, vol. 229(1), pages 591-605, June.
    12. Xiao-Bai Li & Sumit Sarkar, 2013. "Class-Restricted Clustering and Microperturbation for Data Privacy," Management Science, INFORMS, vol. 59(4), pages 796-812, April.
    13. Xiaojin Zheng & Yutong Pan & Zhaolin Hu, 2021. "Perspective Reformulations of Semicontinuous Quadratically Constrained Quadratic Programs," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 163-179, January.
    14. Jordi Castro & Jordi Cuesta, 2013. "Solving L 1 -CTA in 3D tables by an interior-point method for primal block-angular problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 25-47, April.
    15. Robert Garfinkel & Ram Gopal & Steven Thompson, 2007. "Releasing Individually Identifiable Microdata with Privacy Protection Against Stochastic Threat: An Application to Health Information," Information Systems Research, INFORMS, vol. 18(1), pages 23-41, March.
    16. Jordi Castro, 2007. "A Shortest-Paths Heuristic for Statistical Data Protection in Positive Tables," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 520-533, November.
    17. Bocanegra, Silvana & Castro, Jordi & Oliveira, Aurelio R.L., 2013. "Improving an interior-point approach for large block-angular problems by hybrid preconditioners," European Journal of Operational Research, Elsevier, vol. 231(2), pages 263-273.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:891-909. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.