  


Mathematical programming algorithms for spatial cloaking
Alberto Ceselli (alberto.ceselliunimi.it) Abstract: 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 branchandcut exact algorithm. Then we use the same algorithm for the purpose of pricing out columns in an exact branchandprice algorithm for the multiarborescence version. We also propose a branchandpricebased heuristic algorithm, where branching and pricing respectively act as diversification and intensification mechanisms. The heuristic consistently finds optimal or nearoptimal 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. Keywords: Steiner trees, branchandprice, branchandcut, spatial cloaking Category 1: Combinatorial Optimization Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Applications  Science and Engineering Citation: technical report, University of Milan, Department of Computer Science, June 2015. Currently submitted for publication. Download: [PDF] Entry Submitted: 06/24/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  