Fix-and- elax app oaches o con olled abula adjus men
Daniel Baena Jo di Cas o José A. González
Dep . o S a . and Ope a ions Resea ch
Uni e si a Poli ècnica de Ca alunya
[email p o ec ed] [email p o ec ed] [email p o ec ed]
Resea ch Repo UPC-DEIO DR 2013-02
July, 2013; upda ed July 2014, Oc obe 2014
Repo a ailable om h p://www-eio.upc.es/˜jcas o
Fix-and- elax app oaches o con olled abula adjus men
Daniel Baenaa, Jo di Cas o∗,a, José A. Gonzáleza
aDep . o S a is ics and Ope a ions Resea ch, Uni e si a Poli ècnica de Ca alunya, Ba celona
Abs ac
Con olled abula adjus men (CTA) is a ela i ely new p o ec ion echnique o abula da a
p o ec ion. CTA o mula es a mixed in ege linea p og amming p oblem, which is challenging
o ables o mode a e size. E en inding a easible ini ial solu ion may be a challenging ask o
la ge ins ances. On he o he hand, end use s o abula da a p o ec ion echniques gi e p io i y
o as execu ions and a e hus sa is ied in p ac ice wi h subop imal solu ions. This wo k has wo
goals. Fi s , he ix-and- elax (FR) s a egy is applied o ob ain good easible ini ial solu ions
o la ge CTA ins ances. FR is based on pa i ioning he se o bina y a iables in o clus e s o
selec i ely explo e a smalle b anch-and-cu ee. Secondly, he FR solu ion is used as a wa m
s a o a block coo dina e descen (BCD) heu is ic (app oach named FR+BCD); BCD was
con i med o be a good op ion o la ge CTA ins ances in an ea lie pape by he second and hi d
co-au ho s (Compu e s & Ope a ions Resea ch 2011). We epo ex ensi e compu a ional esul s
on a se o eal-wo ld and syn he ic CTA ins ances. FR is shown o be compe i i e compa ed
o CPLEX b anch-and-cu in e ms o quickly inding ei he a easible solu ion o a good uppe
bound. FR+BCD imp o ed he quali y o FR solu ions o app oxima ely 25% and 50% o
he syn he ic and eal-wo ld ins ances, espec i ely. FR o FR+BCD p o ided simila o be e
solu ions in less CPU ime han CPLEX o 73% o he di icul eal-wo ld ins ances.
Key wo ds: Fix-and-Relax, Block Coo dina e Descen , Mixed-in ege Linea P og amming,
Con olled Tabula Adjus men , P imal Heu is ics, Feasibili y Pump, S a is ical Disclosu e
Con ol
1. In oduc ion
Mic oda a and abula da a p o ec ion a e he wo main disciplines o s a is ical disclosu e
con ol. The pu pose o his ield is o a oid ha con iden ial in o ma ion can be de i ed om
da a eleased. This is one o he main conce ns o Na ional S a is ical Agencies (NSAs), which
ha e o dissemina e a la ge amoun o in o ma ion minimizing a he same ime he disclosu e
isk o indi idual esponden s. Tabula da a is ob ained by c ossing wo o mo e ca ego ical
a iables in a mic oda a ile. Fo each cell, he able may epo ei he he numbe o indi iduals
( equency ables) o in o ma ion abou ano he a iable (magni ude ables). Mo e de ails can be
ound in he ecen su ey [5] and he monog aphs [26, 27].
∗Co esponding add ess: Dep . o S a is ics and Ope a ions Resea ch, Uni e si a Poli ècnica de Ca alunya, Campus
No d, O ice C5203, Jo di Gi ona 1–3, 08034 Ba celona, Ca alonia, Spain
Email add esses: [email p o ec ed] (Daniel Baena), [email p o ec ed] (Jo di Cas o),
[email p o ec ed] (José A. González)
1 2
.
.
.... ... ... ...
51–55 ... 38000d40000d...
56–60 ... 39000d42000d...
.
.
.... ... ... ...
(a)
1 2
.
.
.... ... ... ...
51–55 ... 20 1 o 2 ...
56–60 ... 30 35 ...
.
.
.... ... ... ...
(b)
Figu e 1: Example o disclosu e in abula da a. (a) A e age sala y pe age and own. (b) Numbe o indi iduals pe age
and own. I he e is only one indi idual in own 2and age in e al 51–55, hen any ex e nal a acke knows he sala y o
his single pe son is 40000d. Fo wo indi iduals, any o hem can deduce he sala y o he o he , becoming an in e nal
a acke .
Al hough cell ables epo agg ega ed in o ma ion o se e al esponden s—so hey could
be conside ed anonymized— he e is a isk o disclosing indi idual da a. Figu e 1 illus a es his
si ua ion wi h a simple case. The le able (a) epo s he a e age sala y o indi iduals by age
( ow a iable) and own (column a iable), while able (b) p o ides he numbe o indi iduals. I
he e we e only one indi idual o age be ween 51–55 in own 2, hen any ex e nal a acke would
know he con iden ial sala y o his pe son. Fo wo indi iduals, any o hem could disclose he
o he ’s sala y, becoming an in e nal a acke . Cells ha equi e p o ec ion (such as ha o he
example) a e named sensi i e, unsa e, o con iden ial cells. Sensi i e cells a e a p io i de ec ed
by some sensi i i y ules. The abo e example showed he simples minimum- equency ule,
which conside s sensi i e hose cells wi h e y ew esponden s. The mos widely used ule,
named p-% ule, conside s a cell unsa e i some esponden may ob ain an es ima e o ano he
esponden con ibu ion wi hin a p-% p ecision. A de ailed desc ip ion o hese ules can be
ound in [27].
A abula da a p o ec ion me hod can be seen as a map Fsuch ha F(T)=T′, i.e., able T
is ans o med o ano he able T′. Two a e he main equi emen s o F: (1) he ou pu able
T′should be “sa e”, and (2) he quali y o T′should be high (o equi alen ly, he in o ma ion
loss should be small), i.e., T′should be a good eplacemen o T. The disclosu e isk can
be analyzed h ough he in e se map T=F−1(T′): i no a ailable o di icul o compu e by
any da a a acke , hen we may gua an ee ha Fis sa e. Con olled Tabula Adjus men (CTA)
[3, 11] is a ecen echnique o he p o ec ion o any abula da a. I was empi ically obse ed in
[6] ha es ima es ˆ
T=ˆ
F−1(T′), ˆ
F−1being an es ima e o F−1 o CTA, we e no close o T o
some eal ables. CTA can hus be conside ed a sa e me hod in gene al. Mo eo e , he quali y
o CTA solu ions has shown o be high [10], highe han ha p o ided by al e na i e me hods in
some eal ins ances [9].
The goal o CTA—which will be o mula ed in Sec ion 2—is, gi en a able wi h any s uc-
u e, o ind he closes sa e able o he o iginal one. This is achie ed by adding he minimum
amoun o de ia ions (o pe u ba ions) o he o iginal cell ables ha makes he eleased able
sa e. Sa e y is gua an eed by imposing ha sensi i e cells in he new p o ec ed able a e a
enough om he o iginal alue. This means he cell alue is ei he abo e o below some ce ain
alues, hus a disjunc i e cons ain in ol ing a bina y a iable is needed o each sensi i e cell.
The minimum amoun o abo e o below pe u ba ions equi ed o each sensi i e cell a e named,
espec i ely, uppe p o ec ion and lowe p o ec ion le els. Changes in sensi i e cells o ce o he
changes in he emaining cells o gua an ee ha he alue o o al o ma ginal cells is p ese ed.
2
Al hough i is a ecen app oach, CTA is gaining ecogni ion among NSAs; o ins ance, CTA
is conside ed a ela i ely new eme ging me hod in he ecen monog aphs [26, 27]. We ecen ly
implemen ed a package o CTA in collabo a ion wi h he NSAs o Ge many and he Ne he -
lands, wi hin a p ojec unded by Eu os a , he S a is ical O ice o he Eu opean Communi ies.
This package has been la gely imp o ed wi hin he FP7-INFRA-2010-262608 p ojec unded by
he Eu opean Union, wi h he pa icipa ion, among o he s, o he na ional s a is ical ins i u es o
Ge many, Ne he lands, Finland, Sweden and Slo enia. This CTA so wa e is included in he au-
A gus package [25] (h p://neon. b.cbs.nl/casc/ au.h m), used o many Eu opean na-
ional s a is ical ins i u es o he p o ec ion o abula da a. Among he ecen li e a u e on CTA
a ian s we ind [8, 24]. In ecen specialized wo kshops on s a is ical disclosu e con ol, some
NSAs s a ed ha pe u ba i e me hods, like CTA, a e gaining accep ance [31], and pe u ba i e
app oaches a e being used o he p o ec ion o na ional census ables (e.g., [21] o Ge many).
CTA has also been used wi hin o he wide p o ec ion schemes, such as he p e- abula p o ec-
ion me hod o [20]. In addi ion, some Na ional S a is ical Agencies a e ques ioning cu en
non-pe u ba i e p o ec ion me hods because “ he ask o balancing con iden iali y and usabili y
[...] is nea ly impossible” [30]. The e o e he e is a need o new me hods, and his jus i ies he
esea ch on CTA and o he app oaches. Indeed, he e is no ac ually any p o ec ion me hod ha
i s he needs o all NSAs in he wo ld.
F om a compu a ional poin o iew, he size o he CTA op imiza ion p oblem is by a
smalle han o o he well-known p o ec ion me hods, such as he cell supp ession p oblem
[4, 19]. Despi e hese nice ea u es, CTA o mula es a challenging mixed in ege linea p oblem
(MILP) o cu en s a e-o - he-a sol e s (such as CPLEX o XP ess). Op imal (o subop imal,
e.g., wi h a 5% gap) solu ions may equi e many hou s o execu ion o medium ins ances; e y
la ge o massi e ables can no be ackled wi h cu en echnology. Se e al app oaches ha e been
ied o speed up he solu ion ime. A s aigh o wa d Bende s e o mula ion o he p oblem was
a emp ed in [7], bu p omising esul s we e only ob ained o wo-dimensional ables (i.e., ables
ob ained by c ossing wo ca ego ical a iables, whose cons ain s a e ep esen ed by a node-a c
ne wo k incidence ma ix [5]). Heu is ic and me aheu is ic me hods we e a emp ed in [22], bu
hey only sol ed small wo-dimensional and h ee-dimensional ables o up o 625 and 8000
cells, espec i ely, while we conside in his wo k much mo e complex syn he ic and eal ables
om he li e a u e, o up o 200000 and 36000 cells, espec i ely. Fo ins ance, we gene a ed a
se o 20 wo-dimensional and 20 h ee-dimensional ables wi h he same cha ac e is ics (sizes
and numbe o sensi i e cells) han hose in [22]. We ema k ha : (1) he ables used in [22]
we e also andomly gene a ed; (2) he ma ix cons ain s only depends on he able s uc u e
( wo- o h ee-dimensional able) so hey we e he same in ou expe imen s and hose in [22];
(3) al hough he ins ances a e no exac ly he same, wha makes di icul (in gene al) a p oblem
is he s uc u e o he ma ix cons ain s and he numbe o sensi i e cells (which is associa ed
o he numbe o bina y a iables o he op imiza ion p oblem); hose cha ac e is ics a e he
same in ou expe imen s and hose o [22]. CPLEX 12.5 ound a 0% gap solu ion o all hese
wo-dimensional ables wi h an a e age CPU ime o 0.02 seconds ( he maximum ime equi ed
by an ins ance was 0.03 seconds). Fo he h ee-dimensional ables, he a e age CPU ime was
0.2 seconds ( he maximum ime o an ins ance was 0.49 seconds), again o 0% gap solu ions.
No CPU ime compa ison wi h CPLEX was epo ed in [22]; i was jus s a ed ha CPLEX 8.1
could no sol e he ins ances. The e o e, up o now, he e is no conclusi e e idence ha hose
me aheu is ics a e help ul o he CTA p oblem.
We also ied in he pas o he gene al me aheu is ics as gene ic algo i hms wi hou success:
combina ions o modi ica ions o solu ions a e no expec ed o sa is y he la ge numbe o linea
3

cons ain s wi h no pa icula s uc u e o CTA. Indeed, hese cons ain s a e usually complex,
and any p ac ical app oach mus ely on he e icien solu ion o (usually di icul ) linea ly con-
s ained p oblems (ei he LPs o MILPs). The app oaches in his pape ely on decomposing
he p oblem in o smalle , hus ac able, MILP ins ances. I is wo h o no e ha e en he LPs
ob ained om la ge CTA ins ances by ixing he bina y a iables a e e y di icul o oday s a e-
o - he-a sol e s. Indeed, some o hese ins ances ha e been included in s anda d LP eposi o ies
[29].
The pu pose o his wo k is wo old. I s i s goal is o apply a ix-and- elax (FR) heu is ic
[13] o he MILP CTA p oblem. B ie ly, FR pa i ions he se o bina y a iables in o kclus e s,
and i e a i ely op imizes o each clus e i=1,...,k, ixing he bina y a iables o clus e s j<i
a he op imal alue ound in p e ious i e a ions, and elaxing he in eg ali y o bina y a iables
o clus e s j>i. The e ec o his pa i ioning o he se o bina y a iables is ha he nodes
o he b anch-and-cu ee a e selec i ely explo ed. Equipping his p ocedu e wi h a backwa d
epa i ion s a egy (de ails will be gi en in Sec ion 3.1), i he MILP is easible hen FR will al-
ways p o ide a easible, hope ully good and e icien , subop imal solu ion. The app oach canno
gua an ee he op imal solu ion, bu in p ac ice end use s o s a is ical da a p o ec ion echniques
p e e quick subop imal solu ions han op imal cos ly ones, i.e., equi ing oo many hou s, days
o weeks o CPU ime.
The second objec i e o he wo k is o apply a hyb id app oach combining FR and he block
coo dina e descen (BCD) heu is ic, which was success ully applied o some classes o CTA
p oblems in [23]. This hyb id me hod will be named FR+BCD. Indeed, FR is e icien o
compu ing ini ial, hope ully good, easible poin s, while BCD equi es a easible s a ing poin .
The e o e, bo h heu is ics a e complemen a y. As i will be shown in Sec ion 4, BCD, wa m
s a ed wi h he FR solu ions, was able o educe he gap o he FR solu ion in app oxima ely
hal o he eal-wo ld CTA ins ances. In 25 o he 34 eal-wo ld ins ances FR o FR+BCD p o-
ided simila o be e objec i e unc ions in less CPU ime han he s a e-o - he-a MILP sol e
CPLEX.
FR has been success ully applied in he pas mainly o scheduling p oblems [13, 15, 16].
In hose applica ions, a iables and cons ain s can na u ally be pa i ioned acco ding o some
sequen ial s ages, wo consecu i e ones being only linked by a ew o he a iables and con-
s ain s o each pa i ion. Such a s uc u e can also be ound in some classes o ables, named
wo dimensional ables wi h one hie a chical a iable, o , sho ly, 1H2D ables. These ables a e
ob ained by c ossing a pa icula ca ego ical a iable wi h a se o , say, hca ego ical a iables
ha ha e a hie a chical ela ion; his esul s in a se o h wo-dimensional ables wi h some com-
mon cells. Fo ins ance, Figu e 2 ( om [5]) illus a es a pa icula 1H2D able. The le sub able
shows numbe o esponden s o “ egion”דp o ession”; he middle sub able is a “zoom in” o
egion R2, p o iding he numbe o esponden s in municipali ies o his egion; inally he igh
sub able de ails he ZIP codes o municipali y R21. This ype o ables, which a e ele an o
NSAs, a e a p io i sui able o FR. Mos o he ins ances es ed in he compu a ional esul s o
his wo k a e 1H2D, and, as i will be shown, FR p o ides good solu ions in a ac ion o he ime
equi ed by s a e-o - he-a b anch-and-cu sol e s ( o ob ain equi alen solu ions, i.e., wi h he
same objec i e unc ion alue). I will be seen ha FR+BCD imp o ed he FR solu ions in only
25% o hese 1H2D ables. Fo eal-wo ld ables, his pe cen age inc eased up o 50%, making
FR+BCD a compe i i e app oach.
The pape is o ganized as ollows. Sec ion 2 ou lines he MILP CTA p oblem. Sec ion
3.1 desc ibes he FR heu is ic o CTA; i also ou lines he BCD app oach. Finally, Sec ion
4 p esen s ex ensi e compu a ional esul s, showing he e ec i eness o FR and FR+BCD o
4
C1C2C3
R15 6 11
R210 15 25
R315 21 36
T1
C1C2C3
R21 8 10 18
R22 2 5 7
R210 15 25
T2
C1C2C3
R211 6 6 12
R212 2 4 6
R21 8 10 18
T3
Figu e 2: 1H2D able made o h ee sub ables: “ egion”דp o ession”, “municipali y”דp o ession” and
“zip code”דp o ession”.
syn he ic 1H2D and eal-wo ld ables.
2. The MILP o mula ion o he CTA p oblem
Any CTA p oblem ins ance can be ep esen ed by he ollowing pa ame e s :
•A se o cells ai,i∈ N ={1,...,n}, ha sa is ies M={1,...,m}linea ela ions Aa =b,
a∈Rnbeing he ec o o ai’s, and A∈Rm×n. These linea ela ions impose ha he se o
inne cells has o be equal o he o al o ma ginal cell, i.e., i Ijis he se o inne cells o
ela ion j∈ M, and jis he index o he o al cell o ela ion j, he cons ain associa ed
o his ela ion is Pi∈Ijai−a j=0.
•Nonnega i e cell weigh s wi,i∈ N, used in he de ini ion o he objec i e unc ion. These
weigh s penalize pe u ba ions om he o iginal cell alues in he eleased able. Cells
weigh s a e usually a unc ion o he cell alue, e.g., wi=1/ai— o his pa icula weigh s,
he objec i e unc ion ep esen s ela i e cell de ia ions.
•A lowe and uppe bound o each cell i∈ N, espec i ely laiand uai, which can be
conside ed publicly known.
•A se S={i1,i2, . . . , is} ⊆ N o indices o sensi i e o con iden ial cells.
•A lowe and uppe p o ec ion le el o each sensi i e cell, espec i ely, lpliand upli,i∈ S.
Values o sensi i e cells mus be ou o he in e al (ai−lpli,ai+upli) in he eleased able.
The pu pose o CTA is o ind he closes sa e alues xi o ai. Conside ing any dis ance ℓ,
CTA can be o mula ed as
min
x||x−a||ℓ
s. o Ax =b
lai≤xi≤uaii∈ N
xi≤ai−lplio xi≥ai+uplii∈ S.
(1)
The disjunc i e cons ain s o (1) gua an ee he published alue is sa ely ou o he in e al
(ai−lpli,ai+upli). P oblem (1) can also be o mula ed in e ms o de ia ions om he cu en
5
cell alues. De ining zi=xi−ai,i∈ N—and simila ly lzi=lai−aiand uzi=uai−ai—, (1) can
be ecas as
min
z||z||ℓ
s. o Az =0
lzi≤zi≤uzii∈ N
zi≤ −lplio zi≥uplii∈ S,
(2)
z∈Rnbeing he ec o o cell de ia ions. Using he ℓ1o Manha an dis ance and he cell
weigh s wi, he objec i e unc ion is Pi∈N wi|zi|. Since wia e nonnega i e, spli ing he ec o o
de ia ions zin wo nonnega i e ec o s z+∈Rnand z−∈Rn, model (2) wi h he ℓ1dis ance can
hus be w i en as
min
z+,z−,yX
i∈N
wi(z+
i+z−
i)
s. o A(z+−z−)=0
0≤z+
i≤uzii∈ N S
0≤z−
i≤ −lzii∈ N S
upliyi≤z+
i≤uziyii∈ S
lpli(1 −yi)≤z−
i≤ −lzi(1 −yi)i∈ S
yi∈ {0,1},i∈ S,
(3)
y∈Rsbeing he ec o o bina y a iables associa ed o p o ec ion di ec ions. When yi=1 he
cons ain s mean upli≤z+
i≤uziand z−
i=0, hus he p o ec ion di ec ion is “uppe ”; when yi=0
we ge z+
i=0 and lpli≤z−
i≤ −lzi, hus he p o ec ion di ec ion is “lowe ”.
3. Heu is ic me hods applied o CTA
Model (3) is a di icul MILP e en o medium size ables. Finding an op imal (o quasi-
op imal) solu ion may equi e many hou s (e en days o weeks) o execu ion. When he numbe
o sensi i e cells is la ge, he b anch-and-cu scheme has shown o be ine icien , and in some
cases i is e en unable o p o ide a i s easible solu ion. Fo some massi e ins ances—such as,
e.g., hose in h p://www-eio.upc.es/~jcas o/huge_sdc_ins ances.h ml— he LPs
ob ained by ixing he alue o bina y a iables—associa ed o he p o ec ion di ec ions—a e
e en no sol able wi h mode a e compu a ional esou ces. Fo example, he LPs de i ed om
he six million cells ins ances o he abo e web add ess exhaus ed he memo y o a 16 gigaby es
wo ks a ion when sol ed wi h he CPLEX ba ie sol e . Un o una ely, he al e na i e simplex
sol e is e en mo e p ohibi i e, bu in e ms o CPU ime: in e io -poin algo i hms ha e shown
o be much mo e e icien han he simplex o he LPs de i ed om CTA [3, 5]. In his wo k we
conside a FR heu is ic and a hyb id FR+BCD app oach o CTA. FR and BCD a e, espec i ely,
desc ibed and ou lined below.
3.1. Fix-and- elax
FR is a decomposi ion me hod based on pa i ioning he se o bina y a iables in o clus e s
o i e a i ely sol e a sequence o MILPs o smalle dimension han he o iginal p oblem. In
hose smalle MILPs only a subse o a iables e ain hei bina y cons ain s while he es a e
ei he ixed o elaxed. Since only a educed subse o (non- ixed) 0-1 a iables is kep in ege
a each FR i e a ion, a compu a ional imp o emen is expec ed. FR can bo h be seen as an
app oach o ob aining (hope ully good) ini ial easible solu ions and p imal bounds. The e a e
6
1. Inpu : Numbe o clus e s k≥1
2. Pa i ion Sin o {V1, . . . , Vk}clus e s
3. Ini ialize =1 and sol e CT A1
FR
4. i CT A1
FR is in easible, STOP
5. else S o e alues o bina y a iables o CT A1
FR, se lowe bound LB, and ← +1
6. while ≤kdo
7. Sol e CT A
FR
8. i in easible, ede ine he pa i ion s uc u e as in (5)
9. else S o e op imal alues o bina y a iables o CT A
FR, and ← +1
10. end while
11. Re u n UB (solu ion o CT Ak
FR) and LB
Figu e 3: The ix-and- elax heu is ic applied o he CTA p oblem
o he app oaches o ini ial good solu ions in MILPs, such as he easibili y pump [17], bu as i
will seen in Sec ion 4, in p ac ice FR ou pe o med hem.
FR can be b ie ly s a ed as ollows. The se o bina y a iables is pa i ioned in o a ini e se
o clus e s {V1,...,Vk}. The o iginal MILP is hen decomposed in o ksubp oblems and a each
i e a ion one o hem is sol ed. A i s i e a ion (coun e se o 1) he subp oblem conside s
as bina y only he a iables o V1, while he in eg ali y o bina y a iables in he emaining
clus e s is elaxed. Con inuous a iables in he o iginal MILP main ain his same s a us a each
subp oblem. Hope ully, his i s subp oblem will be easily sol ed since he ca dinali y o V1is
much smalle han he numbe o bina y a iables in he o iginal MILP. Once sol ed, he coun e
is inc emen ed and he nex subp oblem is conside ed. A subp oblem o i e a ion ,k> >1,
he bina y a iables o clus e s Vi,i< , a e ixed o he alues o op imal solu ions om he
p e ious i e a ions; a iables o clus e V a e conside ed bina y, while he in eg ali y o a iables
in clus e s Vj,j> is elaxed. The p ocess is epea ed un il =k. I no subp oblem is in easible,
a (hope ully good) easible solu ion will be a ailable a e he solu ion o subp oblem k. In he
pa icula case o CTA, he se So sensi i e cells is pa i ioned in o he subse s {V1,...,Vk}, and
he subp oblem associa ed o (3)—which will be e e ed as (CT A
FR)—is
min
z+,z−,y
n
X
i=1
wi(z+
i+z−
i)
s. o A(z+−z−)=0
0≤z+
i≤uzii∈ N S
0≤z−
i≤ −lzii∈ N S
upliyi≤z+
i≤uziyii∈ S
lpli(1 −yi)≤z−
i≤ −lzi(1 −yi)i∈ S
yi=˜yii∈Sh=1,..., −1Vh
yi∈ {0,1}i∈V
yi∈[0,1] i∈Sh= +1,...,kVh,
(4)
whe e ˜yi,i∈ ∪h=1,..., −1Vh, a e he alues o bina y a iables ound a subp oblems CT A1
FR,...,
CT A −1
FR . Al hough FR is a heu is ic o MILP p oblems, i is easily swi ched o an op imal
app oach by se ing k=1.
I is wo h no ing ha he i s subp oblem CT A1
FR has wo main ea u es compa ed o he
subsequen ones:
7
ins ance TFR GAPFR %GAPBC %∆(BC,FR)GAPup
BC %Tup
BC ∆(Tup
BC ,TFR)
asym-40-50-5 72.76 2.52 †(40.70,5) †(38.18,5) ‡(1.20,13) ‡(87.76,13) ‡(15.00,13)
asym-40-50-15 158.75 3.55 86.67 83.11 ‡(1.94,13) ‡(465.84,13) ‡(307.09,13)
asym-40-50-30 210.51 5.60 99.98 94.38 1.84 1083.47 872.96
asym-40-60-5 95.40 2.40 †(0.88,5) †(−1.51,5) ‡(1.08,14) ‡(124.01,14) ‡(28.61,14)
asym-40-60-15 193.37 3.17 99.96 96.79 ‡(1.69,12) ‡(945.40,12) ‡(752.03,12)
asym-40-60-30 314.96 5.26 99.97 94.71 2.43 1107.84 792.88
asym-50-50-5 110.54 1.82 †(0.08,8) †(−1.74,8) ‡(0.62,14) ‡(135.65,14) ‡(25.11,14)
asym-50-50-15 186.95 3.11 86.66 83.54 ‡(1.02,11) ‡(804.02,11) ‡(617.07,11)
asym-50-50-30 333.50 5.94 99.94 93.99 2.21 1704.06 1370.55
asym-50-60-5 153.14 1.23 †(0.45,9) †(−0.78,9) ‡(0.85,13) ‡(163.61,13) ‡(10.46,13)
asym-50-60-15 282.79 3.05 93.33 90.28 ‡(1.46,13) ‡(1569.41,13) ‡(1286.62,13)
asym-50-60-30 406.42 5.52 99.92 94.40 2.39 1396.89 990.47
sym-40-50-5 8.99 2.43 12.69 10.26 ‡(1.61,2) ‡(15.09,2) ‡(6.10,2)
sym-40-50-15 115.34 4.31 45.79 41.48 ‡(2.56,4) ‡(443.91,4) ‡(328.57,4)
sym-40-50-30 371.35 4.61 63.90 59.29 ‡(4.36,3) ‡(2681.80,3) ‡(2310.45,3)
sym-40-60-5 10.52 2.79 14.44 11.65 1,33 37.76 27.24
sym-40-60-15 102.29 2.20 82.23 80.03 ‡(−,0) ‡(−,0) ‡(−,0)
sym-40-60-30 800.45 4.39 12.88 8.49 †(4.59,3) †(2870.02,3) †(2069.57,3)
sym-50-50-5 25.47 1.94 †(12.20,3) †(10.25,3) ‡(0.72,5) ‡(50.75,5) ‡(25.27,5)
sym-50-50-15 166.33 3.66 12.74 9.08 ‡(1.95,2) ‡(1434.04,2) ‡(1267.71,2)
sym-50-50-30 511.19 3.45 66.81 63.36 ‡(3.71,2) ‡(5049.30,2) ‡(4538.11,2)
sym-50-60-5 56.80 1.61 †(54.33,4) †(52.72,4) ‡(0.97,4) ‡(104.60,4) ‡(47.80,4)
sym-50-60-15 279.63 2.47 13.60 11.14 ‡(0.70,1) ‡(1055.10,1) ‡(775.47,1)
sym-50-60-30 833.45 3.95 47.62 43.66 ‡(4.38,2) ‡(3863.53,2) ‡(3030.08,2)
†(x,y)BC could no ind a solu ion in yo he o e all numbe o eplica ions wi hin TFR seconds;
xis he a e age alue o he emaining success ul uns.
‡(z,w)BC could no imp o e he FR solu ion in wo he o e all numbe o eplica ions wi hin he ime limi ;
zis he a e age alue o he emaining success ul uns.
Table 3: Compa ison be ween ix-an- elax and plain b anch-and-cu o syn he ic asymme ic and symme ic 1H2D
ins ances
F om Table 3 i can be concluded ha FR is mo e e icien han BC o as good easible
solu ions o 1H2D ables. In se e al uns (ma ked wi h ‡) BC could no ind a be e solu ion
han FR wi hin he ime limi . I is wo h no ing ha o all he 1H2D ins ances FR p o ided
solu ions wi h gaps below 6%. Fo he eal-wo ld gene al ins ances o Table 4 he si ua ion is
sligh ly di e en . These ins ances a e no gua an eed o ha e a hie a chical s uc u e, and his
may explain why FR is no as compe i i e as o 1H2D ables. FR p o ided a be e gap han BC
wi hin he same CPU ime in 17 o he 34 ins ances, and bo h FR and BC p o ided he same gap
in six adi ional cases. In six o hese cases BC could no imp o e he FR solu ion wi hin he wo
hou s ime limi . In he emaining ins ances BC ou pe o med FR.
4.3. Compa ison be ween ix-and- elax wi h block coo dina e descen and plain b anch-and-cu
As men ioned in sec ion 3.2, since FR can p o ide good easible solu ions as e in a e -
age han BC, BCD was wa m s a ed wi h he FR solu ion. This hyb id app oach was named
FR+BCD.
The BCD algo i hm pe o med in all cases a loop wi h wo clus e s, each one wi h a hal o
he sensi i e cells, pa i ioned a andom. A exi , he CPU compu a ion ime and he objec i e
unc ion alue we e sa ed. This CPU ime was added o he FR CPU ime and compa ed o he
CPU ime used by BC. We also ook in o accoun whe he he sensi i e cells had been co ec ly
p o ec ed in he inal solu ions, since accu acy e o s migh be p esen in some ins ances, making
ac ually in easible he p o ec ed able. This accu acy e o s a e due o he big-M cons ain s
z+
i≤uziyiand z−
i≤ −lzi(1 −yi) o (3) and (4), since uziand −lzican ake e y la ge alues.
14

ins ance TFR GAPFR %GAPBC %∆(BC,FR)GAPup
BC %Tup
BC ∆(Tup
BC ,TFR)
aus alia_ABS 6,05 73,87 3,84 -70,03 7,40 2,45 -3,6
b s4 6332,15 66,57 74,16 7,59 ‡ ‡ ‡
cbs 2,87 100,00 100,00 0,00 0,00 2,88 0,01
dale 595,85 48,44 48,44 0,00 48,44 7199,96 6604,11
des a is 204,32 19,53 99,97 80,44 1,80 706,48 502,16
hie 13d4 6410,73 82,86 99,98 17,12 ‡ ‡ ‡
hie 13 747,29 6,88 4,90 -1,98 4,90 159,24 -588,05
hie 13x13x13a 542,72 5,22 5,22 0,00 4,94 690,15 147,43
hie 13x13x13b 584,92 5,89 5,24 -0,65 5,24 369,13 -215,79
hie 13x13x13c 542,86 5,63 4,99 -0,65 4,99 243,43 -299,43
hie 13x13x13d 178,12 4,69 5,27 0,58 2,40 340,47 162,35
hie 13x13x13e 336,72 5,39 4,40 -0,99 4,40 269,82 -66,9
hie 13x13x7d 34,72 5,58 7,19 1,61 4,96 69,32 34,6
hie 13x7x7d 2,71 4,82 12,35 7,53 ‡ ‡ ‡
hie 16 4854,46 59,48 63,07 3,59 ‡ ‡ ‡
hie 16x16x16a 2803,76 44,96 48,80 3,84 44,71 3706,65 902,89
hie 16x16x16b 3401,2 33,49 99,95 66,46 31,89 6275,87 2874,67
hie 16x16x16c 3488,27 40,86 50,40 9,54 39,62 4926,13 1437,86
hie 16x16x16d 3776,81 57,66 63,32 5,66 57,07 5369,03 1592,22
hie 16x16x16e 3862,21 46,55 46,87 0,32 ‡ ‡ ‡
nine5d 6133,25 67,69 99,99 32,30 ‡ ‡ ‡
oso io 1,86 0,00 0,00 0,00 0,00 1,03 -0,83
sbs2008_C 543,88 50,11 3,36 -46,75 21,77 32,24 -511,64
sbs2008_E 4,56 4,73 4,73 0,00 4,73 2,94 -1,62
able1 0,62 8,38 13,43 5,06 4,92 1,25 0,63
able3 1909,18 25,39 15,07 -10,32 17,11 408,3 -1500,88
able4 1196,86 25,39 17,30 -8,09 18,60 511,64 -685,22
able5 720,49 22,80 20,20 -2,60 20,25 216,19 -504,3
able6 1,01 7,77 39,32 31,54 3,36 2,17 1,16
able7 0,1 1,01 0,41 -0,61 0,41 0,02 -0,08
able8 0,18 2,44 0,00 -2,44 1,35 0,04 -0,14
a gus 0,08 3,84 3,84 0,00 3,84 0,01 -0,07
oy3dsa ah 25,47 0,34 7,29 6,94 0,34 37,46 11,99
wo5in6 3010,89 66,04 99,99 33,95 63,91 7200,45 4189,56
‡Time limi eached wi hou imp o ing he easible FR solu ion.
Table 4: Compa ison be ween ix-an- elax and plain b anch-and-cu o eal ins ances
15
Objec i e Func ion
FR+BCD <BC FR+BCD >BC
FR+BCD <BC
mean (sd) ∆F
max |∆F|
mean (sd) ∆T
max |∆T|
N [Nasym ; Nsym]
−1.24 (1.08)
−4.23
−1564 (1872)
−6641
58 [27; 31]
1.86 (1.46)
7.26
−883 (1281)
−6351
119 [93; 26]
Time FR+BCD >BC
mean (sd) ∆F
max |∆F|
mean (sd) ∆T
max |∆T|
N [Nasym ; Nsym]
−1.55 (1.43)
−3.89
146 (207)
508
5 [4; 1]
0.83 (1.07)
4.17
49 (38)
182
58 [56; 2]
∆Fs ands o 100(FFR+BCD −FBC )/FBC .∆Ts ands o (TFR+BCD −TBC ), in seconds.
“sd” s ands o s anda d de ia ion.
Table 5: Summa y o esul s o 1H2D ins ances, in he compa ison be ween FR+BCD e sus BC.
Wi h ega d o 1H2D ins ances, i has been obse ed ha he ex a ime needed by he BCD
s age is ela ed o he numbe o sensi i e cells, al hough wi h conside able a iabili y especially
i he able is la ge. The 16 ables wi h mo e han 50,000 sensi i e cells consumed be ween 114
and 492 seconds, wi h a median ime o 255 seconds. In 104 ins ances wi h less han 10,000
sensi i e cells he median ime was 29.7 seconds. Compa ed o he ime employed by he FR
s age, i ook abou 40% o ha ime (median p opo ion): in 18 ins ances ou o 240 BCD las ed
longe han FR, gene ally in ables wi h high densi y o sensi i e cells.
Six y-one ables imp o ed he objec i e unc ion a e he BCD s age, and he o he s e-
mained in he same alue (no necessa ily in he same solu ion). The median change in he
objec i e unc ion wi h espec o he alue a ained by FR was 3%, wi h a maximum o 10%.
Imp o ing he solu ion equi es also mo e ime: 54.6% o FR ime, ins ead o 37% o he a-
bles no imp o ed. We obse ed a highe a e o success among he ables wi h high densi y o
sensi i e cells: an odd o 33 e sus 47 o ables wi h 30% o sensi i e cells, compa ed o 28
e sus 132 o ables wi h 15% o lowe p opo ion. The able size o he asymme y deg ee in
he p o ec ion le els we e no ela ed o imp o emen in he objec i e unc ion.
Table 5 summa izes he esul s wi h 1H2D ins ances o wo ac o s: solu ion imes (in ows)
and objec i e unc ion alues (in columns) be ween BC and FR+BCD. The wo ca ego ies o
each ac o a e ei he FR+BCD ou pe omed BC (“FR+BCD <BC”, i.e., less CPU ime o a
lowe objec i e unc ion alue) o he opposi e (“FR+BCD >BC”). Each o he ou cells shows
he numbe o ins ances (“N”), and some s a is ics (mean, s anda d de ia ion, maximum) abou
he change in bo h ac o s: ∆Fis he pe cen age change in he objec i e unc ion, ∆Tis he
absolu e change in he ime. Compa ing le e sus igh columns, we can see small di e ences
be ween he pe cen age changes in objec i e unc ion alues ( hey ange om −4.23% o 7.26%).
Howe e , compa ing abo e e sus below ows, we can see la ge di e ences wi h espec o
solu ion imes: 1564 and 883 seconds in a o o FR+BCD (177 cases) agains 146 and 49
seconds (63 cases) in a o o BC.
Fo he eal-wo ld ables, FR+BCD go be e solu ions han FR in 18 ins ances a e a BCD
cycle, whe eas i did no imp o e he FR objec i e unc ion in 16 cases. Table 6 epo s he esul s
ob ained. Columns “F.” and “T.” p o ide, espec i ely, he objec i e unc ion and CPU solu ion
imes o each me hod, BC, FR and FR+BCD o BCD. Column “∆(FFR,FFR+BCD)” p o ides
he ela i e change (as a pe cen age) in he objec i e unc ion be ween he FR and FR+BCD
solu ions. The ows a e o de ed by ∆(FFR,FFR+BCD); he i s ins ance shows a nega i e change
16
ins ance FBC FFR FFR+BCD TBC TFR.TBCD ∆(FFR,FFR+BCD)
able6‡28331962414 29686800000 29899600000 2.17 1 0.38 -0.72
dale 256 256 256 7199.96 595.9 596.62 0
hie 13 434834824.5 444063000 444063000 1312.7 747.3 8.18 0
hie 13d4 5.11488e+12 6143970000 6143970000 7201.23 6410.7 2769.53 0
hie 13x13x13a 434834824.5 436127000 436127000 895.44 542.7 6.16 0
hie 13x13x13b 44385.67 44865.8 44865.8 1444.94 584.9 7.14 0
hie 13x13x13c 368036.2 370564 370564 1561.69 542.9 8.47 0
hie 13x13x13d 414115.44 424074 424074 340.48 178.1 6.89 0
hie 13x13x13e 4644973.87 4693570 4693570 269.83 336.7 6.83 0
hie 13x7x7d 594401 593370 593370 29.19 2.7 0.24 0
hie 16 591756145.8 556221000 556221000 7200.41 4854.5 130.81 0
hie 16x16x16b 74891.53 76700.4 76700.4 7200.44 3401.2 121.52 0
oso io 13 13 13 1.8 1.9 1.35 0
sbs2008_E 109959.57 109960 109960 2.95 4.6 0.13 0
able7 9970266227 10031200000 10031200000 0.04 0.1 0.1 0
oy3dsa ah 5.0747e+14 5.07506e+14 5.07506e+14 37.46 25.5 0.22 0
hie 13x13x7d 1684140 1695250 1686430 241.81 34.7 2.59 0.52
able8 439 450 445 0.09 0.2 0.18 1.11
hie 16x16x16a 529703489.9 532145000 525466000 7200.31 2803.8 372.61 1.26
a gus 1103759.75 1103760 1088480 0.02 0.1 0.08 1.38
nine5d 6.20788e+12 1215790000 1191810000 7200.51 6133.3 2389.56 1.97
able5 10154665.5 11094800 10837600 7200.21 720.5 258.66 2.32
hie 16x16x16c 604844.28 620633 601548 7200.39 3488.3 672.13 3.08
able4 10290147784 11843300000 11433900000 7200.27 1196.9 142.92 3.46
hie 16x16x16e 9543201.06 9485820 9077750 7200.41 3862.2 692.34 4.3
able1 2.93185e+13 3.04227e+13 2.89576e+13 1.45 0.6 0.54 4.82
wo5in6 707133564.8 751514000 713214000 7200.45 3010.9 169.86 5.1
hie 16x16x16d 752648610.3 765577000 725869000 7200.31 3776.8 789.54 5.19
able3 1.20849e+12 1.39866e+12 1.29248e+12 7200.24 1909.2 171.17 7.59
des a is 234541294 286199000 241329000 2528.91 204.3 29.83 15.68
b s4 4114851966 3180710000 2592590000 7200.6 6332.2 6002.29 18.49
sbs2008_C 320835.46 621448 459655 66.34 543.9 0.43 26.03
aus alia_ABS 651 2396 746 2.91 6.05 4.46 68.86
cbs†0 268 0 2.88 2.9 1.79 100
‡This nega i e imp o emen is due o unp o ec ed cells in FR solu ion.
†cbs ins ance has a global op imum o ze o because all he sensi i e cells ha e null weigh s in he objec i e unc ion.
Table 6: Compa ison be ween plain b anch-and-cu and FR+BCD wi h eal-wo ld ins ances.
because he solu ion eached by FR was ac ually no easible, due o sligh de ia ions in some
sensi i e cells beyond hei p o ec ion le els, bu unde ec able wi h he (al eady igh ) in easi-
bili y ole ance in use by he sol e (c . big-M issue discussed abo e). In gene al, FR al eady
p o ided a good solu ion o ins ances which could no be imp o ed by BCD; his FR solu ion
was close o he one ob ained by BC, bu i was compu ed as e . On he o he hand, i is ema k-
able ha mos o he ins ances whe e he BCD cycle could imp o e he solu ion we e di icul
o he BC scheme, which used o exhaus he ime limi .
Table 7 summa izes he esul s o he eal-wo ld ins ances wi h espec o CPU ime and
objec i e unc ion alues. The s uc u e o his able is simila o ha o Table 5, bu wi h an
addi ional cen al column. This cen al column co esponds o ins ances wi hou ele an di -
e ences in he objec i e unc ion alue (i.e., (FFR+BCD −FBC)/FBC less han 5%). Each cell o
Table 7 epo s he numbe and names o i s ins ances. The i s ow includes he ins ances ha
we e sol ed as e wi h FR+BCD han wi h BC, and he ins ances ha could no be sol ed in he
2-hou ime limi by BC, bu hey could by FR+BCD. Mo eo e , some ins ances we e no sui -
ably p o ec ed: b s4, dale, able1, able3, able4, able5, able6 and able7 p esen some sensi i e
cells unp o ec ed in he BC solu ion; dale, able5 and able6 had he same p oblem wi h FR, and
BCD was in ouble as well wi h b s4 and able6: in gene al, FR+BCD deal be e han BC wi h
hese di icul ins ances.
17
Objec i e Func ion
FR+BCD <BC FR+BCD ≈BC FR+BCD >BC
FR+BCD <BC
b s4 hie 16 nine5d
able3 able4 able5
[N=6]
dale des a is
hie 13 hie 13d4
hie 13x13x13a
hie 13x13x13b
hie 13x13x13c
hie 13x13x13d
hie 13x13x7d
hie 13x7x7d
hie 16x16x16a
hie 16x16x16b
hie 16x16x16c
hie 16x16x16d
hie 16x16x16e
able1 able6
oy3dsa ah wo5in6
[N=19]
[N=0]
Time
FR+BCD >BC
[N=0] cbs hie 13x13x13e
oso io sbs2008_E
able7 able8 a gus
[N=7]
aus alia_ABS
sbs2008_C
[N=2]
Table 7: Summa y o esul s o eal ins ances, in he compa ison be ween FR+BCD e sus BC.
Nine ables we e sol ed as e wi h he pu e BC scheme, bu i is wo h no ing ha only wo
(sbs2008_C and hie 13x13x13e) can be conside ed as challenging, since hey needed mo e han
one minu e o be sol ed, whe eas ou (oso io, able7, able8 and a gus) ha e ew sensi i e cells
and could be sol ed e y quickly by bo h FR+BCD and BC.
To sum up, Table 7 shows ha he combina ion FR+BCD is compe i i e wi h BC in he
solu ion’s quali y, and, in addi ion, i p o ec s he able in signi ican ly less ime.
4.4. Compa ison be ween ix-and- elax and o he heu is ics
Cu en s a e-o - he-a MILP sol e s can be u ned in o heu is ic app oaches by uning some
o hei p e-build heu is ics. Fo a ai compa ison, FR is es ed in his sec ion agains easibili y
pump (FP), elaxa ion induced neighbo hod sea ch (RINS), and FR+BC (wa m s a ing CPLEX
om he FR solu ion) wi h and wi hou polishing.
4.4.1. Fix-and- elax and easibili y pump heu is ics
FP [17] is conside ed an e icien heu is ic o he as compu a ion o hope ully good ini ial
easible solu ions o MILPs. We used he objec i e easibili y pump (oFP) [1], which is mo e
e icien han FP in e ms o quali y o he solu ion and he analy ic cen e easibili y pump (AC-
FP) [2], which was in oduced as a good al e na i e in some MILP ins ances (ei he in ime
o quali y o he solu ion). Table 8 shows a compa ison be ween FR and hese FP a ian s o
eal ins ances. I epo s he p imal gap o he FR and FP solu ions (columns “GAPFR%” and
“GAPFP%”, espec i ely), he CPU ime equi ed by FR and FP o compu e he easible solu ion
(columns “TFR” and “TFP”, espec i ely), and he di e ence be ween bo h me hods in CPU imes
and gaps (columns “∆(TFP,TFR)” and “∆(FP,FR)”, espec i ely). We an bo h oFP and AC-FP.
Table 8 only shows he esul o he bes FP a ian , i.e., he one ha p o ides he lowes gap,
and in case o equal gaps, he as es one. The bes FP a ian is clea ly ma ked in he able.
18
ins ance GAPFR%TFR GAPFP%TFP ∆(TFP,TFR)∆(FP,FR)
aus alia_ABS 73,87 6,05 95,90AC−FP 26 19,95 22,03
b s4 66,57 6332,15 74,09oFP 552 -5780,15 7,52
cbs 100,00 2,87 100,00oFP 20 17,13 0,00
dale 48,44 595,85 98,52oFP 27 -568,85 50,08
des a is 19,53 204,32 21,93AC−FP 222 17,68 2,40
hie 13d4 82,86 6410,73 † † † †
hie 13 6,88 747,29 58,96oFP 126 -621,29 52,08
hie 13x13x13a 5,22 542,72 63,36AC−FP 122 -420,72 58,14
hie 13x13x13b 5,89 584,92 53,36AC−FP 235 -349,92 47,47
hie 13x13x13c 5,63 542,86 54,01oFP 217 -325,86 48,38
hie 13x13x13d 4,69 178,12 99,86oFP 132 -46,12 95,17
hie 13x13x13e 5,39 336,72 99,87oFP 128 -208,72 94,48
hie 13x13x7d 5,58 34,72 60,49AC−FP 13 -21,72 54,91
hie 13x7x7d 4,82 2,71 73,56oFP 2 -0,71 68,73
hie 16 59,48 4854,46 68,36AC−FP 2852 -2002,46 8,89
hie 16x16x16a 44,96 2803,76 99,99oFP 4537 1733,24 55,03
hie 16x16x16b 33,49 3401,2 99,91oFP 3742 340,8 66,42
hie 16x16x16c 40,86 3488,27 99,93oFP 3937 448,73 59,07
hie 16x16x16d 57,66 3776,81 66,88AC−FP 2706 -1070,81 9,22
hie 16x16x16e 46,55 3862,21 81,19oFP 4430 567,79 34,64
nine5d 67,69 6133,25 † † † †
oso io 0,00 1,86 27,65oFP 0 -1,86 27,65
sbs2008_C 50,11 543,88 82,64oFP 12 -531,88 32,53
sbs2008_E 4,73 4,56 74,15oFP 2 -2,56 69,42
able1 8,38 0,62 2,17oFP 0 -0,62 -6,20
able3 25,39 1909,18 100,00oFP 323 -1586,18 74,61
able4 25,39 1196,86 96,81AC−FP 379 -817,86 71,42
able6 7,77 1,01 9,05oFP 0 -1,01 1,28
able7 1,01 0,1 69,21oFP 0 -0,1 68,20
able8 2,44 0,18 6,51oFP 0 -0,18 4,07
a gus 3,84 0,08 0,92oFP 0 -0,08 -2,92
oy3dsa ah 0,34 25,47 65,07oFP 5 -20,47 64,73
wo5in6 66,04 3010,89 61,91AC−FP 5234 2223,11 -4,13
†Time limi eached wi hou inding a easible easibili y pump solu ion.
oFP: bes solu ion p o ided by oFP.
AC−FP: bes solu ion p o ided by AC-FP.
Table 8: Compa ison be ween ix-and- elax and easibili y pump o eal ins ances.
I is clea ly seen ha FR ou pe o med FP o CTA in e ms o quali y o he solu ion. In
mos cases, FR p o ided a be e gap han FP by a big di e ence. Only in h ee ins ances FP was
be e . FP eached he ime limi wi hou a easible solu ion in wo ins ances. Howe e , FP is in
gene al as e han FR in o de o ind a easible solu ion. I can be concluded ha , o he CTA
p oblem, FR ins ead o FP should be used o inding good easible solu ions wi hin a easonable
sho ime.
4.4.2. Fix-and- elax and RINS and local b anching heu is ics
RINS [12] is a heu is ic ha explo es a neighbo hood o he cu en incumben solu ion
and he con inuous elaxa ion a a node ho he BC ee o y o ind a new and imp o ed
incumben . CPLEX BC inco po a es RINS, allowing he use o con ol how o en o apply he
heu is ic h ough a equency pa ame e . A alue >0 means ha RINS is applied a nodes
h=0, ,2 , ... while o =0 CPLEX au oma ically decides when o apply he heu is ic. The
esul s o Table 4 we e ob ained wi h =0; as i was shown in ha able, FR ou pe o med BC
in a conside able pe cen age o eal-wo ld ins ances. Table 9 adds a compa ison be ween FR and
BC wi h =50. The meaning o columns is he same as in Table 4. The alue o , ei he
0 o 50, is epo ed in he new column RINS . We only conside ed he subse o eal-wo ld
19

ins ance TFR GAPFR %RINS GAPBC %∆(BC,FR)GAPup
BC %Tup
BC ∆(TFR,Tup
BC )
b s4 6332,15 66,57 0 74,16 7,59 ‡ ‡ ‡
50 100 33,43 ‡ ‡ ‡
dale 595,85 48,44 0 48,44 0 48,44 7199,96 6604,11
50 48,44 0 ‡ ‡ ‡
des a is 204,32 19,53 0 99,97 80,44 1,8 706,48 502,16
50 99,97 80,44 1,78 3090,16 2885,84
hie 13 747,29 6,88 0 4,9 -1,98 4,9 159,24 -588,05
50 99,98 93,1 4,9 1239,3 492,01
hie 13x13x13a 542,72 5,22 0 5,22 0 4,94 690,15 147,43
50 99,99 94,77 4,94 1426,84 884,12
hie 13x13x13b 584,92 5,89 0 5,24 -0,65 5,24 369,13 -215,79
50 99,98 94,09 4,87 2742,67 2157,75
hie 13x13x13c 542,86 5,63 0 4,99 -0,65 4,99 243,43 -299,43
50 99,98 94,34 4,99 3405,16 2862,3
hie 13x13x7d 34,72 5,58 0 7,19 1,61 4,96 69,32 34,6
50 38,93 33,34 4,84 158,96 124,24
hie 13x7x7d 2,71 4,82 0 12,35 7,53 ‡ ‡ ‡
50 24,1 19,28 4,53 20,09 17,38
hie 16 4854,46 59,48 0 63,07 3,59 ‡ ‡ ‡
50 100 40,52 ‡ ‡ ‡
hie 16x16x16a 2803,76 44,96 0 48,8 3,84 44,71 3706,65 902,89
50 100 55,03 43,87 7200,57 4396,81
hie 16x16x16d 3776,81 57,66 0 63,32 5,66 57,07 5369,03 1592,22
50 100 42,33 56,08 7200,59 3423,78
hie 16x16x16e 3862,21 46,55 0 46,87 0,32 ‡ ‡ ‡
50 99,96 53,41 46,18 7200,52 3338,31
able3 1909,18 25,39 0 15,07 -10,32 17,11 408,3 -1500,88
50 100 74,61 16,78 2303,34 394,16
able4 1196,86 25,39 0 17,3 -8,09 18,6 511,64 -685,22
50 100 74,61 14,64 2163,97 967,11
able5 720,49 22,8 0 20,2 -2,6 20,25 216,19 -504,3
50 100 77,2 16,96 1441,96 721,47
‡Time limi eached wi hou imp o ing he easible ix-and- elax solu ion.
Table 9: Compa ison be ween FR and BC wi h equency RINS equal o 0 and 50 o some eal-wo ld ins ances
ins ances whose BC ee had mo e han 50 nodes. F om Table 9 i can be concluded ha FR s ill
ou pe o ms BC wi h he RINS heu is ic using =50.
We addi ionally ied RINS equencies ∈ {100,150,200}, ob aining exac ly he same e-
sul s ( hey a e hus omi ed in Table 9). As s a ed abo e, CPLEX always applies he RINS heu is-
ic a node 0 o any >0. We no ed ha , since RINS is an expensi e heu is ic, i exhaus ed
mos o he allowed ime ( ha o he FR heu is ic) a node 0, making i ele an he pa icula
alue o . The e o e, a leas o his pa icula applica ion, RINS =0 seems o be he bes
choice. Indeed, we no ed ha when =0 CPLEX does no apply RINS o node 0 in many
ins ances.
The local b anching (LB ) heu is ic also explo es he neighbo hood o an incumben solu-
ion, bu by adding cons ain s based on he numbe o bina y a iables lipping hei alues
wi h espec he incumben [18]. Running CPLEX wi h he LB heu is ic, and se ing as ime
limi he CPU ime o FR, we only obse ed di e ences wi h RINS =0 o i e ins ances
o Table 9: hie 13x13x7d (solu ions o 6.2% and 7.2% gaps o LB and RINS, espec i ely),
hie 13x7x7d (24.1% gap o LB , 12,4% gap o RINS), hie 16 (61.2% o LB , 63.0% o
RINS), hie 16x16x16a (44.4% o LB , 49.0% o RINS), and hie 16x16x16d (62.4% o LB ,
63,0% o RINS). LB only clea ly ou pe o med RINS =0 in hie 16x16x16a; o ha in-
s ance, LB was also mo e e icien han FR.
20
ins ance TFR GAPFR %TFR+BC GAPFR+BC %TBC GAPBC %∆(FR +BC,BC)∆(TFR+BC ,TBC )
asym-40-50-5 72.76 1.89 264.45 0.47 306.46 0.35 0.12 −42.01
asym-40-50-15 158.75 3.13 †(1223.55,1) 0.71 †(1357.15,3) 0.67 0.04 −133.60
asym-40-50-30 210.51 5.41 †(1606.53,2)0.82 †(2062.43,3)1.04 −0.23 −455.90
asym-40-60-5 95.40 1.75 259.40 0.40 231.36 0.40 0.00 28.04
asym-40-60-15 193.37 3.11 †(1352.60,2)0.93 †(1430.58,4)1.02 −0.09 −77.98
asym-40-60-30 314.96 5.07 †(2181.63,6) 1.40 †(2040.04,6) 1.21 0.19 141.59
asym-50-50-5 110.54 1.53 †(560.24,1) 0.43 476.49 0.35 0.08 83.75
asym-50-50-15 186.95 2.86 †(1403.85,3)0.90 †(1533.78,4)0.93 −0.03 −129.93
asym-50-50-30 333.50 5.81 †(2417.91,5) 1.52 †(2284.80,5) 1.74 −0.22 133.11
asym-50-60-5 153.14 1.06 268.43 0.64 286.51 0.48 0.16 −18.08
asym-50-60-15 278.72 2.73 †(1263.52,3)1.24 †(1408.72,3)‡(8.67,2)−7.43 −145.21
asym-50-60-30 416.11 5.54 †(2768.88,8) 1.60 †(2665.53,7) ‡(1.74,1) −0.14 103.35
sym-40-50-5 8.99 2.00 41.51 0.40 29.10 0.68 −0.28 12.40
sym-40-50-15 115.34 4.21 1114.50 0.75 720.22 0.80 −0.06 394.29
sym-40-50-30 371.35 4.62 †(3097.98,4) 1.93 †(3131.25,3) 1.77 0.16 −33.27
sym-40-60-5 10.52 2.68 32.82 0.63 60.05 0.52 0.11 −27.23
sym-40-60-15 102.29 2.16 1731.73 0.86 1381.75 0.82 0.04 349.98
sym-40-60-30 800.45 4.40 †(3600,5)3.22 †(3600,5)6.55 −3.33 0
sym-50-50-5 25.47 1.88 103.45 0.50 85.12 0.57 −0.07 18.33
sym-50-50-15 166.33 3.66 †(2370.98,1) 0.97 †(1728.63,1) 0.75 0.22 642.35
sym-50-50-30 511.19 3.45 †(3600,5)2.54 †(3600,5)4.46 −1.92 0
sym-50-60-5 56.80 1.59 80.64 0.54 134.79 0.36 0.17 −54.15
sym-50-60-15 279.63 2.46 2347.58 0.91 1894.95 0.74 0.17 452.63
sym-50-60-30 833.45 3.93 †(3600,5)3.54 †(3600,5)6.31 −2.77 0
†(x,y)a solu ion wi hin 1% op imali y gap could no be ound in yo he o e all numbe o eplica ions wi hin he ime limi o 3600 seconds;
xis he a e age CPU ime o he emaining success ul uns.
‡(z,w)no easible solu ion was ound in wo he o e all numbe o eplica ions wi hin he ime limi o 3600 seconds;
zis he a e age gap o he emaining uns.
Table 10: Using he ix-and- elax solu ion o wa m s a CPLEX b anch-and-cu
4.5. Using ix-and- elax o wa m s a b anch-and-cu
Table 10 shows he esul s ob ained wi h FR+BC (i.e., wa m s a ing BC wi h he FR solu-
ion) on 1H2D ables. The able epo s he CPU compu a ion ime and gap (as a pe cen age)
o he FR solu ion (columns “TFR” and “GAPFR%”). The same in o ma ion is p o ided o
he FR+BC solu ion using a 1% op imali y gap (columns “TFR+BC ” and GAPFR+BC%); and o
CPLEX BC wi hou s a ing poin wi h he same 1% op imali y gap (columns TBC and GAPBC%).
Columns ∆(FR +BC,BC) and ∆(TFR+BC ,TBC) gi e he di e ence in gap and CPU ime be ween
he FR+BC and BC solu ions. A ime limi o one hou was conside ed o hese uns. Some
FR+BC o BC execu ions we e unable o ind a solu ion o 1% op imali y gap wi hin his ime
limi ; hese a e clea ly ma ked in Table 10. BC could no ind a easible solu ion wi hin he
ime limi o h ee ins ances, which a e also clea ly ma ked in he able. In hose si ua ions he
a e age gap epo ed in Table 10 may be g ea e han 1%.
FR+BC p o ided a lowe gap han BC in 12 o 24 cases. In addi ion, in six o hese 12 cases
he CPU ime o FR+BC was in e io . These six success ul FR+BC execu ions a e ma ked in
bold ace in Table 10. These esul s a e no en i ely sa is ac o y, since i could be expec ed ha
p o iding a good incumben om he beginning would signi ican ly educe he compu a ional
bu den o all he ins ances, by p uning po ions o he sea ch space. In ac , we ound epo ed
simila expe iences. In h p://www2.isye.ga ech.edu/~ ca ajal3/2012/2012-12-24_e ec -o -in o ma ion
he au ho p esen s an expe imen wi h ins ances om MIPLIB 2010 [28] whe e p o iding he
op imal solu ion as a wa m s a can ac ually be ha m ul o he pe o mance o he sol e .
We also applied he CPLEX polishing heu is ic o he FR s a ing poin . This heu is ic,
which can be e y ime consuming, ies o exploi an ini ial easible solu ion p o ided o BC by
21
sol ing an al e na i e b anch-and-cu . We an FR+BC wi h and wi houg polishing. Ac i a ing
he polishing he gap was imp o ed in 92% o he execu ions; howe e he a e age gap educ ion
was 0.4%. On he o he hand, in 83% o he execu ions he polishing signi ican ly inc eased he
CPU ime: an a e age inc emen o 59%. In he emaining 17% o execu ions he CPU ime
was educed, in a e age, a 18%. F om hese igu es, i can be concluded ha he polishing is in
gene al e y ime consuming o CTA, and i is no wo h he gap educ ion p o ided.
5. Conclusions
FR, ei he alone o in combina ion wi h o he heu is ics such as BCD, has shown o be an e i-
cien app oach o he di icul MILP CTA p oblem. Ini ially de eloped o scheduling p oblems
ha can be pa i ioned in o s ages, FR has also been success ully applied o a class o hie a chical
ables named 1H2D. Fo hese ables, i was compe i i e agains BC, and FP o RINS heu is ics.
Fo gene al eal-wo ld ables, FR and FR+BCD ou pe o med BC in 73% o he ins ances es ed.
P omising esul s we e also ob ained in a educed se o ins ances by wa m s a ing BC wi h he
FR solu ion.
Quick ools o p o ide as solu ions o CTA a e a necessi y because o he inc easing abili y
o NSAs o c ea e mo e complex and huge ables om collec ed da a. FR is hus an s ep in
his di ec ion. Combining FR wi h o he heu is ics, o embedding FR in exac app oaches, like
Bende s e o mula ion, is pa o he u he wo k o be done in his ield.
Acknowledgmen s
This wo k has been suppo ed by g an MTM2012-31440 o he Spanish Go e nmen . We
hank wo anonymous e iewe s o hei commen s which g ea ly imp o ed he p esen a ion o
he pape .
Re e ences
[1] T. Ach e be g, T. Be hold, Imp o ing he easibili y pump, Disc e e Op imiza ion 4, 77–86, (2007).
[2] D. Baena, J. Cas o, Using he analy ic cen e in he easibili y pump, Ope a ions Resea ch Le e s, 39, 310–317
(2011).
[3] J. Cas o, Minimum-dis ance con olled pe u ba ion me hods o la ge-scale abula da a p o ec ion, Eu opean
Jou nal o Ope a ional Resea ch, 171, 39–52 (2006).
[4] J. Cas o, A sho es -pa hs heu is ic o s a is ical da a p o ec ion in posi i e ables, INFORMS Jou nal on Com-
pu ing, 19(4), 520–533 (2007).
[5] J. Cas o, Recen ad ances in op imiza ion echniques o s a is ical abula da a p o ec ion, Eu opean Jou nal o
Ope a ional Resea ch, 21, 257–269 (2012).
[6] J. Cas o, On assessing he disclosu e isk o con olled adjus men me hods o s a is ical abula da a, In e na ional
Jou nal o Unce ain y, Fuzziness and Knowledge-Based Sys ems, 20, 921–941 (2012) .
[7] J. Cas o, D. Baena, Using a ma hema ical p og amming modeling language o op imal CTA, Lec u e No es in
Compu e Science, 5262, 1–12 (2008).
[8] J. Cas o, A. F angioni, C. Gen ile, Pe spec i e e o mula ions o he CTA p oblem wi h L2dis ances, Ope a ions
Resea ch, 62(4), 891–909 (2014).
[9] J. Cas o, S. Giessing, Tes ing a ian s o minimum dis ance con olled abula adjus men . In: Monog aphs o
O icial S a is ics, Eu os a -O ice o O icial Publica ions o he Eu opean Communi ies, Luxembou g, 333–343
(2006).
[10] J. Cas o, J.A. González, Assessing he in o ma ion loss o con olled adjus men me hods in wo-way ables,
Lec u e No es in Compu e Science, 8744, in p ess (2014).
[11] R.A. Dandeka , L.H. Cox, Syn he ic abula da a: an al e na i e o complemen a y cell supp ession, manusc ip ,
Ene gy In o ma ion Adminis a ion, U.S. Depa men o Ene gy (2002).
22
[12] E. Danna, E. Ro hbe g, C. Le Pape, Explo ing elaxa ion induced neighbo hoods o imp o e MIP solu ions, Ma h-
ema ical P og amming, 102, 71-90 (2005).
[13] C. Dillenbe ge , L.F. Escude o, A. Wollensak, W. Zhang. On p ac ical esou ce alloca ion o p oduc ion planning
and scheduling wi h pe iod o e lapping se ups, Eu opean Jou nal o Ope a ional Resea ch, 75, 275–286 (1994).
[14] E.D. Dolan, J.J. Mo é, Benchma king op imiza ion so wa e wi h pe o mance p o iles, Ma hema ical P og am-
ming, A, 91, 201–13 (2002).
[15] L.F. Escude o, J. Salme ón, On a ix-and- elax amewo k o a class o p ojec scheduling p oblems, Annals o
ope a ions esea ch, 140, 163–188 (2005).
[16] D. Fe ei a, R. Mo abi o, S. Rangel, Relax and ix heu is ics o sol e one-s age one-machine lo -scheduling models
o small-scale so d ink plan s, Compu e s & Ope a ions Resea ch, 37, 684–691 (2010).
[17] M. Fische i, F. Glo e , A. Lodi, The Feasibili y Pump, Ma hema ical P og amming, 104, 91–104 (2005).
[18] M. Fische i, A. Lodi, Local b anching, Ma hema ical P og amming, 98, 23–47 (2003).
[19] M. Fische i, J.J. Salaza , Sol ing he cell supp ession p oblem on abula da a wi h linea cons ain s, Managemen
Science, 47, 1008–1026 (2001).
[20] S. Giessing, P e- abula pe u ba ion wi h con olled abula adjus men : some conside a ions, Lec u e No es in
Compu e Science, 8744, 48–61 (2014).
[21] S. Giessing, J. Höhne, Elimina ing small cells om census coun s ables: some conside a ions on ansi ion p oba-
bili ies, Lec u e No es in Compu e Science, 6344, 52–65 (2010).
[22] F. Glo e , L.H. Cox, R. Pa il, J.P. Kelly, In eg a ed exac , hyb id and me aheu is ic lea ning me hods o con iden-
iali y p o ec ion, Annals o Ope a ions Resea ch, 183, 47–73 (2011).
[23] J.A. González, J. Cas o, A heu is ic block coo dina e descen app oach o con olled abula adjus men , Com-
pu e s & Ope a ions Resea ch, 38, 1826–1835 (2011).
[24] M.S. He nández, J.J. Salaza , Enhanced con olled abula adjus men , Compu e s & Ope a ions Resea ch, 43,
61–67 (2014).
[25] A. Hundepool, The A gus so wa e in CENEX, Lec u e No es in Compu e Science, 4302, 334–346 (2006).
[26] A. Hundepool, J. Domingo-Fe e , L. F anconi, S. Giessing, R. Lenz, J. Naylo , E. Schul e No d-
hol , G. Se i, P.-P. De Wol , Handook on S a is ical Disclosu e Con ol 1.2, Ne wo k o Excellence in
he Eu opean S a is ical Sys em in he ield o S a is ical Disclosu e Con ol, 2010. A ailable online a
h p://neon. b.cbs.nl/casc/handbook.h m.
[27] A. Hundepool, J. Domingo-Fe e , L. F anconi, S. Giessing, E. Schul e No dhol , K. Spice , P.-P. De Wol , S a is-
ical Disclosu e Con ol. Chiches e , Wiley, 2012.
[28] T. Koch, e al., MIPLIB 2010. Mixed in ege p og amming lib a y e sion 5, Ma hema ical P og amming Compu-
a ion, 3, 103–163 (2011).
[29] H. Mi elmann, Decision ee o op imiza ion so wa e, h p://pla o.asu.edu/guide.h ml (2014).
[30] K. Soinin aa a, T. Oinonen, A. Nissinen, Balancing con iden iali y and usabili y: p o ec ing sensi i e da a in he
case o inwa d Fo eign A iliaTes S a is ics (FATS), Lec u e No es in Compu e Science, 8744, 338–349 (2014).
[31] L. Zaya z, U.S. Census Bu eau, communica ion a Join UNECE/Eu os a Wo k Session on S a is ical Da a Con i-
den iali y, Bilbao (Basque Coun y, Spain) (2009).
23