Efficient neighborhood evaluation for the maximally diverse grouping problem

Schulz, A ne
A icle — Published Ve sion
E icien neighbo hood e alua ion o he maximally
di e se g ouping p oblem
Annals o Ope a ions Resea ch
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Schulz, A ne (2024) : E icien neighbo hood e alua ion o he maximally di e se
g ouping p oblem, Annals o Ope a ions Resea ch, ISSN 1572-9338, Sp inge US, New Yo k, NY, Vol.
341, Iss. 2, pp. 1247-1265,
h ps://doi.o g/10.1007/s10479-024-06217-9
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/315283
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Annals o Ope a ions Resea ch (2024) 341:1247–1265
h ps://doi.o g/10.1007/s10479-024-06217-9
ORIGINAL-COMPARATIVE COMPUTATIONAL STUDY
E icien neighbo hood e alua ion o he maximally di e se
g ouping p oblem
A ne Schulz1,2
Recei ed: 23 Oc obe 2023 / Accep ed: 5 Augus 2024 / Published online: 21 Augus 2024
© The Au ho (s) 2024
Abs ac
The Maximally Di e se G ouping P oblem is one o he well-known combina o ial op i-
miza ion p oblems wi h applica ions in he assignmen o s uden s o g oups o cou ses. Due
o i s NP-ha dness se e al (me a)heu is ic solu ion app oaches ha e been p esen ed in he
li e a u e. Mos o hem include he inse ion o an i em o one g oup in o ano he g oup
and he swap o wo i ems cu en ly assigned o di e en g oups as neighbo hoods. The
pape p esen s a new e icien implemen a ion o bo h neighbo hoods and compa es i wi h
he s anda d implemen a ion, in which all inse s/swaps a e e alua ed, as well as he neigh-
bo hood decomposi ion app oach. The esul s show ha he newly p esen ed app oach is
clea ly supe io o la ge ins ances allowing o up o 160% mo e i e a ions in compa ison
o he s anda d implemen a ion and up o 76% mo e i e a ions in compa ison o he neigh-
bo hood decomposi ion app oach. Mo eo e , he esul s can also be used o (me a)heu is ic
algo i hms o o he g ouping o clus e ing p oblems.
Keywo ds Combina o ial op imiza ion ·G ouping ·Local sea ch ·Compu a ional
e iciency
1 In oduc ion
The Maximally Di e se G ouping P oblem (MDGP) is a well-known and well-in es iga ed
combina o ial op imiza ion p oblem. Gi en a se o i ems i∈Iwi h a pai wise di e si y
dij ≥0, he ask is o assign he i ems o g oups g∈Gsuch ha each g oup gge s a leas lg
and a mos ugi ems assigned and he wi hin g oup di e si y is maximized o e all g oups.
The MDGP is an impo an combina o ial op imiza ion p oblem o wo easons: Fi s , i has
a wide ield o applica ions such as he assignmen o s uden s o p ojec g oups (Behesh ian-
A dekani & Mahmood, 1986) o eams (Dias & Bo ges, 2017), he assignmen o pupils o
u o g oups (Bake & Benn, 2001) o o child en o equally s ong spo eams (Rubin &
Bai, 2015). Mo eo e , he e a e applica ions in inal exam scheduling, VLSI design (Wei z &
Lakshmina ayanan, 1998), and an iclus e ing. An iclus e ing aims like he MDGP o pa i ion
BA ne Schulz
a ne.schulz@uni-hambu g.de ; [email p o ec ed]
1Ins i u e o Ope a ions Managemen , Uni e si ä Hambu g, Moo weidens aße 18, 20148 Hambu g,
Ge many
2Ins i u e o Quan i a i e Logis ics, Helmu Schmid Uni e si y, Hols enho weg 85, 22043 Hambu g,
Ge many
123
1248 Annals o Ope a ions Resea ch (2024) 341:1247–1265
i ems in o disjoin g oups such ha g oups a e simila bu wi hin-g oup he e ogenei y is high
(B usco e al., 2020; Papenbe g, 2024). Applica ions a e in he assignmen o pa icipan s o
g oups (Ba is a e al., 2023) and in di iding da a se s o c oss alida ion (Papenbe g & Klau,
2021). Second, he MDGP is NP-ha d o sol e (Feo & Khella , 1990) al hough i can be
o mula ed as a sho in ege p og am, which can easily be linea ized (compa e e.g. (Gallego
e al., 2013)):
max 
g∈G

i∈I

j∈I:j>i
dijxigxjg
wi h he cons ain s (1)

