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.
Mathematical Programming Algorithms for Spatial Cloaking / A. Ceselli, M.L. Damiani, G. Righini, D. Valorsi. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 30:4(2018), pp. 710-723. [10.1287/ijoc.2018.0813]
Mathematical Programming Algorithms for Spatial Cloaking
A. Ceselli
Primo
;M.L. DamianiSecondo
;G. RighiniPenultimo
;
2018
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.File | Dimensione | Formato | |
---|---|---|---|
cloaking_AIR.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
597.87 kB
Formato
Adobe PDF
|
597.87 kB | Adobe PDF | Visualizza/Apri |
ijoc.2018.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
1.84 MB
Formato
Adobe PDF
|
1.84 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.