Mathematical Programming Algorithms for Spatial Cloaking
研究空间信息隐匿的组合优化问题，设计精确和启发式算法求解最小化顶点数的树状结构，计算时间比精确优化快三到四个数量级。
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 .