Mathematical Programming Algorithms for Spatial Cloaking

Alberto Ceselli (), Maria Luisa Damiani (), Giovanni Righini () and Diego Valorsi ()
Additional contact information
Alberto Ceselli: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy
Maria Luisa Damiani: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy
Giovanni Righini: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy
Diego Valorsi: Dipartimento di Informatica, Università degli Studi di Milano, 20133 Milano, Italy

INFORMS Journal on Computing, 2018, vol. 30, issue 4, 710-723

Abstract: We consider a combinatorial optimization problem for spatial information cloaking. The problem requires computing one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices in each arborescence is reached. For a single arborescence case, we solve the problem to optimality by designing a branch-and-cut exact algorithm. Then we adapt this algorithm for the purpose of pricing out columns in an exact branch-and-price algorithm for the multiarborescence version. We also propose a branch-and-price-based heuristic algorithm, where branching and pricing, respectively, act as diversification and intensification mechanisms. The heuristic consistently finds optimal or near optimal solutions within a computing time, which can be three to four orders of magnitude smaller than that required for exact optimization. From an application point of view, our computational results are useful to calibrate the values of relevant parameters, determining the obfuscation level that is achieved. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0813 .

Keywords: Steiner trees; branch and price; branch and cut (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0813 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:4:p:710-723

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().