Controlled tabular adjustment (CTA) is an emerging protection technique for tabular data protection. CTA formulates a mixed integer linear programming problem, which is tough for tables of moderate size. Finding a feasible initial solution may even be a challenging task for large instances. On the other hand, end users of tabular data protection techniques give priority to fast executions and are thus satisfied in practice with suboptimal solutions. In this work the fix-and-relax strategy is applied to large CTA instances. Fix-and-relax is based on partitioning the set of binary variables into clusters to selectively explore a smaller branch-and-cut tree. We report extensive computational results on a set of real and random CTA instances. Fix-and-relax is shown to be competitive compared to plain CPLEX branch-and-cut in terms of quickly finding either a feasible solution or a good upper bound in difficult instances.
Citation
D. Baena, J. Castro, A fix-and-relax heuristic for controlled tabular adjustment, Research Report DR 2013/02, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2013.
Article
View A fix-and-relax heuristic for controlled tabular adjustment