Optimization Online


Mathematical programming algorithms for spatial cloaking

Alberto Ceselli (alberto.ceselli***at***unimi.it)
Maria Luisa Damiani (damiani***at***di.unimi.it)
Giovanni Righini (giovanni.righini***at***unimi.it)
Diego Valorsi (diego.valorsi***at***me.com)

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 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 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.

Keywords: Steiner trees, branch-and-price, branch-and-cut, 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
Entry Accepted: 06/24/2015
Entry Last Modified: 06/24/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society