A new mathematical optimization-based method for the m-invariance problem

Soft Computing https://doi.org/10.1007/s00500-025-10514-1 OPTIMIZATION A new mathematical optimization-based method for the m-invariance problem Adrián Tobar Nicolau1 ·Jordi Castro2 ·Claudio Gentile3 Accepted: 6 November 2024 © The Author(s) 2025 Abstract Privacy preserving dynamic data publication aims at protecting data while simultaneously preserving its utility when the data is published dynamically. For static data (i.e., data published only once), privacy is based on concepts such as k-anonymity and -differential privacy. In contrast, for dynamic data, the notions of m-invariance and τ-safety are considered. However, most current approaches focus solely on guaranteeing m-invariance and τ-safety without paying attention to the quality of the solution, such as maximizing utility. We propose a new heuristic approach for the NP-hard combinatorial problem of minvariance and τ-safety, which is based on a mathematical optimization column generation scheme. The quality of a solution to m-invariance and τ-safety can be measured by the Information Loss (IL), a value in [0, 100], the closer to 0 the better. We show that our approach improves by far current heuristics, reducing IL by more than 60% and, in some instances, by more than 95%. Keywords Privacy ·Dynamic dataset ·Privacy preserving dynamic data publishing ·Continuous data publishing · m-invariance ·Mathematical optimization ·Column generation 1 Introduction The statistical disclosure control (Hundepool et al. 2012) field is devoted to the private-preserving publication of multiple forms of data. In the microdata publication, a table with information at the individuals level is published. The existing mechanisms for protecting privacy and anonymity of respondents, that is, the users that shared their data, can be broadly classified by two main properties: the data publishing scenario and how they achieve privacy. BJordi Castro [email protected] Adrián Tobar Nicolau [email protected] Claudio Gentile [email protected].it 1Department of Telematics Engineering, Universitat Politècnica de Catalunya, Barcelona 08034, Catalonia 2Department of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona 08034, Catalonia 3Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, Consiglio Nazionale delle Ricerche (IASI-CNR), Roma 00185, Italy Syntactic notions are those that enforce a particular structure on the dataset. On the other hand, semantic notions are those that base their privacy on enforcing certain properties on the algorithms anonymizing the data. Since the inception of statistical disclosure control the most studied publishing scenario was the static data release, that is, publishing the data exactly once. Examples of syntactic notions for this framework are k-anonymity (Sweeney 2002; Samarati 2001), l-diversity (Machanavajjhala et al. 2006) and t-closeness (Li et al. 2007; Rebollo-Monedero et al. 2010), that base their privacy in making batches of tuples indistinguishable, and examples of semantic notions are -differential privacy (Dwork 2006; Dwork et al. 2010; Dwork and Roth 2014) and their variations , which base their protection on distorting the real data with noise. A notable difference between each approach is that syntactic methods assume a classification of microdata in two types, quasi-identifiers, that is, data that is not sensitive to the users but may be used to partially identify them (age, sex, weight, marital status, ...) and sensitive data, i.e., the information that, if associated with a user, would violate his/her privacy (medical records, criminal history, salary, ...). Broadly speaking semantic methods assume stronger attackers and achieve better privacy guarantees but at the expense of worsening significantly data utility. 123 A. T. Nicolau et al. On the other hand syntactic methods achieve a better tradeoff between privacy and utility at the cost of assuming rigid attacker with limited information. With the interest of using alternative data structures a new umbrella of publishing scenarios has appeared, in particular dynamic scenarios. These scenarios are defined by allowing editions of data and the partial or total republication of data in several independent publications. Continuous data publishing (Byun et al. 2006)isa dynamic framework where a dataset is periodically published and in-between publications it is updated via insertion of new tuples, deletion of existing ones, updates of microdata and reinsertion of previously deleted tuples. There are three levels of dynamicity: incremental, the dataset can be increased adding new users, i.e., new rows; external dynamic, rows can be added and deleted but a row from a deleted user cannot be reinserted; fully dynamic, additions, deletions, reinsertions and updates of microdata are possible. Since the first proposal for continuous data publishing due to Byun et al. (2006) several notions and algorithms have been proposed (Xiao and Tao 2007; Fung et al. 2008; Riboni and Bettini 2009;Heetal.2011; Anjum and Raschia 2013; Wang et al. 2016; Amiri et al. 2018; Temuujin et al. 2019; Khan et al. 2022; Attaullah et al. 2022) to handle various attackers and publishing scenarios. Among them minvariance (Xiao and Tao 2007) appeared as the first clear notion that bounds the capacity of an attacker. However minvariance was limited to external dynamic datasets, i.e., datasets which only update inserting and deleting tuples. To overcome these limitations, τ-safety (Anjum and Raschia 2013; Anjum et al. 2017) was proposed. Fundamentally τsafety strengthens m-invariance at the expense of stronger assumptions. The enforcement of m-invariance and related notions may need the usage of counterfeits or the deletion of tuples. The work presented in Tobar Nicolau et al. (2024) studies the minimization of these editions. Alternative approaches such as HD-composition (Bu et al. 2008) and m-Distinct (Li and Zhou 2008) were examples of competing approaches although none has reached the prevalence of minvariance. For a complete overview of the field we refer to Majeed and Lee (2021); Tobar Nicolau et al. (2024). The more recent advancements in continuous data publishing (Zhu et al. 2019; Temuujin et al. 2019; Ren et al. 2019; Khan et al. 2022) are slight improvements of τ-safety and their implementations with the exception of Attaullah et al. (2022) which presents a new enforcement algorithm based on fuzzy clustering. Nevertheless the study of utility preserving enforcement of m-invariance and τ-safety has been almost non-existent and in most cases only improvements of the original algorithm of m-invariance have been carried out. Furthermore, no deep analysis of the combinatorial problem of obtaining m-invariance has been performed so far. The most remarkable feature of our novel approach compared to previous ones is that it is the only method supported by mathematical optimization, whereas the others rely on greedy heuristics to find a solution for m-invariance. m-Invariance and τ-safety are related to the microaggregation problem (Domingo-Ferrer and Mateo-Sanz 2002), a privacy preserving technique that guarantees k-anonymity. k-Anonymity (together with differential privacy) is one of the main privacy models, with applications beyond data protection (Blanco-Justicia et al. 2020; Soria-Comas and Domingo-Ferrer 2018; Domingo-Ferrer and Soria-Comas 2015). Briefly, given a set of points, the goal of microaggregation is to partition them into clusters of a minimum size k(kbeing a parameter of the problem) that minimize the information loss (IL) (to be defined later in Sect. 3). A partition satisfying the constraint on cluster cardinality is referred as feasible clustering, and, of all the feasible clusterings, the one minimizing IL is named the optimal clustering. Microaggregation is known to be a NP-hard problem (Oganian and Domingo-Ferrer 2001). The purpose of m-invariance is also to find an optimal clustering (mbeing the minimum cluster cardinality) with the m-unique constraint, that is, that two points in the same cluster can not have the same value for a particular (sensitive) attribute. For instance, if this particular attribute is named the “color” of the point, m-invariance finds an optimal clustering where all the points of a cluster have a different color. Furthermore, in a framework with republication, for subsequent releases, the set of sensitive attribute values (signature) of all clusters to which a given row/tuple belongs throughout its lifespan remains constant. If all the points of the dataset have initially a different color, then m-invariance reduces to microaggregation, and it is thus also a NP-hard problem. In this work we extend a mathematical optimization-based approach initially developed for microaggregation (Castro et al. 2022a,b)tothem-invariance problem. As it will be shown in the computational results, this new approach provides solutions to the m-invariance problem of much higher quality than previous heuristics. 1.1 Contributions of the work Briefly, the main contributions of the novel approach introduced in this work for the m-invariance problem are: •Significant reduction in information loss (IL): The proposed method reduces IL by more than 60% in most cases and by over 95% in certain instances. This represents a substantial improvement in the preservation of data utility compared to existing methods. •Enhanced privacy preservation: The new approach effectively ensures m-invariance and τ-safety, which are crucial for maintaining privacy in dynamic datasets. The 123 A New mathematical optimization-based method ... method leverages a column generation scheme to optimize the privacy-utility trade-off. •Performance on benchmark datasets: The algorithm was tested on standard instances such as the "Adult" and "IPUMS USA" datasets. The computational results show that the proposed method outperforms existing heuristics in terms of information loss and privacy preservation. •Detailed methodological framework: The paper outlines a comprehensive methodological framework that includes classification, balancing, assignment, partitioning, optimization, and local search. These steps collectively contribute to the improved performance of the proposed method. 2m-invariance and -safety m-Invariance and τ-safety are privacy notions designed to upper bound the probability that an attacker can correctly link a sensitive attribute to a user participating in a dynamic dataset. To present them we first introduce the necessary definitions. Adataset T is a p×dmatrix whose element i,jprovides the value of the attribute Vjof user i. The attributes Vjwith 1≤j<dare quasi-identifiers and Vdis considered to be the sensitive attribute, the “color” of the point, using the notation in Sects.1and 3). The classes of a dataset Tare each set of the partition of the rows of Tin disjoint subsets such that all rows on each class have common quasi-identifiers, particularly, a class Qis a non-empty subset of users with common quasi-identifiers. We denote as SD(Q)the signature of Q, that is, the set of sensitive attribute values of a class Q. For instance, Table 2 has two classes, the first containing tuples 1 and 3 with signature {HIV, ACNE}, and the second composed of tuples 2 and 4 with signature {FLU, COUGH}. In general we denote Tto refer to a dataset and T∗to refer to its anonymized version , that is the version that can be published while preserving the privacy of the individuals from which data has been obtained. If multiple publications of a changing dataset Tare done, we denote as T={T1,...,Tn}the set of versions of Tbefore each publication and T∗={T∗ 1,...,T∗ n}to the set of publications. The row of microdata t, from now on tuple, of a user can belong to several versions of Tand T∗. We denote as lifespan of a tuple haset[x,y]={x,x+1,...,y}that satisfies h∈T∗ ifor all i∈[x,y]and h/∈Tx−1,Ty+1. In other words, the lifespan of a tuple is the interval of publications in which it has participated. If a tuple is deleted and reinserted later, then it can have more than one lifespan. We also define Q(h,T∗)as the class of hin T∗. Table 1 First 2-unique publication Id Age S.D 1 [18–20] HIV 2 [18–20] Flu Table 2 Second 2-unique but not 2-invariant publication Id Age S.D 1 [18–19] HIV 3 [18–19] Acne 2 [20–21] Flu 4 [20–21] Cough Table 3 Second 2-invariant publication Id Age S.D 1 [18–20] HIV 2 [18–20] Flu 3 [19–21] Acne 4 [19–21] Cough We say that a dataset has arbitrary updates if each change to the microdata was not dependent on the previous values. Definition 1 (m-uniqueness) A dataset T∗is m-unique if each class in T∗contains at least mtuples, and all tuples in the class have different sensitive attribute values. Tables 1,2,3are examples of 2-unique datasets. With these previous definitions we can now define m-invariance. Definition 2 (m-invariance) Let T∗={T∗ 1,...,T∗ n}be the distinct publications of an external dynamic dataset, then T∗ is m-invariant if the following conditions hold: •T∗ iis m-unique for all i∈[1,n]. •For any tuple hwith lifespan [x,y]it is satisfied SD(Q(h,T∗ i)) =SD(Q(h,T∗ j)) for all i,j∈[x,y]. In addition to m-uniqueness, the notion of m-invariance imposes that the signature of the class of each tuple, that is SD(Q(h,T∗)), remains constant across all publications in which it participates. Tables 1and 2do not satisfy 2invariance since the signatures of the classes of tuple 1 are {HIV, FLU} ={HIV, ACNE}. On the other hand Tables 1 and 3are 2-invariant. We state now the definition of τ-safety. Definition 3 (τ-safety) Let T∗={T∗ 1,...,T∗ n}be the distinct publications of a fully dynamic dataset with arbitrary updates, then T∗is τ-safe if the following conditions hold: •T∗is m-invariant. 123 A. T. Nicolau et al. •For any tuple hwith lifespans [x,y],[z,t]it is satisfied SD(Q(h,T∗ y)) =SD(Q(h,T∗ z)). The notion of τ-safety extends the condition of minvariance to scenarios where a tuple has multiple lifespans. The motivation behind these definitions is ensuring that the republication of data cannot allow the attacker to deduce sensitive information of any user participating in the dataset. We illustrate previous ideas with the following example of intersection attack. Assume an attacker is searching information of a participant with age =18. Tables 1and 2are two consecutive releases of the dynamic dataset. From Table 1 the attacker deduces that the participant has sensitive value HIV or FLU and from the Table 2that it has HIV or ACNE. Intersecting both cases, the attacker deduces that the attacked tuple has HIV. Such attacks are avoidable using m-invariance, in this case, publishing Table 3instead of Table 2. 2.1 Enforcing m-invariance and -safety Most proposals to enforce m-invariance and τ-safety use the same bucketization algorithm: classification, balancing, assignment and partitioning. We present now the main ideas behind these algorithms and where does our proposal improve the state of the art. A bucket is a data structure which uses the key values as the indices of the buckets, for instance, given a bucket Bthen B[sd]are the tuples in Bwith sensitive value sd. A bucket B has signature SD(B), the set of its keys. A bucket is balanced if for all keys it has the same number of tuples, otherwise it is unbalanced. The bucket algorithms to obtain m-invariance or τ-safety proceed as follows. •Classification: the tuples in the dataset are categorized as new (never published), and old (previously published). This yields two datasets Tnewand Told . Data from Told is stored in multiple bucket datasets in the following manner: for each tuple h, if a bucket Bwith signature SD(Q(h,T∗))1exists, add hto B, otherwise create a bucket with that signature and add hto it. •Balancing: for each bucket created in the classification step, if it is unbalanced, add tuples from Tnewuntil it is balanced, if none available add counterfeits. •Assignment: divide the remaining tuples of Tnewin balanced buckets of at least signature size m. •Partitioning: for each bucket Bdivide it in groups of tuples of size |SD(B)|with one tuple per sensitive value. Generalize each group into a class and publish the dataset. 1Signature of the class of the last publication of h. Fig. 1 Flowchart of the main steps of the algorithm. Classification, balancing, assignment and partition correspond with the steps of the approaches presented in Xiao and Tao (2007)andAnjumetal.(2017). The approach with worse results is discarded. (1) Prior to the optimization step, an instance of two-swapping can be executed to improve the initial solution This algorithm structure allows for a republication which does not increase drastically in time complexity as new versions are published. The bulk of the utility lost is due to steps of assignment and partitioning. Only one method exists in the literature for the assignment phase, presented in Xiao and Tao (2007). Partitioning has two versions, being Anjum and Raschia (2013); Anjum et al. (2017) the only improvements of the original version in Xiao and Tao (2007). Our work is an alternative method that jointly performs the assignment and partitioning steps in a single stage. Performing assignment and partitioning together drastically improves the quality (i.e., reduction of IL) of the solutions computed. Briefly, the assignment and partition steps can be solved by partitioning the set of points of the dataset such that each group has cardinality at least m, and that all points of a group have different values for the sensitive attribute (the “color” of the point). Next sections introduce an integer optimization-based method for the solution of this problem, whose main steps are presented in Fig. 1. 3 Integer optimization models Here we adapt to m-invariance a formulation inspired by the clique partitioning problem with minimum clique size of Ji and Mitchell (2007). Defining as C∗={C⊆{1,...,p}: m≤|C|≤2m−1,c(i)= c(j)for i,j∈C}the set of feasible clusters, where c(i)is the color of element i,the 123 A New mathematical optimization-based method ... m-invariance problem can be formulated as: min  C∈C∗ wCxC s. to  C∈C∗:i∈C xC=1i∈{1,...,p} xC∈{0,1}C∈C∗, (1) where wCwill be defined in below equation (4), xC=1 means that feasible cluster Cappears in the m-invariance provided solution, and the constraints guarantee that all the points are covered by some feasible cluster, and only once, that is, a point can not belong to two different clusters, thus having a partition of {1,...,p}. A widely used measure for evaluating the quality of a clustering is its spread or sum of squared errors (SSE) (Domingo-Ferrer and Mateo-Sanz 2002): SSE = C∈C∗:xC=1 SSEC,(2) where SSECis the spread of cluster Cwhich is defined as SSEC= i∈C (ai−aC)(ai−aC), (3) aibeing a point of the cluster and ¯aC=1 |C|i∈Caiits centroid. The cost wCof cluster Cin the objective function of (1) is wC=1 2|C| i∈C  j∈C Dij,(4) where Dij =(ai−aj)(ai−aj). Using, for every cluster C, the following well-known equivalence (see Castro et al. 2022a):  i∈C (ai−¯aC)(ai−¯aC) =1 2|C| i∈C  j∈C (ai−aj)(ai−aj), (5) we have that wC=SSEC, and then the objective function of (1) equals SSE. Information loss IL is an equivalent measure to SSE, defined as IL =SSE SST ×100,(6) where SST is the total sum of squared errors for all the points: SST = p  i=1 (ai−¯a)(ai−¯a)where ¯a=p i=1ai p.(7) IL always takes values within the range [0,100]; the smaller the IL, the better the clustering. Therefore, the optimal solution of (1) provides the feasible clustering that minimizes the information loss. It is worth noting that in the definition of C∗only clusters of cardinality |C|≤2m−1 are considered, since, as proved in Domingo-Ferrer and Mateo-Sanz (2002), a cluster of cardinality |C|=2mcan be divided in two smaller clusters of mpoints, thus improving the IL. The number of feasible clusters in C∗—that is, the number of variables in the optimization problem (1)—can be huge, so its direct solution by optimization methods is unpractical at least for large sizes. Therefore we resort to heuristics based on two ingredients: •decomposition, •column generation, that will be detailed in next two sections 4 Decomposition The decomposition heuristic is an extension of the heuristic initially developed for the microaggregation problem in Castro et al. (2022b). The decomposition heuristic is based on partitioning the initial set of points P={1,...,p}in ssubsets Pk,k= 1,...,s, such that ∪s k=1Pk=P, and Pk∩Pl=∅for all k,l:k= l. This initial partitioning is obtained by first finding a feasible clustering using the two existing heuristics for m-invariance (namely, the classical approach of Xiao and Tao (2007) and the τ-safety proposal of Anjum and Raschia (2013); Anjum et al. (2017)). Following the original notation, we execute the classification, balancing, assignment and partitioning of the τ-safety proposal to obtain an initial clustering to optimize. Then, points in different clusters of this initial clustering are sequentially added, obtaining the initial partitioning Pk,k=1,...,s. For each subset Pk,k=1,...,s, we then consider the (smaller) optimization problem (1) replacing the feasible set C∗by C∗ k={C⊆Pk:m≤|C|≤2m−1,c(i)= c(j)for i,j∈C}. These soptimization problems, though smaller than the original problem (1), may still have a very large number of optimization variables and are solved using the column generation technique described below in Sect.5. Each of the soptimization problems will provide a set of 123 A. T. Nicolau et al. feasible clusters Ok⊆C∗ kfor the subset of points Pk, and therefore its union O=∪ s k=1Okwill be a feasible clustering for P(suboptimal, but in general of good quality—that is, small information loss). Additionally, the feasible clustering Ois further improved by applying a local search heuristic based on a two-swapping procedure. In short, this procedure analyzes all the feasible swappings between two points iand jlocated in different clusters Ciand Cj, such that c(i)= c(h)for each h∈Cj and c(j)= c(h)for each h∈Ci, performing the swapping of the pair (i,j)that minimizes the objective function of (1). This is repeated until there is no improvement in the objective function. The cost per iteration of this procedure is O(p2/2). The two-swapping heuristics can also be optionally used to obtain the initial partitioning Pk,k=1,...,s, of points. Indeed, two-swapping can be applied to the initial clustering found by the m-invariance heuristics, obtaining a new clustering with a smaller objective function. This new clustering is then used to obtain the initial partitioning. The main steps of the decomposition heuristic can be summarized as follows: 1. Apply m-invariance heuristics to get an initial feasible clustering. 2. Optionally, apply the two-swapping heuristic to this initial feasible clustering. 3. Compute the initial partitioning Pk,k=1,...,s,of points from the initial feasible clustering. 4. Apply the column generation optimization algorithm to each set of points Pk, obtaining a feasible clustering Ok for all k=1,...,s. Note that this step can be performed in parallel for all the sets k=1,...,s. 5. Compute O=∪ s k=1Ok, which is a feasible clustering for P. 6. Finally, apply the two-swapping heuristic to the feasible clustering O. 5 Column generation approach In this section we describe the novel column generation approach developed for the m-invariance problem, as an extension of the procedure initially developed for microaggregation in Castro et al. (2022a). The novelty of the approach is the definition in the column generation procedure of a master and subproblem that guarantee that the solutions computed are m-invariant. Column generation is a well-known approach in mathematical optimization for the solution of linear programming problems with a large number of variables (Desrosiers and Lübbecke 2005). Given a general linear programming problem min  j∈V cjxj s. to  j∈V Ejxj=b xj≥0j∈V, (8) where Ej∈Rris the vector with the contribution of variable xjto the rconstraints of the problem (we assume that |V|>r), the simplex method optimizes (8) by finding a set of variables B⊂V(named set of basic variables) such that: (i) |B|=r; (ii) the rvectors Ej,j∈B, are linearly independent; (iii) and for any variable j∈N=V\B (named set of nonbasic variables), we have that the values μj=cj−λEj(named reduced costs) are non-negative, where λ=(E B)−1cB∈Rris the set of dual variables or Lagrange’s multipliers of the constraints of (8), and EBand cBare respectively a matrix and vector formed by the vectors Ejand coefficients cjsuch that j∈B. When the number of variables |V|is very large, we can initially consider a subset ¯ V⊆Vof variables. Problem (8) can thus be solved with the simplex method replacing Vby ¯ V, obtaining the sets of basic and nonbasic variables ¯ Band ¯ N. The simplex method guarantees that μj≥0for j∈¯ N. If in addition μj≥0for j∈V\¯ Vwe can certificate that the current solution is also optimal for (8). Otherwise, there is some j∈V\¯ Vwith μj<0. Column generation then solves the subproblem min cj−λEj,j∈V\¯ V,(9) where λis the vector of dual variables provided by the previous solution of (8)using ¯ V, and cjrepresents the cost of the variable associated to column Ej. The solution of (9) provides both a new column Ejand its associated reduced cost μj. If the reduced cost is non-negative, we conclude that the current solution (x¯ B,x¯ N)is optimal. Otherwise, if the reduced cost is negative, we add the new column Ejto the set of already generated columns (that is, ¯ V←¯ V∪{j}), and reoptimize again (8). This procedure is repeated until (9) provides a non-negative reduced cost. Applying the previous procedure to the m-invariance problem, the column generation approach enables us to solve the continuous relaxation of (1) considering only a subset ¯ C of C∗: min  C∈¯ C wCxC s. to  C∈¯ C:i∈C xC=1i∈P xC∈[0,1]C∈¯ C, (10) 123 A New mathematical optimization-based method ... where the original binary constraints xC∈{0,1}have been relaxed and replaced by xC∈[0,1]. At each iteration we test if the solution of (10) is optimal for the continuous relaxation of (1) by solving the following optimization problem for each size η∈{m,...,2m−1}: min 1 2η(i,j)∈ADijzij −i∈Pλi η−1yi s. to yi=(j,i)∈δ− izji +(i,j)∈δ+ izij i∈P (i,j)∈Azij =η(η −1)/2 yi−(η −1)zij ≥0ij ∈A zij ∈{0,1}ij ∈A (11) where A={(i,j)|i,j∈P,i<j,c(i)= c(j)},δ+ i= {(i,j)∈A},δ− i={(j,i)∈A}, and λiis the value of the dual variable with respect to constraint for point iin (10). The objective function (11) is the reduced cost of a new feasible cluster represented by binary variables zij (which are 1 if points i,jare in the cluster, and 0 otherwise). Problem (11) is solved by adapting the method described in Castro et al. (2022a)tothem-invariance case by simply fixing to zero zij when (i,j)/∈A. Within the decomposition approach of Sect. 4, problem (10) is solved for each subset of points Pk,k=1,...,s, and a subset Akof Ais defined accordingly. The previous column generation algorithm provides an optimal solution to the continuous relaxation of (1). If all the variables xCare either 0 or 1, this solution is optimal for the integer optimization model (1). If some variables xC are fractional, some rounding heuristic is needed to obtain a (suboptimal but in general good quality) binary solution. In most cases, the best binary solution was obtained by solving (10) with the last set of clusters ¯ Ccomputed, and replacing bounds xC∈[0,1]by binary constraints xC∈{0,1}. Since column generation is in essence a particular strategy to implement the simplex method in problems with a huge number of variables, its computational complexity is the same as the one of the simplex method, which is exponential in the worst case. However, the empirical complexity of the simplex method is proportional to the number of constraints and variables. Unfortunately, for a large database, the linear relaxation of the m-invariance problem (1) provides an exponential number of variables, which means that even the empirical complexity for this problem can be exponential. Although the column generation is designed to generate only the most promising columns, the number of columns that will be generated cannot be known or predicted a priori, and it is problem dependent. In practice a maximum number of columns generated, or time limit, is required to prematurely stop the procedure, hopefully with a good solution. This was done in all the computational tests performed, as described in the next section. Despite this complexity results, column generation was able to obtain solutions of much higher quality than those computed by current heuristics for m-invariance. 6 Computational tests The column generation algorithm for m-invariance introduced in this paper has been implemented in C++. The solution of the linear optimization problems (10) and integer optimization subproblems (11) of the column generation algorithm were computed with the CPLEX solver. Alternatively, subproblems (11) can also be solved, for small values of m, using the implicit enumeration scheme of Aloise et al. (2014). A parallel version of Step 4 of the decomposition approach of Sect.4was implemented using OpenMP. The implementation was tested with the “Adult” (Dua and Graff 2017) and the “IPUMS USA” (Ruggles et al. 2023) datasets. Both datasets have been used in several previous works on syntactic privacy for dynamic data publishing. From the “Adult” dataset the attributes age, sex and education-num have been used as quasi-identifiers and occupation as sensitive attribute (that is, “occupation” is the “color” attribute according to the notation of Sect. 3). For the “IPUMS” dataset we considered a data extract with columns sex, age, educ and occupation, using occupation as sensitive attribute and the rest as quasi-identifiers. We used samples of 1500 and 1000 randomly selected users for Adult and IPUMS respectively. These two datasets were considered for their prevalent appearance in the related literature and to reflect two scenarios depending on the number of unique sensitive values. The Adult dataset has 13 unique sensitive values while IPUMS has 281 unique sensitive values. We tested the performance of our approach in comparison with the implementations of assignment and partitioning of Xiao and Tao (2007) (denoted as “Classic”), and Anjum et al. (2017) (denoted as “Tau”). These implementations are the two main approaches in the existing literature. 6.1 Results Tables 4and 5show the results obtained for, respectively, the “Adult” and “IPUMS” datasets. Each dataset was solved for the cluster sizes m∈{3,5,7}and number of subsets s∈{40,20,10,5,2}, which amounts to 15 runs of the algorithm with each dataset. The runs were carried out on a DELL PowerEdge R7525 with two 2.4 GHz AMD EPYC 7532 CPUs (128 total cores), under a GNU/Linux operating system (openSuse 15.3). The columns of the tables provide results for the different steps of the decomposition algorithm: step 1: m-invariance heuristics (used to partition the set of points in step 3); step 4: optimization with column generation for each subset of 123 A. T. Nicolau et al. Table 4 Computational results for the adult dataset with two-swapping applied only after column generation Cluster size mm-invariance heuristics Column generation from heuristic solution Two-swapping Algorithm Time (s) IL sTime(s)IL Time (s) IL 3 Classic 0.14 66.76 40 0.09 15.57 42.25 2.08 Tau 0.02 39.03 20 0.19 10.50 38.31 2.15 10 1.49 7.47 32.07 2.17 5 16.33 5.49 26.87 2.16 2 137.1 3.13 14.17 1.86 5 Classic 0.07 81.46 40 0.49 29.73 95.31 8.77 Tau 0.14 51.84 20 13.27 23.83 98.79 9.03 10 1082.9 18.33 73.16 9.03 5 5044.7 21.28 69.41 9.01 2 7232.3 23.46 64.28 8.79 7 Classic 0.37 88.73 40 364.16 44.17 151.65 22.44 Tau 0.12 57.97 20 387.76 46.65 172.49 22.73 10 4321.1 43.46 137.92 22.79 5 5143.9 47.84 141.83 22.43 2 7025.7 48.95 145.08 22.89 Table 5 Computational results for the IPUMS dataset with two-swapping applied only after column generation Cluster size mm-invariance heuristics Column generation from heuristic solution Two-swapping Algorithm Time (s) IL sTime(s)IL Time (s) IL 3 Classic 0.04 67.20 40 0.06 11.91 10.31 0.71 Tau 0.02 55.39 20 0.07 6.10 8.97 0.76 10 0.12 3.31 7.33 0.61 5 0.68 1.56 5.14 0.51 2 4.29 0.74 2.33 0.49 5 Classic 0.03 82.58 40 0.08 26.26 23.27 1.34 Tau 0.03 67.07 20 0.78 13.80 23.06 1.42 10 26.31 7.00 18.80 1.35 5 2421.8 3.63 12.74 1.19 2 7208.3 5.51 8.28 1.04 7 Classic 0.03 86.38 40 20.09 33.73 38.37 2.28 Tau 0.03 72.83 20 415.86 19.62 37.68 2.19 10 1141.2 15.39 34.78 2.31 5 3602.8 17.40 27.64 2.14 2 3613.9 12.15 16.75 1.88 points obtained from the solution of the previous step, the m-invariance heuristics; step 6: two-swapping heuristic. The execution of the two state-of-the-art m-invariance heuristics (“Classic” and “Tau”) is independent of s, then the values of these columns are common to all the rows with the same m. For each step we provide the computational time, and the information loss (IL) obtained (which monotonically decreases with the steps). For step 1, the results with the “Classic” and “Tau” heuristic are given; “Tau” always outperformed “Classic” in terms of IL, then it was chosen as the initial clustering to partition the set of points in ssubsets. Executions of the optimization stage were multithreaded using OpenMP, the number of threads being equal to the number of subsets s. For this reason, times in the table refer to “wall-clock” time, instead of CPU time. We set both a time limit (of two hours) and a limit on the number of columns generated, for each column generation process. Usually, the smaller the s, the larger (and likely more difficult) are the column generation problems, and a longer solution time can be expected. However, in some cases, these larger column gen123 A New mathematical optimization-based method ... Table 6 Computational results for the adult dataset with two-swapping applied before and after the column generation heuristic Cluster size mm-invariance heuristics Two-swapping 1 Column generation from two-swapping 1 Two-swapping 2 Alg Time (s) IL Time (s) IL sTime(s)IL Time (s) IL 3 Classic 0.14 66.76 44.32 2.23 40 0.05 2.22 1.30 2.16 Tau 0.02 39.03 20 0.07 2.17 3.05 1.96 10 0.62 2.05 4.04 1.90 5 1.95 1.92 4.73 1.79 2 48.17 1.74 4.18 1.64 5 Classic 0.07 81.46 104.22 9.76 40 0.51 9.76 2.98 9.64 Tau 0.14 51.84 20 17.17 9.69 11.57 9.53 10 1292.4 9.38 17.54 8.79 5 5045.9 9.76 0.10 9.76 2 7202.6 9.76 0.08 9.76 7 Classic 0.37 88.73 183.14 22.78 40 219.32 22.78 0.17 22.78 Tau 0.12 57.97 20 388.79 22.78 0.16 22.78 10 907.78 22.78 0.21 22.78 5 7221.4 22.78 0.15 22.78 2 2847.8 22.78 0.13 22.78 Table 7 Computational results for the IPUMS dataset with two-swapping applied before and after the column generation heuristic Cluster size mm-invariance heuristics Two-swapping 1 Column generation from two-swapping 1 Two-swapping 2 Alg Time (s) IL Time (s) IL sTime(s)IL Time (s) IL 3 Classic 0.04 67.20 11.01 0.74 40 0.03 0.69 0.16 0.66 Tau 0.04 55.39 20 0.03 0.67 0.65 0.57 10 0.07 0.60 0.33 0.56 5 0.38 0.57 0.54 0.53 2 3.21 0.46 0.55 0.38 5 Classic 0.03 82.58 24.11 1.34 40 0.06 1.34 0.07 1.34 Tau 0.03 67.07 20 1.68 1.32 0.96 1.20 10 40.78 1.15 1.15 1.08 5 2169.8 1.06 0.85 1.00 2 3758.9 0.83 0.60 0.81 7 Classic 0.03 86.38 44.06 2.41 40 301.25 2.41 0.20 2.41 Tau 0.03 72.83 20 445.41 2.34 1.43 2.26 10 1070.4 2.17 2.60 1.98 5 427.02 2.19 0.52 2.17 2 2822.4 2.33 0.48 2.32 Table 8 Summary: best IL results with classic and tau heuristics, and with the new optimization approach Instance mIL Classic Tau Optimization Adult 3 66.76 39.03 1.64 5 81.46 51.84 8.77 7 88.73 57.97 22.43 IPUMS 3 67.20 55.39 0.38 5 82.58 67.07 0.81 7 86.38 72.83 1.88 123