Optimization Online


A fix-and-relax heuristic for controlled tabular adjustment

Daniel Baena (daniel.baena***at***upc.edu)
Jordi Castro (jordi.castro***at***upc.edu)

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

Keywords: Fix-and-Relax ; Mixed-integer Linear Programming ; Controlled Tabular Adjustment ; Primal Heuristics ; Feasibility Pump ; Statistical Disclosure Control

Category 1: Applications -- Science and Engineering

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

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.

Download: [PDF]

Entry Submitted: 07/26/2013
Entry Accepted: 07/26/2013
Entry Last Modified: 08/02/2013

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