g∈G
xig =1∀i∈I(2)
lg≤
i∈I
xig ≤ug∀g∈G(3)
xig ∈{0,1}∀i∈I,g∈G(4)
In he s udy by Gallego e al. (2013), only ins ances wi h up o 12 i ems could be sol ed o
op imali y. Gi en ha dij alues o en ha e a ce ain s uc u e in p ac ice, e.g. hey a e he
di e ence o a ibu e alues (Schulz, 2021) o bina y alues (Minge s & O’B ien, 1995),
ins ances o up o 30–70 i ems can be sol ed o p o en op imali y (Schulz, 2022). I a mos
wo a ibu es a e conside ed, Schulz (2021) p o ed ha e en la ge ins ances can be sol ed
e icien ly.
Howe e , i we wan o sol e la ge ins ances o ins ances wi h gene al dij ≥0(dii =0
o all i∈I), e icien heu is ic solu ion me hods a e equi ed. While ea lie app oaches
ocussed on cons uc ion and local sea ch imp o emen heu is ics (compa e he o e iew
by Wei z and Lakshmina ayanan (1998)), la e pape s ocussed on di e en me aheu is ic
solu ion app oaches. In he las yea s, B imbe g e al. (2015) de eloped a skewed gene al
a iable neighbo hood sea ch, Palubeckis e al. (2015) an i e a ed abu sea ch app oach,
Lai and Hao (2016) an i e a ed maxima sea ch heu is ic, Lai e al. (2021a) a neighbo hood
decomposi ion based a iable neighbo hood sea ch and abu sea ch, and Yang e al. (2022)
a h ee-phase app oach wi h a dynamic popula ion size. These a e he mos ecen and suc-
cess ul app oaches. Please see Lai and Hao (2016) o a mo e dep h e iew o me aheu is ic
solu ion app oaches o he MDGP.
The ocus o he pape a hand is no o de elop a new ad anced me aheu is ic solu ion
app oach bu o conside he e alua ion o neighbo hoods, especially inse ions and swaps,
wi hin hese app oaches. We p esen a new me hod o e alua e hese neighbo hoods mo e
e icien ly. In doing so, he pape is inspi ed by he neighbo hood decomposi ion app oach
by Lai e al. (2021a).
Gi en a easible solu ion o he MDGP, i.e. an assignmen o each i em o exac ly one
g oup such ha each g oup has a numbe o i ems be ween lgand ugassigned, he inse ion
neighbo hood con ains all easible solu ions such ha exac ly one i em is assigned o a di e -
en g oup. Thus, gi en solu ion y, whe ea yiindica es he g oup o i em i, he neighbo hood
includes all solu ions ¯ysuch ha (2)–(4) a e ul illed and yi=¯yi o all bu exac ly one
i em i∈I. Co espondingly, he swap neighbo hood o yincludes all solu ions ¯ysuch ha
(2)–(4) a e ul illed, yi=¯yi o all i ems i∈I { j,j},¯yj=yj,and ¯yj=yj.These wo
neighbo hoods a e used in mos o he ad anced solu ion me hods o he MDGP, includ-
ing he i e ad anced algo i hms men ioned be o e as well as o example Bake and Powell
(2002), Chen e al. (2011), Fan e al. (2011), Palubeckis e al. (2011), Rod iguez e al. (2013),
123
Annals o Ope a ions Resea ch (2024) 341:1247–1265 1249
U oše i´c(2014),andSchulz(2023). In he pape a hand, we p esen a new e icien me hod
enhancing he neighbo hood decomposi ion (ND) me hod desc ibed in Lai e al. (2021a) o
e alua e he wo neighbo hoods as e han in he s anda d implemen a ion, which simply
e alua es he en i e neighbo hood, and he ND implemen a ion.
The p esen ed neighbo hood e alua ion can also be applied o o he g ouping o clus e ing
p oblems. These include clus e ing p oblems like he capaci a ed clus e ing p oblem (Lai e
al., 2021b) and he capaci a ed p-median p oblem (Zheng e al., 2021). I can also be applied
o he a io cu and no malized cu g aph pa i ioning p oblem (Palubeckis, 2022), o ehicle
ou ing p oblems (e.g. P ei e and Schulz (2022)o Zhoue al.(2023)) o o pa allel machine
scheduling (Yalaoui & Chu, 2002).
The pape is cons uc ed as ollows: All h ee implemen a ions a e in oduced in he
ollowing Sec .2. Sec ion3p esen s he gene al amewo k used in he compu a ional s udy,
in which all h ee implemen a ions a e e alua ed on benchma k ins ances (Sec . 4). The pape
closes wi h a conclusion (Sec .5).
2 Implemen a ion o neighbo hoods
In his sec ion, we p esen he h ee implemen a ions s anda d,ND,ande icien ND o
implemen he inse ion and he swap neighbo hood.
2.1 S anda d implemen a ion
In he s anda d implemen a ion, simply all solu ions o he neighbo hoods a e e alua ed.
The eby, a solu ion is encoded by pa ame e s yiand addi ionally by se s Ig={i∈I:
yi=g},g∈G, i.e. Igis he se o i ems assigned o g oup gin he cu en solu ion. The
pseudo-code o he inse ion neighbo hood can be ound in Algo i hm 1.
Algo i hm 1 [s anda d inse ion]
1: Le a solu ion y be gi en.
2: o all g∈G:lg<|Ig|do
3: o all g∈G:g= g∧|Ig|<ugdo
4: o all i∈Igdo
5: E alua e inse o i in g oup gand sa e i i i is he bes ound so a .
6: end o
7: end o
8: end o
9: Realize bes inse i one imp o ing he objec i e alue o y was ound.
By using Ig, we only once ha e he check o each pai o g oups whe he hey a e iden ical
(Line 3). O en au ho s eplace he h ee o -loops s a ing in Lines 2–4by a o -loop o e
all i ems, a o -loop o e all g oups, and an i -s a emen checking whe he he i em is in
he g oup o no . Thus, he i -check needs o be done |I|·|G| imes while in he abo e
implemen a ion he check in Line 3is only done |G|2 imes, whe ea |G|<< |I|holds
ypically. We use his implemen a ion o Algo i hms 1and 2(swap neighbo hood) also
o ensu e ha he neighbo hoods a e always e alua ed in he exac same way in he h ee
di e en implemen a ions p esen ed in his pape . By his, we ensu e ha he sea ch is he
same o all h ee implemen a ions. Thus, i one implemen a ion leads o a highe numbe o
123
1250 Annals o Ope a ions Resea ch (2024) 341:1247–1265
ope a ed i e a ions due o i s mo e e icien implemen a ion, he bes ound solu ion canno
be wo se han he bes one ound wi h he o he wo implemen a ions.
Algo i hm 2p esen s he pseudo-code o a ull e alua ion o he swap neighbo hood.
Algo i hm 2 [s anda d swap]
1: Le a solu ion y be gi en.
2: o all g∈Gdo
3: o all g∈G:g>gdo
4: o all i∈Igdo
5: o all j∈Igdo
6: E alua e swap o i ems i and j, i.e. eassign i em i o g oup gand
i em j o g oup g and sa e i i i is he bes ound swap so a .
7: end o
8: end o
9: end o
10: end o
11: Realize bes swap i one imp o ing he objec i e alue o y was ound.
I is well-known in he li e a u e (see e.g. B imbe g e al. (2015)) ha inse s and swaps
can be e alua ed e ec i ely by using ma ix (Dig)i∈I,g∈Gwi h
Dig =
j∈Ig
dij
which indica es he sum o di e si ies o i em iwi h all i ems assigned o g oup g.By his, he
change in he objec i e alue due o a mo e o i em i om g oup g o g oup gcan di ec ly
be compu ed as
Dig−Dig.(5)
Fo a swap o he g oups o i ems iand jcu en ly assigned o g oups gand gwe ob ain
he change in he objec i e alue by
Dig−Dig +Djg −Djg−2·dij.(6)
As dij is included in Digand Djg,bu iis emo ed om gand jis emo ed om g,we
ha e o sub ac dij wice. A e ealizing an inse o a swap Dig needs o be upda ed o
all i ems and he in ol ed wo g oups gand gby sub ac ing he di e si y wi h he emo ed
i em and adding he di e si y wi h he added i em.
2.2 Neighbo hood decomposi ion implemen a ion
Laie al.(2021a) ecognized ha i is no necessa y o e alua e he en i e neighbo hood in
e e y i e a ion. In e e y i e a ion, he assignmen o only wo g oups is changed. Thus, i
we ound ou ha he e is no p omising inse o an i em om g oup gin o g oup go no
p omising swap be ween i ems o g oups gand g, we do no need o e alua e hese inse s
o swaps again un il a leas one o he wo g oups is changed by emo ing o adding an i em.
As e alua ing all inse s o i ems o g oup gin o g oup go all swaps be ween i ems
o g oups gand gis independen o he e alua ion o all inse s/swaps o all o he g oup
pai s, Lai e al. (2021a) call he pa o he neighbo hood con aining hese inse s/swaps he
neighbo hood block o g oups gand g. No e ha he neighbo hood block o gand gis
123

