We consider a combinatorial optimization problem for spatial information cloaking. The problem requires to compute 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 use the same algorithm for the purpose of pricing out columns in an exact branch-and-price algorithm for the multi-arborescence version. We also propose a branch-and-price-based heuristic algorithm, where branching and pricing respectively act as diversi cation and intensi cation mechanisms. The heuristic consistently nds 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.
Download Full PDF Version (Non-Commercial Use)