So Compu ing
h ps://doi.o g/10.1007/s00500-025-10514-1
OPTIMIZATION
A new ma hema ical op imiza ion-based me hod o he m-in a iance
p oblem
Ad ián Toba Nicolau1
·Jo di Cas o2
·Claudio Gen ile3
Accep ed: 6 No embe 2024
© The Au ho (s) 2025
Abs ac
P i acy p ese ing dynamic da a publica ion aims a p o ec ing da a while simul aneously p ese ing i s u ili y when he da a
is published dynamically. Fo s a ic da a (i.e., da a published only once), p i acy is based on concep s such as k-anonymi y
and -di e en ial p i acy. In con as , o dynamic da a, he no ions o m-in a iance and τ-sa e y a e conside ed. Howe e ,
mos cu en app oaches ocus solely on gua an eeing m-in a iance and τ-sa e y wi hou paying a en ion o he quali y o
he solu ion, such as maximizing u ili y. We p opose a new heu is ic app oach o he NP-ha d combina o ial p oblem o m-
in a iance and τ-sa e y, which is based on a ma hema ical op imiza ion column gene a ion scheme. The quali y o a solu ion
o m-in a iance and τ-sa e y can be measu ed by he In o ma ion Loss (IL), a alue in [0, 100], he close o 0 he be e . We
show ha ou app oach imp o es by a cu en heu is ics, educing IL by mo e han 60% and, in some ins ances, by mo e
han 95%.
Keywo ds P i acy ·Dynamic da ase ·P i acy p ese ing dynamic da a publishing ·Con inuous da a publishing ·
m-in a iance ·Ma hema ical op imiza ion ·Column gene a ion
1 In oduc ion
The s a is ical disclosu e con ol (Hundepool e al. 2012)
ield is de o ed o he p i a e-p ese ing publica ion o mul-
iple o ms o da a. In he mic oda a publica ion, a able wi h
in o ma ion a he indi iduals le el is published. The exis ing
mechanisms o p o ec ing p i acy and anonymi y o espon-
den s, ha is, he use s ha sha ed hei da a, can be b oadly
classi ied by wo main p ope ies: he da a publishing sce-
na io and how hey achie e p i acy.
BJo di Cas o
[email p o ec ed]
Ad ián Toba Nicolau
[email p o ec ed]
Claudio Gen ile
[email p o ec ed].i
1Depa men o Telema ics Enginee ing, Uni e si a
Poli ècnica de Ca alunya, Ba celona 08034, Ca alonia
2Depa men o S a is ics and Ope a ions Resea ch, Uni e si a
Poli ècnica de Ca alunya, Ba celona 08034, Ca alonia
3Is i u o di Analisi dei Sis emi ed In o ma ica “A. Rube i”,
Consiglio Nazionale delle Rice che (IASI-CNR), Roma
00185, I aly
Syn ac ic no ions a e hose ha en o ce a pa icula s uc-
u e on he da ase . On he o he hand, seman ic no ions a e
hose ha base hei p i acy on en o cing ce ain p ope ies
on he algo i hms anonymizing he da a. Since he incep ion
o s a is ical disclosu e con ol he mos s udied publishing
scena io was he s a ic da a elease, ha is, publishing he
da a exac ly once. Examples o syn ac ic no ions o his
amewo k a e k-anonymi y (Sweeney 2002; Sama a i 2001),
l-di e si y (Machana ajjhala e al. 2006) and -closeness
(Li e al. 2007; Rebollo-Monede o e al. 2010), ha base
hei p i acy in making ba ches o uples indis inguishable,
and examples o seman ic no ions a e -di e en ial p i acy
(Dwo k 2006; Dwo k e al. 2010; Dwo k and Ro h 2014)
and hei a ia ions , which base hei p o ec ion on dis o -
ing he eal da a wi h noise. A no able di e ence be ween
each app oach is ha syn ac ic me hods assume a classi i-
ca ion o mic oda a in wo ypes, quasi-iden i ie s, ha is,
da a ha is no sensi i e o he use s bu may be used o pa -
ially iden i y hem (age, sex, weigh , ma i al s a us, ...) and
sensi i e da a, i.e., he in o ma ion ha , i associa ed wi h a
use , would iola e his/he p i acy (medical eco ds, c imi-
nal his o y, sala y, ...). B oadly speaking seman ic me hods
assume s onge a acke s and achie e be e p i acy gua an-
ees bu a he expense o wo sening signi ican ly da a u ili y.
123
A. T. Nicolau e al.
On he o he hand syn ac ic me hods achie e a be e ade-
o be ween p i acy and u ili y a he cos o assuming igid
a acke wi h limi ed in o ma ion.
Wi h he in e es o using al e na i e da a s uc u es a new
umb ella o publishing scena ios has appea ed, in pa icula
dynamic scena ios. These scena ios a e de ined by allowing
edi ions o da a and he pa ial o o al epublica ion o da a
in se e al independen publica ions.
Con inuous da a publishing (Byun e al. 2006)isa
dynamic amewo k whe e a da ase is pe iodically published
and in-be ween publica ions i is upda ed ia inse ion o new
uples, dele ion o exis ing ones, upda es o mic oda a and
einse ion o p e iously dele ed uples. The e a e h ee le -
els o dynamici y: inc emen al, he da ase can be inc eased
adding new use s, i.e., new ows; ex e nal dynamic, ows can
be added and dele ed bu a ow om a dele ed use canno be
einse ed; ully dynamic, addi ions, dele ions, einse ions
and upda es o mic oda a a e possible.
Since he i s p oposal o con inuous da a publishing
due o Byun e al. (2006) se e al no ions and algo i hms
ha e been p oposed (Xiao and Tao 2007; Fung e al. 2008;
Riboni and Be ini 2009;Hee al.2011; Anjum and Raschia
2013; Wang e al. 2016; Ami i e al. 2018; Temuujin e al.
2019; Khan e al. 2022; A aullah e al. 2022) o handle
a ious a acke s and publishing scena ios. Among hem m-
in a iance (Xiao and Tao 2007) appea ed as he i s clea
no ion ha bounds he capaci y o an a acke . Howe e m-
in a iance was limi ed o ex e nal dynamic da ase s, i.e.,
da ase s which only upda e inse ing and dele ing uples. To
o e come hese limi a ions, τ-sa e y (Anjum and Raschia
2013; Anjum e al. 2017) was p oposed. Fundamen ally τ-
sa e y s eng hens m-in a iance a he expense o s onge
assump ions. The en o cemen o m-in a iance and ela ed
no ions may need he usage o coun e ei s o he dele-
ion o uples. The wo k p esen ed in Toba Nicolau e al.
(2024) s udies he minimiza ion o hese edi ions. Al e na-
i e app oaches such as HD-composi ion (Bu e al. 2008) and
m-Dis inc (Li and Zhou 2008) we e examples o compe ing
app oaches al hough none has eached he p e alence o m-
in a iance. Fo a comple e o e iew o he ield we e e o
Majeed and Lee (2021); Toba Nicolau e al. (2024).
The mo e ecen ad ancemen s in con inuous da a pub-
lishing (Zhu e al. 2019; Temuujin e al. 2019; Ren e al.
2019; Khan e al. 2022) a e sligh imp o emen s o τ-sa e y
and hei implemen a ions wi h he excep ion o A aullah
e al. (2022) which p esen s a new en o cemen algo i hm
based on uzzy clus e ing. Ne e heless he s udy o u il-
i y p ese ing en o cemen o m-in a iance and τ-sa e y has
been almos non-exis en and in mos cases only imp o e-
men s o he o iginal algo i hm o m-in a iance ha e been
ca ied ou . Fu he mo e, no deep analysis o he combina o-
ial p oblem o ob aining m-in a iance has been pe o med
so a . The mos ema kable ea u e o ou no el app oach
compa ed o p e ious ones is ha i is he only me hod sup-
po ed by ma hema ical op imiza ion, whe eas he o he s ely
on g eedy heu is ics o ind a solu ion o m-in a iance.
m-In a iance and τ-sa e y a e ela ed o he mic oagg e-
ga ion p oblem (Domingo-Fe e and Ma eo-Sanz 2002), a
p i acy p ese ing echnique ha gua an ees k-anonymi y.
k-Anonymi y ( oge he wi h di e en ial p i acy) is one o
he main p i acy models, wi h applica ions beyond da a
p o ec ion (Blanco-Jus icia e al. 2020; So ia-Comas and
Domingo-Fe e 2018; Domingo-Fe e and So ia-Comas
2015). B ie ly, gi en a se o poin s, he goal o mic oag-
g ega ion is o pa i ion hem in o clus e s o a minimum size
k(kbeing a pa ame e o he p oblem) ha minimize he
in o ma ion loss (IL) ( o be de ined la e in Sec . 3). A pa i-
ion sa is ying he cons ain on clus e ca dinali y is e e ed
as easible clus e ing, and, o all he easible clus e ings, he
one minimizing IL is named he op imal clus e ing. Mic oag-
g ega ion is known o be a NP-ha d p oblem (Oganian and
Domingo-Fe e 2001).
The pu pose o m-in a iance is also o ind an op imal
clus e ing (mbeing he minimum clus e ca dinali y) wi h
he m-unique cons ain , ha is, ha wo poin s in he same
clus e can no ha e he same alue o a pa icula (sensi i e)
a ibu e. Fo ins ance, i his pa icula a ibu e is named he
“colo ” o he poin , m-in a iance inds an op imal clus e ing
whe e all he poin s o a clus e ha e a di e en colo . Fu -
he mo e, in a amewo k wi h epublica ion, o subsequen
eleases, he se o sensi i e a ibu e alues (signa u e) o
all clus e s o which a gi en ow/ uple belongs h oughou
i s li espan emains cons an . I all he poin s o he da ase
ha e ini ially a di e en colo , hen m-in a iance educes
o mic oagg ega ion, and i is hus also a NP-ha d p oblem.
In his wo k we ex end a ma hema ical op imiza ion-based
app oach ini ially de eloped o mic oagg ega ion (Cas o
e al. 2022a,b) o hem-in a iance p oblem. As i will be
shown in he compu a ional esul s, his new app oach p o-
ides solu ions o he m-in a iance p oblem o much highe
quali y han p e ious heu is ics.
1.1 Con ibu ions o he wo k
B ie ly, he main con ibu ions o he no el app oach in o-
duced in his wo k o he m-in a iance p oblem a e:
•Signi ican educ ion in in o ma ion loss (IL): The p o-
posed me hod educes IL by mo e han 60% in mos cases
and by o e 95% in ce ain ins ances. This ep esen s a
subs an ial imp o emen in he p ese a ion o da a u il-
i y compa ed o exis ing me hods.
•Enhanced p i acy p ese a ion: The new app oach e ec-
i ely ensu es m-in a iance and τ-sa e y, which a e
c ucial o main aining p i acy in dynamic da ase s. The
123
A New ma hema ical op imiza ion-based me hod ...
me hod le e ages a column gene a ion scheme o op i-
mize he p i acy-u ili y ade-o .
•Pe o mance on benchma k da ase s: The algo i hm was
es ed on s anda d ins ances such as he "Adul " and
"IPUMS USA" da ase s. The compu a ional esul s show
ha he p oposed me hod ou pe o ms exis ing heu is ics
in e ms o in o ma ion loss and p i acy p ese a ion.
•De ailed me hodological amewo k: The pape ou -
lines a comp ehensi e me hodological amewo k ha
includes classi ica ion, balancing, assignmen , pa i ion-
ing, op imiza ion, and local sea ch. These s eps collec-
i ely con ibu e o he imp o ed pe o mance o he
p oposed me hod.
2m-in a iance and -sa e y
m-In a iance and τ-sa e y a e p i acy no ions designed o
uppe bound he p obabili y ha an a acke can co ec ly
link a sensi i e a ibu e o a use pa icipa ing in a dynamic
da ase . To p esen hem we i s in oduce he necessa y de -
ini ions.
Ada ase T is a p×dma ix whose elemen i,jp o ides
he alue o he a ibu e Vjo use i. The a ibu es Vjwi h
1≤j<da e quasi-iden i ie s and Vdis conside ed o be he
sensi i e a ibu e, he “colo ” o he poin , using he no a ion
in Sec s.1and 3).
The classes o a da ase Ta e each se o he pa i ion o
he ows o Tin disjoin subse s such ha all ows on each
class ha e common quasi-iden i ie s, pa icula ly, a class Qis
a non-emp y subse o use s wi h common quasi-iden i ie s.
We deno e as SD(Q) he signa u e o Q, ha is, he se o
sensi i e a ibu e alues o a class Q. Fo ins ance, Table 2
has wo classes, he i s con aining uples 1 and 3 wi h sig-
na u e {HIV, ACNE}, and he second composed o uples 2
and 4 wi h signa u e {FLU, COUGH}.
In gene al we deno e T o e e o a da ase and T∗ o
e e o i s anonymized e sion , ha is he e sion ha
can be published while p ese ing he p i acy o he indi-
iduals om which da a has been ob ained. I mul iple
publica ions o a changing da ase Ta e done, we deno e
as T={T1,...,Tn} he se o e sions o Tbe o e each
publica ion and T∗={T∗
1,...,T∗
n} o he se o publica-
ions.
The ow o mic oda a , om now on uple, o a use can
belong o se e al e sions o Tand T∗. We deno e as li espan
o a uple hase [x,y]={x,x+1,...,y} ha sa is ies
h∈T∗
i o all i∈[x,y]and h/∈Tx−1,Ty+1. In o he
wo ds, he li espan o a uple is he in e al o publica ions
in which i has pa icipa ed. I a uple is dele ed and einse ed
la e , hen i can ha e mo e han one li espan. We also de ine
Q(h,T∗)as he class o hin T∗.
Table 1 Fi s 2-unique
publica ion Id Age S.D
1 [18–20] HIV
2 [18–20] Flu
Table 2 Second 2-unique bu
no 2-in a ian publica ion Id Age S.D
1 [18–19] HIV
3 [18–19] Acne
2 [20–21] Flu
4 [20–21] Cough
Table 3 Second 2-in a ian
publica ion Id Age S.D
1 [18–20] HIV
2 [18–20] Flu
3 [19–21] Acne
4 [19–21] Cough
We say ha a da ase has a bi a y upda es i each change
o he mic oda a was no dependen on he p e ious alues.
De ini ion 1 (m-uniqueness) A da ase T∗is m-unique i
each class in T∗con ains a leas m uples, and all uples
in he class ha e di e en sensi i e a ibu e alues.
Tables 1,2,3a e examples o 2-unique da ase s. Wi h
hese p e ious de ini ions we can now de ine m-in a iance.
De ini ion 2 (m-in a iance) Le T∗={T∗
1,...,T∗
n}be he
dis inc publica ions o an ex e nal dynamic da ase , hen T∗
is m-in a ian i he ollowing condi ions hold:
•T∗
iis m-unique o all i∈[1,n].
•Fo any uple hwi h li espan [x,y]i is sa is ied
SD(Q(h,T∗
i)) =SD(Q(h,T∗
j)) o all i,j∈[x,y].
In addi ion o m-uniqueness, he no ion o m-in a iance
imposes ha he signa u e o he class o each uple, ha
is SD(Q(h,T∗)), emains cons an ac oss all publica ions
in which i pa icipa es. Tables 1and 2do no sa is y 2-
in a iance since he signa u es o he classes o uple 1 a e
{HIV, FLU} ={HIV, ACNE}. On he o he hand Tables 1
and 3a e 2-in a ian .
We s a e now he de ini ion o τ-sa e y.
De ini ion 3 (τ-sa e y) Le T∗={T∗
1,...,T∗
n}be he dis-
inc publica ions o a ully dynamic da ase wi h a bi a y
upda es, hen T∗is τ-sa e i he ollowing condi ions hold:
•T∗is m-in a ian .
123
A. T. Nicolau e al.
•Fo any uple hwi h li espans [x,y],[z, ]i is sa is ied
SD(Q(h,T∗
y)) =SD(Q(h,T∗
z)).
The no ion o τ-sa e y ex ends he condi ion o m-
in a iance o scena ios whe e a uple has mul iple li espans.
The mo i a ion behind hese de ini ions is ensu ing ha
he epublica ion o da a canno allow he a acke o deduce
sensi i e in o ma ion o any use pa icipa ing in he da ase .
We illus a e p e ious ideas wi h he ollowing example o
in e sec ion a ack. Assume an a acke is sea ching in o ma-
ion o a pa icipan wi h age =18. Tables 1and 2a e wo
consecu i e eleases o he dynamic da ase . F om Table 1
he a acke deduces ha he pa icipan has sensi i e alue
HIV o FLU and om he Table 2 ha i has HIV o ACNE.
In e sec ing bo h cases, he a acke deduces ha he a acked
uple has HIV. Such a acks a e a oidable using m-in a iance,
in his case, publishing Table 3ins ead o Table 2.
2.1 En o cing m-in a iance and -sa e y
Mos p oposals o en o ce m-in a iance and τ-sa e y use
he same bucke iza ion algo i hm: classi ica ion, balanc-
ing, assignmen and pa i ioning. We p esen now he main
ideas behind hese algo i hms and whe e does ou p oposal
imp o e he s a e o he a .
A bucke is a da a s uc u e which uses he key alues as
he indices o he bucke s, o ins ance, gi en a bucke B hen
B[sd]a e he uples in Bwi h sensi i e alue sd. A bucke B
has signa u e SD(B), he se o i s keys. A bucke is balanced
i o all keys i has he same numbe o uples, o he wise i
is unbalanced. The bucke algo i hms o ob ain m-in a iance
o τ-sa e y p oceed as ollows.
•Classi ica ion: he uples in he da ase a e ca ego ized as
new (ne e published), and old (p e iously published).
This yields wo da ase s Tnewand Told . Da a om Told
is s o ed in mul iple bucke da ase s in he ollowing
manne : o each uple h, i a bucke Bwi h signa u e
SD(Q(h,T∗))1exis s, add h o B, o he wise c ea e a
bucke wi h ha signa u e and add h o i .
•Balancing: o each bucke c ea ed in he classi ica ion
s ep, i i is unbalanced, add uples om Tnewun il i is
balanced, i none a ailable add coun e ei s.
•Assignmen : di ide he emaining uples o Tnewin bal-
anced bucke s o a leas signa u e size m.
•Pa i ioning: o each bucke Bdi ide i in g oups o
uples o size |SD(B)|wi h one uple pe sensi i e alue.
Gene alize each g oup in o a class and publish he da ase .
1Signa u e o he class o he las publica ion o h.
Fig. 1 Flowcha o he main s eps o he algo i hm. Classi ica ion,
balancing, assignmen and pa i ion co espond wi h he s eps o he
app oaches p esen ed in Xiao and Tao (2007)andAnjume al.(2017).
The app oach wi h wo se esul s is disca ded. (1) P io o he op imiza-
ion s ep, an ins ance o wo-swapping can be execu ed o imp o e he
ini ial solu ion
This algo i hm s uc u e allows o a epublica ion which
does no inc ease d as ically in ime complexi y as new e -
sions a e published.
The bulk o he u ili y los is due o s eps o assignmen
and pa i ioning. Only one me hod exis s in he li e a u e o
he assignmen phase, p esen ed in Xiao and Tao (2007). Pa -
i ioning has wo e sions, being Anjum and Raschia (2013);
Anjum e al. (2017) he only imp o emen s o he o iginal
e sion in Xiao and Tao (2007). Ou wo k is an al e na i e
me hod ha join ly pe o ms he assignmen and pa i ioning
s eps in a single s age. Pe o ming assignmen and pa i ion-
ing oge he d as ically imp o es he quali y (i.e., educ ion
o IL) o he solu ions compu ed. B ie ly, he assignmen and
pa i ion s eps can be sol ed by pa i ioning he se o poin s
o he da ase such ha each g oup has ca dinali y a leas
m, and ha all poin s o a g oup ha e di e en alues o
he sensi i e a ibu e ( he “colo ” o he poin ). Nex sec-
ions in oduce an in ege op imiza ion-based me hod o he
solu ion o his p oblem, whose main s eps a e p esen ed in
Fig. 1.
3 In ege op imiza ion models
He e we adap o m-in a iance a o mula ion inspi ed by he
clique pa i ioning p oblem wi h minimum clique size o Ji
and Mi chell (2007). De ining as C∗={C⊆{1,...,p}:
m≤|C|≤2m−1,c(i)= c(j) o i,j∈C} he se o
easible clus e s, whe e c(i)is he colo o elemen i, he
123
A New ma hema ical op imiza ion-based me hod ...
m-in a iance p oblem can be o mula ed as:
min
C∈C∗
wCxC
s. o
C∈C∗:i∈C
xC=1i∈{1,...,p}
xC∈{0,1}C∈C∗,
(1)
whe e wCwill be de ined in below equa ion (4), xC=1
means ha easible clus e Cappea s in he m-in a iance
p o ided solu ion, and he cons ain s gua an ee ha all he
poin s a e co e ed by some easible clus e , and only once,
ha is, a poin can no belong o wo di e en clus e s, hus
ha ing a pa i ion o {1,...,p}.
A widely used measu e o e alua ing he quali y o a
clus e ing is i s sp ead o sum o squa ed e o s (SSE)
(Domingo-Fe e and Ma eo-Sanz 2002):
SSE =
C∈C∗:xC=1
SSEC,(2)
whe e SSECis he sp ead o clus e Cwhich is de ined as
SSEC=
i∈C
(ai−aC)(ai−aC), (3)
aibeing a poin o he clus e and ¯aC=1
|C|i∈Caii s
cen oid.
The cos wCo clus e Cin he objec i e unc ion o (1)
is
wC=1
2|C|
i∈C
j∈C
Dij,(4)
whe e Dij =(ai−aj)(ai−aj). Using, o e e y clus e
C, he ollowing well-known equi alence (see Cas o e al.
2022a):
i∈C
(ai−¯aC)(ai−¯aC)
=1
2|C|
i∈C
j∈C
(ai−aj)(ai−aj), (5)
we ha e ha wC=SSEC, and hen he objec i e unc ion
o (1) equals SSE.
In o ma ion loss IL is an equi alen measu e o SSE,
de ined as
IL =SSE
SST ×100,(6)
whe e SST is he o al sum o squa ed e o s o all he poin s:
SST =
p
i=1
(ai−¯a)(ai−¯a)whe e ¯a=p
i=1ai
p.(7)
IL always akes alues wi hin he ange [0,100]; he smalle
he IL, he be e he clus e ing. The e o e, he op imal solu-
ion o (1) p o ides he easible clus e ing ha minimizes he
in o ma ion loss.
I is wo h no ing ha in he de ini ion o C∗only clus e s
o ca dinali y |C|≤2m−1 a e conside ed, since, as p o ed
in Domingo-Fe e and Ma eo-Sanz (2002), a clus e o ca -
dinali y |C|=2mcan be di ided in wo smalle clus e s o
mpoin s, hus imp o ing he IL.
The numbe o easible clus e s in C∗— ha is, he numbe
o a iables in he op imiza ion p oblem (1)—can be huge,
so i s di ec solu ion by op imiza ion me hods is unp ac ical
a leas o la ge sizes. The e o e we eso o heu is ics based
on wo ing edien s:
•decomposi ion,
•column gene a ion,
ha will be de ailed in nex wo sec ions
4 Decomposi ion
The decomposi ion heu is ic is an ex ension o he heu is-
ic ini ially de eloped o he mic oagg ega ion p oblem in
Cas o e al. (2022b).
The decomposi ion heu is ic is based on pa i ioning he
ini ial se o poin s P={1,...,p}in ssubse s Pk,k=
1,...,s, such ha ∪s
k=1Pk=P, and Pk∩Pl=∅ o all
k,l:k= l. This ini ial pa i ioning is ob ained by i s ind-
ing a easible clus e ing using he wo exis ing heu is ics o
m-in a iance (namely, he classical app oach o Xiao and
Tao (2007) and he τ-sa e y p oposal o Anjum and Raschia
(2013); Anjum e al. (2017)). Following he o iginal no a-
ion, we execu e he classi ica ion, balancing, assignmen and
pa i ioning o he τ-sa e y p oposal o ob ain an ini ial clus-
e ing o op imize. Then, poin s in di e en clus e s o his
ini ial clus e ing a e sequen ially added, ob aining he ini ial
pa i ioning Pk,k=1,...,s.
Fo each subse Pk,k=1,...,s, we hen conside he
(smalle ) op imiza ion p oblem (1) eplacing he easible se
C∗by C∗
k={C⊆Pk:m≤|C|≤2m−1,c(i)=
c(j) o i,j∈C}. These sop imiza ion p oblems, hough
smalle han he o iginal p oblem (1), may s ill ha e a e y
la ge numbe o op imiza ion a iables and a e sol ed using
he column gene a ion echnique desc ibed below in Sec .5.
Each o he sop imiza ion p oblems will p o ide a se o
123
A. T. Nicolau e al.
easible clus e s Ok⊆C∗
k o he subse o poin s Pk, and
he e o e i s union O=∪
s
k=1Okwill be a easible clus e ing
o P(subop imal, bu in gene al o good quali y— ha is,
small in o ma ion loss).
Addi ionally, he easible clus e ing Ois u he imp o ed
by applying a local sea ch heu is ic based on a wo-swapping
p ocedu e. In sho , his p ocedu e analyzes all he easible
swappings be ween wo poin s iand jloca ed in di e en
clus e s Ciand Cj, such ha c(i)= c(h) o each h∈Cj
and c(j)= c(h) o each h∈Ci, pe o ming he swapping
o he pai (i,j) ha minimizes he objec i e unc ion o (1).
This is epea ed un il he e is no imp o emen in he objec i e
unc ion. The cos pe i e a ion o his p ocedu e is O(p2/2).
The wo-swapping heu is ics can also be op ionally used
o ob ain he ini ial pa i ioning Pk,k=1,...,s, o poin s.
Indeed, wo-swapping can be applied o he ini ial clus e ing
ound by he m-in a iance heu is ics, ob aining a new clus-
e ing wi h a smalle objec i e unc ion. This new clus e ing
is hen used o ob ain he ini ial pa i ioning.
The main s eps o he decomposi ion heu is ic can be sum-
ma ized as ollows:
1. Apply m-in a iance heu is ics o ge an ini ial easible
clus e ing.
2. Op ionally, apply he wo-swapping heu is ic o his ini ial
easible clus e ing.
3. Compu e he ini ial pa i ioning Pk,k=1,...,s,o
poin s om he ini ial easible clus e ing.
4. Apply he column gene a ion op imiza ion algo i hm o
each se o poin s Pk, ob aining a easible clus e ing Ok
o all k=1,...,s. No e ha his s ep can be pe o med
in pa allel o all he se s k=1,...,s.
5. Compu e O=∪
s
k=1Ok, which is a easible clus e ing o
P.
6. Finally, apply he wo-swapping heu is ic o he easible
clus e ing O.
5 Column gene a ion app oach
In his sec ion we desc ibe he no el column gene a ion
app oach de eloped o he m-in a iance p oblem, as an
ex ension o he p ocedu e ini ially de eloped o mic oag-
g ega ion in Cas o e al. (2022a). The no el y o he app oach
is he de ini ion in he column gene a ion p ocedu e o a
mas e and subp oblem ha gua an ee ha he solu ions com-
pu ed a e m-in a ian .
Column gene a ion is a well-known app oach in ma he-
ma ical op imiza ion o he solu ion o linea p og amming
p oblems wi h a la ge numbe o a iables (Des osie s and
Lübbecke 2005). Gi en a gene al linea p og amming p ob-
lem
min
j∈V
cjxj
s. o
j∈V
Ejxj=b
xj≥0j∈V,
(8)
whe e Ej∈R is he ec o wi h he con ibu ion o a i-
able xj o he cons ain s o he p oblem (we assume ha
|V|> ), he simplex me hod op imizes (8) by inding a
se o a iables B⊂V(named se o basic a iables) such
ha : (i) |B|= ; (ii) he ec o s Ej,j∈B, a e linea ly
independen ; (iii) and o any a iable j∈N=V B
(named se o nonbasic a iables), we ha e ha he alues
μj=cj−λEj(named educed cos s) a e non-nega i e,
whe e λ=(E
B)−1cB∈R is he se o dual a iables o
Lag ange’s mul iplie s o he cons ain s o (8), and EBand
cBa e espec i ely a ma ix and ec o o med by he ec o s
Ejand coe icien s cjsuch ha j∈B.
When he numbe o a iables |V|is e y la ge, we can
ini ially conside a subse ¯
V⊆Vo a iables. P oblem (8)
can hus be sol ed wi h he simplex me hod eplacing Vby
¯
V, ob aining he se s o basic and nonbasic a iables ¯
Band
¯
N. The simplex me hod gua an ees ha μj≥0 o j∈¯
N.
I in addi ion μj≥0 o j∈V ¯
Vwe can ce i ica e ha he
cu en solu ion is also op imal o (8). O he wise, he e is
some j∈V ¯
Vwi h μj<0. Column gene a ion hen sol es
he subp oblem
min cj−λEj,j∈V ¯
V,(9)
whe e λis he ec o o dual a iables p o ided by he p e-
ious solu ion o (8)using ¯
V, and cj ep esen s he cos o
he a iable associa ed o column Ej. The solu ion o (9)
p o ides bo h a new column Ejand i s associa ed educed
cos μj. I he educed cos is non-nega i e, we conclude
ha he cu en solu ion (x¯
B,x¯
N)is op imal. O he wise, i
he educed cos is nega i e, we add he new column Ej o
he se o al eady gene a ed columns ( ha is, ¯
V←¯
V∪{j}),
and eop imize again (8). This p ocedu e is epea ed un il (9)
p o ides a non-nega i e educed cos .
Applying he p e ious p ocedu e o he m-in a iance
p oblem, he column gene a ion app oach enables us o sol e
he con inuous elaxa ion o (1) conside ing only a subse ¯
C
o C∗:
min
C∈¯
C
wCxC
s. o
C∈¯
C:i∈C
xC=1i∈P
xC∈[0,1]C∈¯
C,
(10)
123
A New ma hema ical op imiza ion-based me hod ...
whe e he o iginal bina y cons ain s xC∈{0,1}ha e been
elaxed and eplaced by xC∈[0,1]. A each i e a ion we es
i he solu ion o (10) is op imal o he con inuous elaxa ion
o (1) by sol ing he ollowing op imiza ion p oblem o each
size η∈{m,...,2m−1}:
min 1
2η(i,j)∈ADijzij −i∈Pλi
η−1yi
s. o 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)
whe e A={(i,j)|i,j∈P,i<j,c(i)= c(j)},δ+
i=
{(i,j)∈A},δ−
i={(j,i)∈A}, and λiis he alue o he
dual a iable wi h espec o cons ain o poin iin (10). The
objec i e unc ion (11) is he educed cos o a new easible
clus e ep esen ed by bina y a iables zij (which a e 1 i
poin s i,ja e in he clus e , and 0 o he wise).
P oblem (11) is sol ed by adap ing he me hod desc ibed
in Cas o e al. (2022a) o hem-in a iance case by simply
ixing o ze o zij when (i,j)/∈A.
Wi hin he decomposi ion app oach o Sec . 4, p oblem
(10) is sol ed o each subse o poin s Pk,k=1,...,s, and
a subse Ako Ais de ined acco dingly.
The p e ious column gene a ion algo i hm p o ides an
op imal solu ion o he con inuous elaxa ion o (1). I all
he a iables xCa e ei he 0 o 1, his solu ion is op imal
o he in ege op imiza ion model (1). I some a iables xC
a e ac ional, some ounding heu is ic is needed o ob ain a
(subop imal bu in gene al good quali y) bina y solu ion. In
mos cases, he bes bina y solu ion was ob ained by sol ing
(10) wi h he las se o clus e s ¯
Ccompu ed, and eplacing
bounds xC∈[0,1]by bina y cons ain s xC∈{0,1}.
Since column gene a ion is in essence a pa icula s a -
egy o implemen he simplex me hod in p oblems wi h a
huge numbe o a iables, i s compu a ional complexi y is
he same as he one o he simplex me hod, which is expo-
nen ial in he wo s case. Howe e , he empi ical complexi y
o he simplex me hod is p opo ional o he numbe o con-
s ain s and a iables. Un o una ely, o a la ge da abase, he
linea elaxa ion o he m-in a iance p oblem (1) p o ides an
exponen ial numbe o a iables, which means ha e en he
empi ical complexi y o his p oblem can be exponen ial.
Al hough he column gene a ion is designed o gene a e only
he mos p omising columns, he numbe o columns ha will
be gene a ed canno be known o p edic ed a p io i, and i
is p oblem dependen . In p ac ice a maximum numbe o
columns gene a ed, o ime limi , is equi ed o p ema u ely
s op he p ocedu e, hope ully wi h a good solu ion. This was
done in all he compu a ional es s pe o med, as desc ibed in
he nex sec ion. Despi e his complexi y esul s, column gen-
e a ion was able o ob ain solu ions o much highe quali y
han hose compu ed by cu en heu is ics o m-in a iance.
6 Compu a ional es s
The column gene a ion algo i hm o m-in a iance in o-
duced in his pape has been implemen ed in C++. The
solu ion o he linea op imiza ion p oblems (10) and in e-
ge op imiza ion subp oblems (11) o he column gene a ion
algo i hm we e compu ed wi h he CPLEX sol e . Al e na-
i ely, subp oblems (11) can also be sol ed, o small alues
o m, using he implici enume a ion scheme o Aloise e al.
(2014). A pa allel e sion o S ep 4 o he decomposi ion
app oach o Sec .4was implemen ed using OpenMP.
The implemen a ion was es ed wi h he “Adul ” (Dua
and G a 2017) and he “IPUMS USA” (Ruggles e al.
2023) da ase s. Bo h da ase s ha e been used in se e al
p e ious wo ks on syn ac ic p i acy o dynamic da a pub-
lishing. F om he “Adul ” da ase he a ibu es age, sex
and educa ion-num ha e been used as quasi-iden i ie s and
occupa ion as sensi i e a ibu e ( ha is, “occupa ion” is he
“colo ” a ibu e acco ding o he no a ion o Sec . 3). Fo he
“IPUMS” da ase we conside ed a da a ex ac wi h columns
sex, age, educ and occupa ion, using occupa ion as sensi i e
a ibu e and he es as quasi-iden i ie s. We used samples o
1500 and 1000 andomly selec ed use s o Adul and IPUMS
espec i ely.
These wo da ase s we e conside ed o hei p e alen
appea ance in he ela ed li e a u e and o e lec wo scena -
ios depending on he numbe o unique sensi i e alues. The
Adul da ase has 13 unique sensi i e alues while IPUMS
has 281 unique sensi i e alues. We es ed he pe o mance
o ou app oach in compa ison wi h he implemen a ions o
assignmen and pa i ioning o Xiao and Tao (2007) (deno ed
as “Classic”), and Anjum e al. (2017) (deno ed as “Tau”).
These implemen a ions a e he wo main app oaches in he
exis ing li e a u e.
6.1 Resul s
Tables 4and 5show he esul s ob ained o , espec i ely,
he “Adul ” and “IPUMS” da ase s. Each da ase was sol ed
o he clus e sizes m∈{3,5,7}and numbe o subse s
s∈{40,20,10,5,2}, which amoun s o 15 uns o he algo-
i hm wi h each da ase . The uns we e ca ied ou on a
DELL Powe Edge R7525 wi h wo 2.4 GHz AMD EPYC
7532 CPUs (128 o al co es), unde a GNU/Linux ope a ing
sys em (openSuse 15.3).
The columns o he ables p o ide esul s o he di e en
s eps o he decomposi ion algo i hm: s ep 1: m-in a iance
heu is ics (used o pa i ion he se o poin s in s ep 3); s ep
4: op imiza ion wi h column gene a ion o each subse o
123
A. T. Nicolau e al.
Table 4 Compu a ional esul s o he adul da ase wi h wo-swapping applied only a e column gene a ion
Clus e size mm-in a iance heu is ics Column gene a ion om heu is ic solu ion Two-swapping
Algo i hm 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 Compu a ional esul s o he IPUMS da ase wi h wo-swapping applied only a e column gene a ion
Clus e size mm-in a iance heu is ics Column gene a ion om heu is ic solu ion Two-swapping
Algo i hm 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
poin s ob ained om he solu ion o he p e ious s ep, he
m-in a iance heu is ics; s ep 6: wo-swapping heu is ic. The
execu ion o he wo s a e-o - he-a m-in a iance heu is ics
(“Classic” and “Tau”) is independen o s, hen he al-
ues o hese columns a e common o all he ows wi h he
same m. Fo each s ep we p o ide he compu a ional ime,
and he in o ma ion loss (IL) ob ained (which mono onically
dec eases wi h he s eps). Fo s ep 1, he esul s wi h he
“Classic” and “Tau” heu is ic a e gi en; “Tau” always ou -
pe o med “Classic” in e ms o IL, hen i was chosen as he
ini ial clus e ing o pa i ion he se o poin s in ssubse s. Exe-
cu ions o he op imiza ion s age we e mul i h eaded using
OpenMP, he numbe o h eads being equal o he num-
be o subse s s. Fo his eason, imes in he able e e o
“wall-clock” ime, ins ead o CPU ime. We se bo h a ime
limi (o wo hou s) and a limi on he numbe o columns
gene a ed, o each column gene a ion p ocess. Usually, he
smalle he s, he la ge (and likely mo e di icul ) a e he col-
umn gene a ion p oblems, and a longe solu ion ime can be
expec ed. Howe e , in some cases, hese la ge column gen-
123
A New ma hema ical op imiza ion-based me hod ...
Table 6 Compu a ional esul s o he adul da ase wi h wo-swapping applied be o e and a e he column gene a ion heu is ic
Clus e size mm-in a iance heu is ics Two-swapping 1 Column gene a ion om wo-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 Compu a ional esul s o he IPUMS da ase wi h wo-swapping applied be o e and a e he column gene a ion heu is ic
Clus e size mm-in a iance heu is ics Two-swapping 1 Column gene a ion om wo-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 Summa y: bes IL
esul s wi h classic and au
heu is ics, and wi h he new
op imiza ion app oach
Ins ance mIL
Classic Tau Op imiza ion
Adul 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