Annals o Ope a ions Resea ch (2024) 341:1247–1265 1251
iden ical o he one o gand g o he swap neighbo hood, bu he e is a di e ence o he
inse ion neighbo hood. In bo h cases, all neighbo hood blocks g,g∈G( o swap wi h
g<g) a e disjunc and hei union is he en i e neighbo hood.
Laie al.(2021a) in oduced wo ze o–one ma ices W1=(W1
gg)g,g∈Gand W2=
(W2
gg)g,g∈G o pic u e whe he he neighbo hood block including g oups gand gneeds o
be e alua ed. I an en y o he ma ices is 1, he inse s/swaps be ween he co esponding
g oups need o be e alua ed. I an en y is 0, he neighbo hood block can be skipped, as we
know al eady ha i does no con ain any p omising inse /swap.
No e ha W2is symme ic while W1is no . I migh be ha he e is no p omising inse
o an elemen o g oup gin o g oup g, bu he e is one in he opposi e di ec ion. I an i em
is added o o emo ed om a g oup g,W1
gg,W1
gg,W2
gg,andW2
gga e se o 1 o all
g∈G {g}, i.e. hey ha e o be e-e alua ed (las line o Algo i hm 3and 4, espec i ely).
Laie al.(2021a) call he p ocedu e neighbo hood decomposi ion, as he neighbo hoods
a e decomposed o each pai o g oups g,g∈Gin o one independen block (swap) and
wo independen blocks (inse ), espec i ely. We w i e o sho ND ins ead o neighbo hood
decomposi ion in he ollowing. The pseudo-code o he inse ion and he swap neighbo hood
using he ND implemen a ion a e p esen ed in Algo i hms 3and 4, espec i ely.
Algo i hm 3 [ND inse ion]
1: Le a solu ion y be gi en.
2: o all g∈G:lg<|Ig|do
3: o all g∈G:g= g∧|Ig|<ugdo
4: i W1
gg=1 hen
5: W1
gg=0
6: o all i∈Igdo
7: E alua e inse o i in g oup g, sa e i i i is he bes ound so a ,
and se W1
gg=1i i imp o es he objec i e alue o y.
8: end o
9: end i
10: end o
11: end o
12: Realize bes inse i one imp o ing he objec i e alue o y was ound.
13: Upda e ma ices W1and W2i an inse was ealized.
Algo i hm 4 [ND swap]
1: Le a solu ion y be gi en.
2: o all g∈Gdo
3: o all g∈G:g>gdo
4: i W2
gg=1 hen
5: W2
gg=0
6: o all i∈Igdo
7: o all j∈Igdo
8: E alua e swap o i ems i and j, i.e. eassign i em i o g oup g
i em j o g oup g, sa e i i i is he bes ound swap so a , and
se W2
gg=1i i imp o es he objec i e alue o y.
9: end o
10: end o
11: end i
12: end o
123
1252 Annals o Ope a ions Resea ch (2024) 341:1247–1265
13: end o
14: Realize bes swap i one imp o ing he objec i e alue o y was ound.
15: Upda e ma ices W1and W2i an inse was ealized.
I can clea ly be seen ha he neighbo hoods can be e alua ed mo e e icien ly han in he
s anda d implemen a ion i he block o a g oup pai gand gdoes no need o be e alua ed
(Line 4 in bo h algo i hms). Howe e , he bene i depends on he numbe o blocks which can
be skipped. In con as , he e is he d awback ha ma ices W1and W2need o be upda ed
a e e e y change in he solu ion (Lines 13 and 15, espec i ely) al hough his equi es
only a linea e o (W1
g¯g,W1
¯gg,W2
g¯g,W2
¯gg,W1
g¯g,W1
¯gg,W2
g¯g,andW2
¯gga e se o 1 o all
¯g∈G {g,g}whe ea gand ga e he wo g oups wi h emo ed/added i ems).
Mo eo e , he app oach s ill has he disad an age ha a block is e alua ed in an i e a ion
and again in he nex i e a ion i he e is a p omising inse /swap, bu ano he one comp ising
wo o he g oups was ealized.
2.3 E icien neighbo hood decomposi ion implemen a ion
We p esen now an imp o ed e sion o o e come his d awback. The e o e, we eplace
ma ices W1and W2by new h ee-dimensional ma ices M1=(M1
ggh)g,g∈G,h=1,2and
M2=(M2
ggh)g,g∈G,h=1,2,3, espec i ely. Fo each pai o g oups gand gwe e alua e all
inse so ani emo g oupgin o g oup g(analogously o conduc Lines 6–8 o Algo i hm
3). I he e is a p omising one, we sa e he change in he objec i e unc ion o he bes one i
he inse would be conduc ed in M1
gg1( alue o (5)) and he co esponding i em numbe iin
M1
gg2. I he e is no p omising inse , we simply se M1
gg1=M1
gg2=0. Thus, M1gi es us
he bes inse o an i em o g oup gin o g oup gi he e is one such ha he neighbo hood
e alua ion educes as can be seen in Lines 8–10 o Algo i hm 5.
Algo i hm 5 [e icien ND inse ion]
1: Le a solu ion y be gi en.
2: max =0.
3: o all g∈G:lg<|Ig|do
4: o all g∈G:g= g∧|Ig|<ugdo
5: i M1
gg1<0 hen
6: E alua e all inse s o i ems o g oup g in o g oup gand sa e he bes
ound in M1
gg1and M1
gg2.
7: end i
8: i M1
gg1>max hen
9: max =M1
gg1and i =M1
gg2.
10: end i
11: end o
12: end o
13: Realize bes inse i max >0, i.e. inse i em i in g oup g.
14: Upda e ma ices M1and M2i an inse was ealized.
Whene e a change occu s in g oups go g, we need o upda e M1
gghand M1
ggh
analogously o he ND me hod. We simply se M1
gg1=M1
gg1=−1 indica ing ha he
neighbo hood block con aining g oups gand gneeds o be e-e alua ed (Line 14 o Algo-
i hm 5). We canno se M1
gg1and M1
gg1 o 0, as 0 indica es ha he neighbo hood block
123
Annals o Ope a ions Resea ch (2024) 341:1247–1265 1253
has been e alua ed, bu no p omising inse was ound. Ma ix M2is upda ed analogously. I
M1
gg1=−1, all inse s o i ems o g oup gin o g oup ga e e alua ed and he bes p omising
one is again sa ed in M1
gg1,M1
gg2,andM1
gg3(Lines 5–7).
As we can eplace Lines 4–9 o Algo i hm 3by Lines 5–10 o Algo i hm 5, e alua ing
he neighbo hood is mo e e icien now. We only need o e alua e neighbo hood blocks
which ha e no been e alua ed since he las change in hei g oup assignmen (Line 5), bu
hese neighbo hood blocks would also be e alua ed in he ND implemen a ion. Addi ionally,
u he p omising neighbo hood blocks migh be e-e alua ed in he ND implemen a ion bu
a e no in he e icien ND implemen a ion.
Fo he swap neighbo hood we analogously sa e he alue he objec i e unc ion changes
in en y M2
gg1( alue o (6)) and he i em i emo ed om g oup gin en y M2
gg2. Addi ionally,
we sa e he i em j emo ed om g oup gin en y M2
gg3. Again, all h ee en ies a e 0 i
he e is no p omising swap be ween g oups gand gand M2
gg1=−1 i he neighbo hood
block has no been e alua ed since he las change in he assigned i ems o g oup go g.The
swap neighbo hood can hen be e alua ed by Algo i hm 6.
Algo i hm 6 [e icien ND swap]
1: Le a solu ion y be gi en.
2: max =0.
3: o all g∈Gdo
4: o all g∈G:g>gdo
5: i M2
gg1<0 hen
6: E alua e all pai wise swaps o i ems o g oup g wi h i ems o g oup gand
sa e he bes ound in M2
gg1,M
2
gg2, and M2
gg3.
7: end i
8: i M2
gg1>max hen
9: max =M2
gg1,i =M2
gg2, and j =M2
gg3.
10: end i
11: end o
12: end o
13: Realize bes swap i max >0, i.e. inse i em i in g oup gand i em j in g oup g.
14: Upda e ma ices M1and M2i a swap was ealized.
2.4 Compa ison o he h ee implemen a ions
Compa ing he h ee implemen a ions, he s anda d implemen a ion ully e alua es he neigh-
bo hoods in e e y i e a ion. The ND implemen a ion sa es some compu a ions by e alua ing
only hose pa s which migh be p omising bu always e alua es a neighbo hood block i
any hing has changed in he assignmen o one o he wo in ol ed g oups. The e icien ND
implemen a ion sa es he bes inse /swap which can be ealized be ween wo g oups such
ha he neighbo hood block only needs o be e-e alua ed i any hing changes in one o he
wo g oups. In o he wo ds, e e y pa o he neighbo hood which needs o be e alua ed in he
e icien ND implemen a ion needs also o be e alua ed in he ND implemen a ion and e e y
pa o he neighbo hood which needs o be e alua ed in he ND implemen a ion needs o be
e alua ed in he s anda d implemen a ion. Thus, we ha e a clea hie a chy in he e iciency
o he implemen a ions.
Conc e ely, we need o e alua e |I|·(|G|−1)=(|I1|+...|I|G||)·(|G|−1)inse s in he
s anda d implemen a ion while we only need o e alua e up o (|Ig1|+|Ig2|)·(|G|−1)inse s
123
1254 Annals o Ope a ions Resea ch (2024) 341:1247–1265
in he e icien ND implemen a ion whe ea g1and g2a e he wo g oups which we e changed
by an inse /swap in he p e ious i e a ion. All i ems o hese wo g oups (|Ig1|+|Ig2|) need
o be einse ed in o all emaining |G|−1 g oups. I can clea ly be seen ha he e icien
ND implemen a ion equi es ewe e alua ed inse s han he s anda d implemen a ion i
|G|>2 while he di e ence is he la ge he la ge |G|is. The ND implemen a ion is in he
bes case as e icien as he e icien ND implemen a ion, bu in he wo s case as ine icien
as he s anda d implemen a ion.
I he swap neighbo hood is conside ed, we need o e alua e g∈G|Ig|·(|I| |Ig|)/2
swaps in he s anda d implemen a ion, i.e. o e e y i em o a g oup (|Ig|) he swap wi h
any i em assigned o ano he g oup (|I| |Ig|). As he swap o wo i ems only needs o be
e alua ed once, we di ide he esul by wo. In he e icien ND implemen a ion, we only need
o upda e swaps o he i ems assigned o a g oup gwi h he i ems assigned o all o he g oups
i g oup gwas changed in he p e ious i e a ion. As in one i e a ion a mos wo g oups g1
and g2a e changed, we need o e alua e a mos g∈{g1,g2}|Ig|·(|I| |Ig|)−|Ig1|·|Ig2|
swaps whe ea |Ig1|·|Ig2|sub ac s he swaps be ween he wo g oups g1and g2which
a e o he wise coun ed wice. Again, he e icien ND implemen a ion is mo e e icien han
he s anda d implemen a ion i |G|>2 and he di e ence is he la ge he la ge |G|is.
Mo eo e , he ND implemen a ion is again in he bes case as e icien as he e icien ND
implemen a ion, bu in he wo s case as ine icien as he s anda d implemen a ion.
The di e ence is e en clea e i one o he neighbou hoods is called wi hou ha ing any
change in he g oup assignmen since he las call o he algo i hm. Then, ma ices M1and
M2, espec i ely, a e up o da e such ha he e icien ND implemen a ion does no need o
e-e alua e any pa o he neighbo hood. I only has an e o o up o |G|·(|G|−1) o ind
he bes neighbou ing solu ion. This is clea ly less e o han in he s anda d implemen a ion
equi ing |I|·(|G|−1) o he inse ion neighbo hood and |I|2 o he swap neighbo hood.
We a e ce ainly in his si ua ion i we a e in a local op imum o bo h neighbo hoods. Then,
we need o e-e alua e bo h neighbo hoods be o e we know ha we a e in a local op imum,
bu o he one leading o he local op imal solu ion no hing has changed since he las call.
O cou se we do no wan o s ay in a local op imum. To no s ick he e, we in oduce a
a iable neighbo hood sea ch (VNS) based amewo k wi h pe u ba ion in he nex sec ion
which is used o e alua e he in oduced neighbo hood implemen a ions in he compu a ional
s udy.
3 Va iable neighbo hood sea ch amewo k
Be o e we in oduce he o e all amewo k we i s in oduce he used pe u ba ion me hods
o a oid s icking in local op imal solu ions. We use he weak and s ong pe u ba ion me hod
p esen ed in Lai and Hao (2016). They a e p esen ed in Algo i hms 7and 8. As in Lai and Hao
(2016)wese ηw=3andηs=·|I|/|G|, whe ea =1i |I|≤400 and 1.5 o he wise.
In Algo i hm 7, we de e mine 5 solu ions in he o -loop s a ing in Line 4. Lai and Hao
(2016) de e mined |I|solu ions in he o -loop. Howe e , in ou p elimina y e alua ions his
esul ed in a e y signi ican ime spen o he weak pe u ba ion. The e o e, we dec eased
he alue such ha he algo i hm spends much mo e ime o he neighbo hood e alua ion
and we can pe o m clea ly mo e i e a ions.
Algo i hm 7 [Weak pe u ba ion]
1: Le a solu ion y be gi en.
2: o all n=1 o ηwdo
123
Annals o Ope a ions Resea ch (2024) 341:1247–1265 1261
Table 2 con inued Skipped block e alua ions [%]
Ins ance ype W1W2M1M2
RanReal_n120_ds 38.75 42.40 40.35 47.41
RanReal_n120_ss – 50.50 – 61.67
RanReal_n240_ds 43.89 45.80 46.94 53.49
RanReal_n240_ss – 50.41 – 67.14
RanReal_n480_ds 59.33 59.95 63.95 69.52
RanReal_n480_ss – 59.17 – 78.80
RanReal_n960_ds 64.23 60.64 70.69 74.76
RanReal_n960_ss – 55.05 – 82.39
I we use he ND implemen a ion, we mo eo e need o e alua e all o he o he s i he e is
a p omising inse /swap. Consequen ly, he sha e o skipped block e alua ions inc eases o
mo e han 82% o he swap neighbo hood and o e 70% o he inse ion neighbo hood i
we use he e icien ND implemen a ion.
The alues a e smalle i he swap as well as he inse ion neighbo hood a e used, i.e.
o he ins ances wi h unequal-sized g oups. One eason is ha bo h neighbo hoods a e
e alua ed al e na ely. Thus, up o ou g oups we e changed ins ead o up o wo be o e he
same neighbo hood is e alua ed nex (can be mo e i pe u ba ion is execu ed meanwhile).
Table 3shows he success a es o he wo neighbo hoods as well as he a e age numbe o
i e a ions be ween wo consecu i e calls o he pe u ba ion algo i hms 7and 8, espec i ely.
The success a e is he pe cen age o calls o he neighbo hood in which an imp o ed solu ion
was ound. I is no su p ising ha mo e i e a ions we e pe o med be o e he algo i hm
eaches a local op imum, i.e. pe u ba ion is equi ed, i he ins ance size is la ge . Thus,
he success a es o bo h neighbo hoods inc ease wi h he ins ance size. Especially he swap
neighbo hood wi h a success a e o up o 91% is e y e ec i e.
The inse ion neighbo hood eaches a success a e o only abou 50%. Thus, he e a e
mo e i e a ions wi hou any change in he cu en solu ion which explains why he ND
implemen a ion is mo e e ec i e o ins ances wi h unequal g oup sizes. I an i e a ion is
unsuccess ul, no p omising neighbo hood block exis s. This also means ha in he nex call
o he inse ion neighbo hood only hose neighbou hood blocks need o be e alua ed which
we e changed due o a swap in he swap neighbo hood which was called in he mean ime.
Thus, ND is as e ec i e as e icien ND and clea ly supe io o s anda d in his case. Ou
implemen a ion wi h he al e na e calls o bo h neighbo hoods ollows Lai and Hao (2016).
The small success a e o he inse ion neighbo hood, howe e , migh be an a gumen o
ollow ano he policy in u u e app oaches.
5 Conclusion
The pape compa es he h ee implemen a ions called s anda d,ND,ande icien ND o he
inse ion and he swap neighbo hood o he MDGP. The e icien ND implemen a ion is
newly in oduced and based on he ND implemen a ion. Bo h implemen a ions use he idea
ha he neighbo hoods can be di ided in o independen blocks con aining he inse s/swaps
be ween wo g oups. While he ND implemen a ion e alua es a block i he e is a p omising,
123

1262 Annals o Ope a ions Resea ch (2024) 341:1247–1265
Table 3 E alua ion o algo i hm design
Success a e Success a e Pe u ba ion (no. i .)
Ins ance ype Inse ion [%] Swap [%] Weak S ong
Geo_n010_ds 3.41 60.42 5.1 32.9
Geo_n010_ss – 41.77 3.4 22.6
Geo_n012_ds 19.29 70.48 6.9 51.2
Geo_n012_ss – 58.42 4.8 32.8
Geo_n030_ds 13.53 80.92 10.5 95.0
Geo_n030_ss – 72.06 7.2 69.7
Geo_n060_ds 19.86 82.75 11.7 101.4
Geo_n060_ss – 74.49 7.8 75.4
Geo_n120_ds 21.25 85.59 14.0 104.0
Geo_n120_ss – 78.81 9.4 77.9
Geo_n240_ds 18.32 89.83 19.8 143.6
Geo_n240_ss – 83.96 12.5 89.9
Geo_n480_ds 17.61 93.61 31.4 134.4
Geo_n480_ss – 90.43 20.9 86.2
Geo_n960_ds 13.43 96.77 62.0 276.7
Geo_n960_ss – 95.08 40.7 170.9
RanIn _n010_ds 18.88 54.95 4.8 31.4
RanIn _n010_ss – 43.59 3.5 21.7
RanIn _n012_ds 32.06 63.80 6.1 47.5
RanIn _n012_ss – 56.00 4.5 30.8
RanIn _n030_ds 38.54 74.29 8.5 72.0
RanIn _n030_ss – 69.37 6.5 57.1
RanIn _n060_ds 45.67 76.91 9.3 74.6
RanIn _n060_ss – 72.29 7.2 55.9
RanIn _n120_ds 46.63 78.78 10.1 74.4
RanIn _n120_ss – 74.29 7.8 51.5
RanIn _n240_ds 52.38 81.73 11.8 87.1
RanIn _n240_ss – 78.84 9.5 59.4
RanIn _n480_ds 51.82 87.45 17.0 76.2
RanIn _n480_ss – 84.14 12.6 51.0
RanIn _n960_ds 51.09 91.39 24.5 110.6
RanIn _n960_ss – 88.78 17.8 71.8
RanReal_n010_ds 17.83 53.61 4.7 31.2
RanReal_n010_ss – 42.79 3.5 21.8
RanReal_n012_ds 27.78 65.44 6.1 48.4
RanReal_n012_ss – 55.33 4.5 30.6
RanReal_n030_ds 39.00 74.17 8.5 71.1
123
Annals o Ope a ions Resea ch (2024) 341:1247–1265 1263
Table 3 con inued
Success a e Success a e Pe u ba ion (no. i .)
Ins ance ype Inse ion [%] Swap [%] Weak S ong
RanReal_n030_ss – 69.35 6.5 56.4
RanReal_n060_ds 45.06 77.13 9.4 75.0
RanReal_n060_ss – 72.34 7.2 56.0
RanReal_n120_ds 46.86 78.76 10.1 74.5
RanReal_n120_ss – 74.30 7.8 51.4
RanReal_n240_ds 52.06 81.82 11.9 87.2
RanReal_n240_ss – 78.87 9.5 59.5
RanReal_n480_ds 51.68 87.49 17.0 76.4
RanReal_n480_ss – 84.14 12.6 51.0
RanReal_n960_ds 50.78 91.43 24.6 111.0
RanReal_n960_ss – 88.79 17.8 71.8
i.e. an imp o ing inse /swap, he e icien ND implemen a ion e alua es each block only i
he assignmen o a leas one o i s g oups has changed.
All h ee neighbo hood implemen a ions we e compa ed in an ex ensi e compu a ional
s udy on he classical benchma k se s. The esul s show ha he s anda d implemen a ion is
supe io o small ins ance sizes while he e icien ND implemen a ion is supe io o la ge
ins ance sizes. The ND implemen a ion pe o med bes o medium sized ins ances wi h
unequal g oup sizes. A eason o i is ha he inse ion neighbo hood ound only in a ound
hal o he cases an imp o ed solu ion. Fo he la ge ins ances he e icien ND implemen a ion
could pe o m up o 160% mo e i e a ions in compa ison o s anda d and up o 76% mo e
i e a ions in compa ison o ND.
Ou esul s lead o se e al di ec ions o u u e esea ch. Fi s , he new neighbo hood
implemen a ion can be used o o he g ouping o clus e ing p oblems. These include as men-
ioned in he in oduc ion p oblems like he capaci a ed clus e ing p oblem o he capaci a ed
p-median p oblem as well as he a io cu and no malized cu g aph pa i ioning p oblem,
ehicle ou ing p oblems, o pa allel machine scheduling (Yalaoui & Chu, 2002). Second, we
ound ha he inse ion neighbo hood has a success a e o only abou 50% i bo h neighbo -
hoods, inse ion and swap, a e called al e na ely. Fu u e esea ch could e alua e o he policies
o inc ease he neighbo hoods’ success a es. Finally, u u e esea ch can ex end ou app oach
by using he ma ices M1and M2 o de e mine mo e han one p omising inse /swap pe
i e a ion. The ma ices indica e he bes inse /swap be ween wo g oups. As long as g oup
pai s a e disjunc one could also ealize addi ional neighbo hood mo es in he same i e a ion.
The bes selec ion can be de e mined by a maximum weigh ed ma ching.
Funding Open Access unding enabled and o ganized by P ojek DEAL. No unding was ecei ed o con-
duc ing his s udy.
Decla a ion
Con lic o in e es The au ho has no Con lic o in e es o decla e ha a e ele an o he con en o his
a icle.
123
1264 Annals o Ope a ions Resea ch (2024) 341:1247–1265
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included in he
a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I ma e ial is
no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by s a u o y
egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde .
To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
Bake , B. M., & Benn, C. (2001). Assigning pupils o u o g oups in a comp ehensi e school. Jou nal o he
Ope a ional Resea ch Socie y, 52(6), 623–629.
Bake , K. R., & Powell, S. G. (2002). Me hods o assigning s uden s o g oups: A s udy o al e na i e objec i e
unc ions. Jou nal o he Ope a ional Resea ch Socie y, 53, 397–404.
Ba is a, R. M., Mao, E., & Sussman, A. B. (2023). Keeping cash and e ol ing deb : Examining co-holding
in he ield and in he lab. A ailable a SSRN 4558490
Behesh ian-A dekani, M., & Mahmood, M. A. (1986). Educa ion de elopmen and alida ion o a ool o
assigning s uden s o g oups o class p ojec s. Decision Sciences, 17(1), 92–113.
B imbe g, J., Mladeno i´c, N., & U oše i´c, D. (2015). Sol ing he maximally di e se g ouping p oblem by
skewed gene al a iable neighbo hood sea ch. In o ma ion Sciences, 295, 650–675.
B usco, M. J., C adi , J. D., & S einley, D. (2020). Combining di e si y and dispe sion c i e ia o an iclus e ing:
A bic i e ion app oach. B i ish Jou nal o Ma hema ical and S a is ical Psychology, 73(3), 375–396.
Chen, Y., Fan, Z. P., Ma, J., & Zeng, S. (2011). A hyb id g ouping gene ic algo i hm o e iewe g oup
cons uc ion p oblem. Expe Sys ems wi h Applica ions, 38(3), 2401–2411.
Dias, T. G., & Bo ges, J. (2017). A new algo i hm o c ea e balanced eams p omo ing mo e di e si y. Eu opean
Jou nal o Enginee ing Educa ion, 42(6), 1365–1377.
Fan, Z. P., Chen, Y., Ma, J., & Zeng, S. (2011). E a um: A hyb id gene ic algo i hmic app oach o he
maximally di e se g ouping p oblem. Jou nal o he Ope a ional Resea ch Socie y, 62(7), 1423–1430.
Feo, T. A., & Khella , M. (1990). A class o bounded app oxima ion algo i hms o g aph pa i ioning. Ne -
wo ks, 20(2), 181–195.
Gallego, M., Laguna, M., Ma í, R., & Dua e, A. (2013). Tabu sea ch wi h s a egic oscilla ion o he
maximally di e se g ouping p oblem. Jou nal o he Ope a ional Resea ch Socie y, 64(5), 724–734.
Lai, X., & Hao, J. K. (2016). I e a ed maxima sea ch o he maximally di e se g ouping p oblem. Eu opean
Jou nal o Ope a ional Resea ch, 254(3), 780–800.
Lai, X., Hao, J. K., Fu, Z. H., & Yue, D. (2021). Neighbo hood decomposi ion based a iable neighbo hood
sea ch and abu sea ch o maximally di e se g ouping. Eu opean Jou nal o Ope a ional Resea ch,
289(3), 1067–1086.
Lai, X., Hao, J. K., Fu, Z. H., & Yue, D. (2021). Neighbo hood decomposi ion-d i en a iable neighbo hood
sea ch o capaci a ed clus e ing. Compu e s & Ope a ions Resea ch, 134, 105362.
Minge s, J., & O’B ien, F. A. (1995). C ea ing s uden g oups wi h simila cha ac e is ics: A heu is ic app oach.
Omega, 23(3), 313–321.
Palubeckis, G. (2022). Me aheu is ic app oaches o a io cu and no malized cu g aph pa i ioning. Meme ic
Compu ing, 14(3), 253–285.
Palubeckis, G., Ka ˇciauskas, E., & Riškus, A. (2011). Compa a i e pe o mance o h ee me aheu is ic
app oaches o he maximally di e se g ouping p oblem. In o ma ion Technology and Con ol, 40(4),
277–285.
Palubeckis, G., Os eika, A., & Rubliauskas, D. (2015). Maximally di e se g ouping: An i e a ed abu sea ch
app oach. Jou nal o he Ope a ional Resea ch Socie y, 66(4), 579–592.
Papenbe g, M. (2024). K-plus an iclus e ing: An imp o ed k-means c i e ion o maximizing be ween-g oup
simila i y. B i ish Jou nal o Ma hema ical and S a is ical Psychology, 77(1), 80–102.
Papenbe g, M., & Klau, G. W. (2021). Using an iclus e ing o pa i ion da a se s in o equi alen pa s. Psy-
chological Me hods, 26(2), 161.
P ei e , C., & Schulz, A. (2022). An alns algo i hm o he s a ic dial-a- ide p oblem wi h ide and wai ing
ime minimiza ion. OR Spec um, 44(1), 87–119.
Rod iguez, F. J., Lozano, M., Ga cía-Ma ínez, C., & González-Ba e a, J. D. (2013). An a i icial bee colony
algo i hm o he maximally di e se g ouping p oblem. In o ma ion Sciences, 230, 183–196.
Rubin, P. A., & Bai, L. (2015). Fo ming compe i i ely balanced eams. IIE T ansac ions, 47(6), 620–633.
123
Annals o Ope a ions Resea ch (2024) 341:1247–1265 1265
Schulz, A. (2021). The balanced maximally di e se g ouping p oblem wi h block cons ain s. Eu opean
Jou nal o Ope a ional Resea ch, 294(1), 42–53.
Schulz, A. (2022). A new mixed-in ege p og amming o mula ion o he maximally di e se g ouping p oblem
wi h a ibu e alues. Annals o Ope a ions Resea ch, 318(1), 501–530.
Schulz, A. (2023). The balanced maximally di e se g ouping p oblem wi h a ibu e alues. Disc e e Applied
Ma hema ics, 335, 82–103.
U oše i´c, D. (2014). Va iable neighbo hood sea ch o maximum di e se g ouping p oblem. Yugosla Jou nal
o Ope a ions Resea ch, 24(1), 21–33.
Wei z, R. R., & Lakshmina ayanan, S. (1998). An empi ical compa ison o heu is ic me hods o c ea ing
maximally di e se g oups. Jou nal o he Ope a ional Resea ch Socie y, 49(6), 635–646.
Yalaoui, F., & Chu, C. (2002). Pa allel machine scheduling o minimize o al a diness. In e na ional Jou nal
o P oduc ion Economics, 76(3), 265–279.
Yang, X., Cai, Z., Jin, T., Tang, Z., & Gao, S. (2022). A h ee-phase sea ch app oach wi h dynamic popula ion
size o sol ing he maximally di e se g ouping p oblem. Eu opean Jou nal o Ope a ional Resea ch,
302(3), 925–953.
Zheng, S., Lai, X., & Gong, W. (2021). Neighbo hood decomposi ion based a iable neighbo hood sea ch o
he capaci a ed p-median p oblem. In: 2021 China Au oma ion Cong ess (CAC), IEEE, pp. 1101–1105
Zhou, Y., Kou, Y., & Zhou, M. (2023). Bile el meme ic sea ch app oach o he so -clus e ed ehicle ou ing
p oblem. T anspo a ion Science, 57(3), 701–716.
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps and
ins i u ional a ilia ions.
123