Efficient neighborhood evaluation for the maximally diverse grouping problem

Schulz, Arne Article — Published Version Efficient neighborhood evaluation for the maximally diverse grouping problem Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Schulz, Arne (2024) : Efficient neighborhood evaluation for the maximally diverse grouping problem, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 341, Iss. 2, pp. 1247-1265, https://doi.org/10.1007/s10479-024-06217-9 This Version is available at: https://hdl.handle.net/10419/315283 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Annals of Operations Research (2024) 341:1247–1265 https://doi.org/10.1007/s10479-024-06217-9 ORIGINAL-COMPARATIVE COMPUTATIONAL STUDY Efficient neighborhood evaluation for the maximally diverse grouping problem Arne Schulz1,2 Received: 23 October 2023 / Accepted: 5 August 2024 / Published online: 21 August 2024 © The Author(s) 2024 Abstract The Maximally Diverse Grouping Problem is one of the well-known combinatorial optimization problems with applications in the assignment of students to groups or courses. Due to its NP-hardness several (meta)heuristic solution approaches have been presented in the literature. Most of them include the insertion of an item of one group into another group and the swap of two items currently assigned to different groups as neighborhoods. The paper presents a new efficient implementation for both neighborhoods and compares it with the standard implementation, in which all inserts/swaps are evaluated, as well as the neighborhood decomposition approach. The results show that the newly presented approach is clearly superior for larger instances allowing for up to 160% more iterations in comparison to the standard implementation and up to 76% more iterations in comparison to the neighborhood decomposition approach. Moreover, the results can also be used for (meta)heuristic algorithms for other grouping or clustering problems. Keywords Combinatorial optimization ·Grouping ·Local search ·Computational efficiency 1 Introduction The Maximally Diverse Grouping Problem (MDGP) is a well-known and well-investigated combinatorial optimization problem. Given a set of items i∈Iwith a pairwise diversity dij ≥0, the task is to assign the items to groups g∈Gsuch that each group ggets at least lg and at most ugitems assigned and the within group diversity is maximized over all groups. The MDGP is an important combinatorial optimization problem for two reasons: First, it has a wide field of applications such as the assignment of students to project groups (BeheshtianArdekani & Mahmood, 1986) or teams (Dias & Borges, 2017), the assignment of pupils to tutor groups (Baker & Benn, 2001) or of children to equally strong sport teams (Rubin & Bai, 2015). Moreover, there are applications in final exam scheduling, VLSI design (Weitz & Lakshminarayanan, 1998), and anticlustering. Anticlustering aims like the MDGP to partition BArne Schulz [email protected] ; [email protected] 1Institute of Operations Management, Universität Hamburg, Moorweidenstraße 18, 20148 Hamburg, Germany 2Institute of Quantitative Logistics, Helmut Schmidt University, Holstenhofweg 85, 22043 Hamburg, Germany 123 1248 Annals of Operations Research (2024) 341:1247–1265 items into disjoint groups such that groups are similar but within-group heterogeneity is high (Brusco et al., 2020; Papenberg, 2024). Applications are in the assignment of participants to groups (Batista et al., 2023) and in dividing data sets for cross validation (Papenberg & Klau, 2021). Second, the MDGP is NP-hard to solve (Feo & Khellaf, 1990) although it can be formulated as a short integer program, which can easily be linearized (compare e.g. (Gallego et al., 2013)): max  g∈G  i∈I  j∈I:j>i dijxigxjg with the constraints (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 the study by Gallego et al. (2013), only instances with up to 12 items could be solved to optimality. Given that dij values often have a certain structure in practice, e.g. they are the difference of attribute values (Schulz, 2021) or binary values (Mingers & O’Brien, 1995), instances of up to 30–70 items can be solved to proven optimality (Schulz, 2022). If at most two attributes are considered, Schulz (2021) proved that even large instances can be solved efficiently. However, if we want to solve large instances or instances with general dij ≥0(dii =0 for all i∈I), efficient heuristic solution methods are required. While earlier approaches focussed on construction and local search improvement heuristics (compare the overview by Weitz and Lakshminarayanan (1998)), later papers focussed on different metaheuristic solution approaches. In the last years, Brimberg et al. (2015) developed a skewed general variable neighborhood search, Palubeckis et al. (2015) an iterated tabu search approach, Lai and Hao (2016) an iterated maxima search heuristic, Lai et al. (2021a) a neighborhood decomposition based variable neighborhood search and tabu search, and Yang et al. (2022) a three-phase approach with a dynamic population size. These are the most recent and successful approaches. Please see Lai and Hao (2016) for a more depth review of metaheuristic solution approaches for the MDGP. The focus of the paper at hand is not to develop a new advanced metaheuristic solution approach but to consider the evaluation of neighborhoods, especially insertions and swaps, within these approaches. We present a new method to evaluate these neighborhoods more efficiently. In doing so, the paper is inspired by the neighborhood decomposition approach by Lai et al. (2021a). Given a feasible solution for the MDGP, i.e. an assignment of each item to exactly one group such that each group has a number of items between lgand ugassigned, the insertion neighborhood contains all feasible solutions such that exactly one item is assigned to a different group. Thus, given solution y, whereat yiindicates the group of item i, the neighborhood includes all solutions ¯ysuch that (2)–(4) are fulfilled and yi=¯yifor all but exactly one item i∈I. Correspondingly, the swap neighborhood of yincludes all solutions ¯ysuch that (2)–(4) are fulfilled, yi=¯yifor all items i∈I\{ j,j},¯yj=yj,and ¯yj=yj.Thesetwo neighborhoods are used in most of the advanced solution methods for the MDGP, including the five advanced algorithms mentioned before as well as for example Baker and Powell (2002), Chen et al. (2011), Fan et al. (2011), Palubeckis et al. (2011), Rodriguez et al. (2013), 123 Annals of Operations Research (2024) 341:1247–1265 1249 Uroševi´c(2014),andSchulz(2023). In the paper at hand, we present a new efficient method enhancing the neighborhood decomposition (ND) method described in Lai et al. (2021a)to evaluate the two neighborhoods faster than in the standard implementation, which simply evaluates the entire neighborhood, and the ND implementation. The presented neighborhood evaluation can also be applied to other grouping or clustering problems. These include clustering problems like the capacitated clustering problem (Lai et al., 2021b) and the capacitated p-median problem (Zheng et al., 2021). It can also be applied to the ratio cut and normalized cut graph partitioning problem (Palubeckis, 2022), to vehicle routing problems (e.g. Pfeiffer and Schulz (2022)orZhouetal.(2023)) or to parallel machine scheduling (Yalaoui & Chu, 2002). The paper is constructed as follows: All three implementations are introduced in the following Sect.2. Section3presents the general framework used in the computational study, in which all three implementations are evaluated on benchmark instances (Sect. 4). The paper closes with a conclusion (Sect.5). 2 Implementation of neighborhoods In this section, we present the three implementations standard,ND,andefficient ND to implement the insertion and the swap neighborhood. 2.1 Standard implementation In the standard implementation, simply all solutions of the neighborhoods are evaluated. Thereby, a solution is encoded by parameters yiand additionally by sets Ig={i∈I: yi=g},g∈G, i.e. Igis the set of items assigned to group gin the current solution. The pseudo-code for the insertion neighborhood can be found in Algorithm 1. Algorithm 1 [standard insertion] 1: Let a solution y be given. 2: for all g∈G:lg<|Ig|do 3: for all g∈G:g= g∧|Ig|<ugdo 4: for all i∈Igdo 5: Evaluate insert of i in group gand save it if it is the best found so far. 6: end for 7: end for 8: end for 9: Realize best insert if one improving the objective value of y was found. By using Ig, we only once have the check for each pair of groups whether they are identical (Line 3). Often authors replace the three for-loops starting in Lines 2–4by a for-loop over all items, a for-loop over all groups, and an if-statement checking whether the item is in the group or not. Thus, the if-check needs to be done |I|·|G|times while in the above implementation the check in Line 3is only done |G|2times, whereat |G|<< |I|holds typically. We use this implementation for Algorithms 1and 2(swap neighborhood) also to ensure that the neighborhoods are always evaluated in the exact same way in the three different implementations presented in this paper. By this, we ensure that the search is the same for all three implementations. Thus, if one implementation leads to a higher number of 123 1250 Annals of Operations Research (2024) 341:1247–1265 operated iterations due to its more efficient implementation, the best found solution cannot be worse than the best one found with the other two implementations. Algorithm 2presents the pseudo-code for a full evaluation of the swap neighborhood. Algorithm 2 [standard swap] 1: Let a solution y be given. 2: for all g∈Gdo 3: for all g∈G:g>gdo 4: for all i∈Igdo 5: for all j∈Igdo 6: Evaluate swap of items i and j, i.e. reassign item i to group gand item j to group g and save it if it is the best found swap so far. 7: end for 8: end for 9: end for 10: end for 11: Realize best swap if one improving the objective value of y was found. It is well-known in the literature (see e.g. Brimberg et al. (2015)) that inserts and swaps can be evaluated effectively by using matrix (Dig)i∈I,g∈Gwith Dig = j∈Ig dij which indicates the sum of diversities of item iwith all items assigned to group g.Bythis,the change in the objective value due to a move of item ifrom group gto group gcan directly be computed as Dig−Dig.(5) For a swap of the groups of items iand jcurrently assigned to groups gand gwe obtain the change in the objective value by Dig−Dig +Djg −Djg−2·dij.(6) As dij is included in Digand Djg,butiis removed from gand jis removed from g,we have to subtract dij twice. After realizing an insert or a swap Dig needs to be updated for all items and the involved two groups gand gby subtracting the diversity with the removed item and adding the diversity with the added item. 2.2 Neighborhood decomposition implementation Laietal.(2021a) recognized that it is not necessary to evaluate the entire neighborhood in every iteration. In every iteration, the assignment to only two groups is changed. Thus, if we found out that there is no promising insert of an item from group ginto group gor no promising swap between items of groups gand g, we do not need to evaluate these inserts or swaps again until at least one of the two groups is changed by removing or adding an item. As evaluating all inserts of items of group ginto group gor all swaps between items of groups gand gis independent of the evaluation of all inserts/swaps of all other group pairs, Lai et al. (2021a) call the part of the neighborhood containing these inserts/swaps the neighborhood block of groups gand g. Note that the neighborhood block of gand gis 123 Annals of Operations Research (2024) 341:1247–1265 1251 identical to the one of gand gfor the swap neighborhood, but there is a difference for the insertion neighborhood. In both cases, all neighborhood blocks g,g∈G(for swap with g<g) are disjunct and their union is the entire neighborhood. Laietal.(2021a) introduced two zero–one matrices W1=(W1 gg)g,g∈Gand W2= (W2 gg)g,g∈Gto picture whether the neighborhood block including groups gand gneeds to be evaluated. If an entry of the matrices is 1, the inserts/swaps between the corresponding groups need to be evaluated. If an entry is 0, the neighborhood block can be skipped, as we know already that it does not contain any promising insert/swap. Note that W2is symmetric while W1is not. It might be that there is no promising insert of an element of group ginto group g, but there is one in the opposite direction. If an item is added to or removed from a group g,W1 gg,W1 gg,W2 gg,andW2 ggare set to 1 for all g∈G\{g}, i.e. they have to be re-evaluated (last line of Algorithm 3and 4, respectively). Laietal.(2021a) call the procedure neighborhood decomposition, as the neighborhoods are decomposed for each pair of groups g,g∈Ginto one independent block (swap) and two independent blocks (insert), respectively. We write for short ND instead of neighborhood decomposition in the following. The pseudo-code for the insertion and the swap neighborhood using the ND implementation are presented in Algorithms 3and 4, respectively. Algorithm 3 [ND insertion] 1: Let a solution y be given. 2: for all g∈G:lg<|Ig|do 3: for all g∈G:g= g∧|Ig|<ugdo 4: if W1 gg=1then 5: W1 gg=0 6: for all i∈Igdo 7: Evaluate insert of i in group g, save it if it is the best found so far, and set W1 gg=1if it improves the objective value of y. 8: end for 9: end if 10: end for 11: end for 12: Realize best insert if one improving the objective value of y was found. 13: Update matrices W1and W2if an insert was realized. Algorithm 4 [ND swap] 1: Let a solution y be given. 2: for all g∈Gdo 3: for all g∈G:g>gdo 4: if W2 gg=1then 5: W2 gg=0 6: for all i∈Igdo 7: for all j∈Igdo 8: Evaluate swap of items i and j, i.e. reassign item i to group g item j to group g, save it if it is the best found swap so far, and set W2 gg=1if it improves the objective value of y. 9: end for 10: end for 11: end if 12: end for 123 1252 Annals of Operations Research (2024) 341:1247–1265 13: end for 14: Realize best swap if one improving the objective value of y was found. 15: Update matrices W1and W2if an insert was realized. It can clearly be seen that the neighborhoods can be evaluated more efficiently than in the standard implementation if the block of a group pair gand gdoes not need to be evaluated (Line 4 in both algorithms). However, the benefit depends on the number of blocks which can be skipped. In contrast, there is the drawback that matrices W1and W2need to be updated after every change in the solution (Lines 13 and 15, respectively) although this requires only a linear effort (W1 g¯g,W1 ¯gg,W2 g¯g,W2 ¯gg,W1 g¯g,W1 ¯gg,W2 g¯g,andW2 ¯ggare set to 1 for all ¯g∈G\{g,g}whereat gand gare the two groups with removed/added items). Moreover, the approach still has the disadvantage that a block is evaluated in an iteration and again in the next iteration if there is a promising insert/swap, but another one comprising two other groups was realized. 2.3 Efficient neighborhood decomposition implementation We present now an improved version to overcome this drawback. Therefore, we replace matrices W1and W2by new three-dimensional matrices M1=(M1 ggh)g,g∈G,h=1,2and M2=(M2 ggh)g,g∈G,h=1,2,3, respectively. For each pair of groups gand gwe evaluate all insertsofanitemofgroupginto group g(analogously to conduct Lines 6–8 of Algorithm 3). If there is a promising one, we save the change in the objective function for the best one if the insert would be conducted in M1 gg1(value of (5)) and the corresponding item number iin M1 gg2. If there is no promising insert, we simply set M1 gg1=M1 gg2=0. Thus, M1gives us the best insert of an item of group ginto group gif there is one such that the neighborhood evaluation reduces as can be seen in Lines 8–10 of Algorithm 5. Algorithm 5 [efficient ND insertion] 1: Let a solution y be given. 2: max =0. 3: for all g∈G:lg<|Ig|do 4: for all g∈G:g= g∧|Ig|<ugdo 5: if M1 gg1<0then 6: Evaluate all inserts of items of group g into group gand save the best found in M1 gg1and M1 gg2. 7: end if 8: if M1 gg1>max then 9: max =M1 gg1and i =M1 gg2. 10: end if 11: end for 12: end for 13: Realize best insert if max >0, i.e. insert item i in group g. 14: Update matrices M1and M2if an insert was realized. Whenever a change occurs in groups gor g, we need to update M1 gghand M1 ggh analogously to the ND method. We simply set M1 gg1=M1 gg1=−1 indicating that the neighborhood block containing groups gand gneeds to be re-evaluated (Line 14 of Algorithm 5). We cannot set M1 gg1and M1 gg1to 0, as 0 indicates that the neighborhood block 123 Annals of Operations Research (2024) 341:1247–1265 1253 has been evaluated, but no promising insert was found. Matrix M2is updated analogously. If M1 gg1=−1, all inserts of items of group ginto group gare evaluated and the best promising one is again saved in M1 gg1,M1 gg2,andM1 gg3(Lines 5–7). As we can replace Lines 4–9 of Algorithm 3by Lines 5–10 of Algorithm 5, evaluating the neighborhood is more efficient now. We only need to evaluate neighborhood blocks which have not been evaluated since the last change in their group assignment (Line 5), but these neighborhood blocks would also be evaluated in the ND implementation. Additionally, further promising neighborhood blocks might be re-evaluated in the ND implementation but are not in the efficient ND implementation. For the swap neighborhood we analogously save the value the objective function changes in entry M2 gg1(value of (6)) and the item iremoved from group gin entry M2 gg2. Additionally, we save the item jremoved from group gin entry M2 gg3. Again, all three entries are 0 if there is no promising swap between groups gand gand M2 gg1=−1 if the neighborhood block has not been evaluated since the last change in the assigned items to group gor g.The swap neighborhood can then be evaluated by Algorithm 6. Algorithm 6 [efficient ND swap] 1: Let a solution y be given. 2: max =0. 3: for all g∈Gdo 4: for all g∈G:g>gdo 5: if M2 gg1<0then 6: Evaluate all pairwise swaps of items of group g with items of group gand save the best found in M2 gg1,M 2 gg2, and M2 gg3. 7: end if 8: if M2 gg1>max then 9: max =M2 gg1,i =M2 gg2, and j =M2 gg3. 10: end if 11: end for 12: end for 13: Realize best swap if max >0, i.e. insert item i in group gand item j in group g. 14: Update matrices M1and M2if a swap was realized. 2.4 Comparison of the three implementations Comparing the three implementations, the standard implementation fully evaluates the neighborhoods in every iteration. The ND implementation saves some computations by evaluating only those parts which might be promising but always evaluates a neighborhood block if anything has changed in the assignment of one of the two involved groups. The efficient ND implementation saves the best insert/swap which can be realized between two groups such that the neighborhood block only needs to be re-evaluated if anything changes in one of the two groups. In other words, every part of the neighborhood which needs to be evaluated in the efficient ND implementation needs also to be evaluated in the ND implementation and every part of the neighborhood which needs to be evaluated in the ND implementation needs to be evaluated in the standard implementation. Thus, we have a clear hierarchy in the efficiency of the implementations. Concretely, we need to evaluate |I|·(|G|−1)=(|I1|+...|I|G||)·(|G|−1)inserts in the standard implementation while we only need to evaluate up to (|Ig1|+|Ig2|)·(|G|−1)inserts 123 1254 Annals of Operations Research (2024) 341:1247–1265 in the efficient ND implementation whereat g1and g2are the two groups which were changed by an insert/swap in the previous iteration. All items of these two groups (|Ig1|+|Ig2|) need to be reinserted into all remaining |G|−1 groups. It can clearly be seen that the efficient ND implementation requires fewer evaluated inserts than the standard implementation if |G|>2 while the difference is the larger the larger |G|is. The ND implementation is in the best case as efficient as the efficient ND implementation, but in the worst case as inefficient as the standard implementation. If the swap neighborhood is considered, we need to evaluate g∈G|Ig|·(|I|\|Ig|)/2 swaps in the standard implementation, i.e. for every item of a group (|Ig|) the swap with any item assigned to another group (|I|\|Ig|). As the swap of two items only needs to be evaluated once, we divide the result by two. In the efficient ND implementation, we only need to update swaps of the items assigned to a group gwith the items assigned to all other groups if group gwas changed in the previous iteration. As in one iteration at most two groups g1 and g2are changed, we need to evaluate at most g∈{g1,g2}|Ig|·(|I|\|Ig|)−|Ig1|·|Ig2| swaps whereat |Ig1|·|Ig2|subtracts the swaps between the two groups g1and g2which are otherwise counted twice. Again, the efficient ND implementation is more efficient than the standard implementation if |G|>2 and the difference is the larger the larger |G|is. Moreover, the ND implementation is again in the best case as efficient as the efficient ND implementation, but in the worst case as inefficient as the standard implementation. The difference is even clearer if one of the neighbourhoods is called without having any change in the group assignment since the last call of the algorithm. Then, matrices M1and M2, respectively, are up to date such that the efficient ND implementation does not need to re-evaluate any part of the neighborhood. It only has an effort of up to |G|·(|G|−1)to find the best neighbouring solution. This is clearly less effort than in the standard implementation requiring |I|·(|G|−1)for the insertion neighborhood and |I|2for the swap neighborhood. We are certainly in this situation if we are in a local optimum for both neighborhoods. Then, we need to re-evaluate both neighborhoods before we know that we are in a local optimum, but for the one leading to the local optimal solution nothing hast changed since the last call. Of course we do not want to stay in a local optimum. To not stick there, we introduce a variable neighborhood search (VNS) based framework with perturbation in the next section which is used to evaluate the introduced neighborhood implementations in the computational study. 3 Variable neighborhood search framework Before we introduce the overall framework we first introduce the used perturbation methods to avoid sticking in local optimal solutions. We use the weak and strong perturbation method presented in Lai and Hao (2016). They are presented in Algorithms 7and 8. As in Lai and Hao (2016)wesetηw=3andηs=·|I|/|G|, whereat =1if|I|≤400 and 1.5 otherwise. In Algorithm 7, we determine 5 solutions in the for-loop starting in Line 4. Lai and Hao (2016) determined |I|solutions in the for-loop. However, in our preliminary evaluations this resulted in a very significant time spent for the weak perturbation. Therefore, we decreased the value such that the algorithm spends much more time for the neighborhood evaluation and we can perform clearly more iterations. Algorithm 7 [Weak perturbation] 1: Let a solution y be given. 2: for all n=1to ηwdo 123 Annals of Operations Research (2024) 341:1247–1265 1261 Table 2 continued Skipped block evaluations [%] Instance type 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 If we use the ND implementation, we moreover need to evaluate all of the others if there is a promising insert/swap. Consequently, the share of skipped block evaluations increases to more than 82% for the swap neighborhood and over 70% for the insertion neighborhood if we use the efficient ND implementation. The values are smaller if the swap as well as the insertion neighborhood are used, i.e. for the instances with unequal-sized groups. One reason is that both neighborhoods are evaluated alternately. Thus, up to four groups were changed instead of up to two before the same neighborhood is evaluated next (can be more if perturbation is executed meanwhile). Table 3shows the success rates of the two neighborhoods as well as the average number of iterations between two consecutive calls of the perturbation algorithms 7and 8, respectively. The success rate is the percentage of calls of the neighborhood in which an improved solution was found. It is not surprising that more iterations were performed before the algorithm reaches a local optimum, i.e. perturbation is required, if the instance size is larger. Thus, the success rates of both neighborhoods increase with the instance size. Especially the swap neighborhood with a success rate of up to 91% is very effective. The insertion neighborhood reaches a success rate of only about 50%. Thus, there are more iterations without any change in the current solution which explains why the ND implementation is more effective for instances with unequal group sizes. If an iteration is unsuccessful, no promising neighborhood block exists. This also means that in the next call of the insertion neighborhood only those neighbourhood blocks need to be evaluated which were changed due to a swap in the swap neighborhood which was called in the meantime. Thus, ND is as effective as efficient ND and clearly superior to standard in this case. Our implementation with the alternate calls of both neighborhoods follows Lai and Hao (2016). The small success rate of the insertion neighborhood, however, might be an argument to follow another policy in future approaches. 5 Conclusion The paper compares the three implementations called standard,ND,andefficient ND of the insertion and the swap neighborhood for the MDGP. The efficient ND implementation is newly introduced and based on the ND implementation. Both implementations use the idea that the neighborhoods can be divided into independent blocks containing the inserts/swaps between two groups. While the ND implementation evaluates a block if there is a promising, 123 1262 Annals of Operations Research (2024) 341:1247–1265 Table 3 Evaluation of algorithm design Success rate Success rate Perturbation (no. it.) Instance type Insertion [%] Swap [%] Weak Strong 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 RanInt_n010_ds 18.88 54.95 4.8 31.4 RanInt_n010_ss – 43.59 3.5 21.7 RanInt_n012_ds 32.06 63.80 6.1 47.5 RanInt_n012_ss – 56.00 4.5 30.8 RanInt_n030_ds 38.54 74.29 8.5 72.0 RanInt_n030_ss – 69.37 6.5 57.1 RanInt_n060_ds 45.67 76.91 9.3 74.6 RanInt_n060_ss – 72.29 7.2 55.9 RanInt_n120_ds 46.63 78.78 10.1 74.4 RanInt_n120_ss – 74.29 7.8 51.5 RanInt_n240_ds 52.38 81.73 11.8 87.1 RanInt_n240_ss – 78.84 9.5 59.4 RanInt_n480_ds 51.82 87.45 17.0 76.2 RanInt_n480_ss – 84.14 12.6 51.0 RanInt_n960_ds 51.09 91.39 24.5 110.6 RanInt_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 of Operations Research (2024) 341:1247–1265 1263 Table 3 continued Success rate Success rate Perturbation (no. it.) Instance type Insertion [%] Swap [%] Weak Strong 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 improving insert/swap, the efficient ND implementation evaluates each block only if the assignment to at least one of its groups has changed. All three neighborhood implementations were compared in an extensive computational study on the classical benchmark sets. The results show that the standard implementation is superior for small instance sizes while the efficient ND implementation is superior for large instance sizes. The ND implementation performed best for medium sized instances with unequal group sizes. A reason for it is that the insertion neighborhood found only in around half of the cases an improved solution. For the large instances the efficient ND implementation could perform up to 160% more iterations in comparison to standard and up to 76% more iterations in comparison to ND. Our results lead to several directions for future research. First, the new neighborhood implementation can be used for other grouping or clustering problems. These include as mentioned in the introduction problems like the capacitated clustering problem or the capacitated p-median problem as well as the ratio cut and normalized cut graph partitioning problem, vehicle routing problems, or parallel machine scheduling (Yalaoui & Chu, 2002). Second, we found that the insertion neighborhood has a success rate of only about 50% if both neighborhoods, insertion and swap, are called alternately. Future research could evaluate other policies to increase the neighborhoods’ success rates. Finally, future research can extend our approach by using the matrices M1and M2to determine more than one promising insert/swap per iteration. The matrices indicate the best insert/swap between two groups. As long as group pairs are disjunct one could also realize additional neighborhood moves in the same iteration. The best selection can be determined by a maximum weighted matching. Funding Open Access funding enabled and organized by Projekt DEAL. No funding was received for conducting this study. Declaration Conflict of interest The author has no Conflict of interest to declare that are relevant to the content of this article. 123 1264 Annals of Operations Research (2024) 341:1247–1265 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Baker, B. M., & Benn, C. (2001). Assigning pupils to tutor groups in a comprehensive school. Journal of the Operational Research Society, 52(6), 623–629. Baker, K. R., & Powell, S. G. (2002). Methods for assigning students to groups: A study of alternative objective functions. Journal of the Operational Research Society, 53, 397–404. Batista, R. M., Mao, E., & Sussman, A. B. (2023). Keeping cash and revolving debt: Examining co-holding in the field and in the lab. Available at SSRN 4558490 Beheshtian-Ardekani, M., & Mahmood, M. A. (1986). Education development and validation of a tool for assigning students to groups for class projects. Decision Sciences, 17(1), 92–113. Brimberg, J., Mladenovi´c, N., & Uroševi´c, D. (2015). Solving the maximally diverse grouping problem by skewed general variable neighborhood search. Information Sciences, 295, 650–675. Brusco, M. J., Cradit, J. D., & Steinley, D. (2020). Combining diversity and dispersion criteria for anticlustering: A bicriterion approach. British Journal of Mathematical and Statistical Psychology, 73(3), 375–396. Chen, Y., Fan, Z. P., Ma, J., & Zeng, S. (2011). A hybrid grouping genetic algorithm for reviewer group construction problem. Expert Systems with Applications, 38(3), 2401–2411. Dias, T. G., & Borges, J. (2017). A new algorithm to create balanced teams promoting more diversity. European Journal of Engineering Education, 42(6), 1365–1377. Fan, Z. P., Chen, Y., Ma, J., & Zeng, S. (2011). Erratum: A hybrid genetic algorithmic approach to the maximally diverse grouping problem. Journal of the Operational Research Society, 62(7), 1423–1430. Feo, T. A., & Khellaf, M. (1990). A class of bounded approximation algorithms for graph partitioning. Networks, 20(2), 181–195. Gallego, M., Laguna, M., Martí, R., & Duarte, A. (2013). Tabu search with strategic oscillation for the maximally diverse grouping problem. Journal of the Operational Research Society, 64(5), 724–734. Lai, X., & Hao, J. K. (2016). Iterated maxima search for the maximally diverse grouping problem. European Journal of Operational Research, 254(3), 780–800. Lai, X., Hao, J. K., Fu, Z. H., & Yue, D. (2021). Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping. European Journal of Operational Research, 289(3), 1067–1086. Lai, X., Hao, J. K., Fu, Z. H., & Yue, D. (2021). Neighborhood decomposition-driven variable neighborhood search for capacitated clustering. Computers & Operations Research, 134, 105362. Mingers, J., & O’Brien, F. A. (1995). Creating student groups with similar characteristics: A heuristic approach. Omega, 23(3), 313–321. Palubeckis, G. (2022). Metaheuristic approaches for ratio cut and normalized cut graph partitioning. Memetic Computing, 14(3), 253–285. Palubeckis, G., Karˇciauskas, E., & Riškus, A. (2011). Comparative performance of three metaheuristic approaches for the maximally diverse grouping problem. Information Technology and Control, 40(4), 277–285. Palubeckis, G., Ostreika, A., & Rubliauskas, D. (2015). Maximally diverse grouping: An iterated tabu search approach. Journal of the Operational Research Society, 66(4), 579–592. Papenberg, M. (2024). K-plus anticlustering: An improved k-means criterion for maximizing between-group similarity. British Journal of Mathematical and Statistical Psychology, 77(1), 80–102. Papenberg, M., & Klau, G. W. (2021). Using anticlustering to partition data sets into equivalent parts. Psychological Methods, 26(2), 161. Pfeiffer, C., & Schulz, A. (2022). An alns algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectrum, 44(1), 87–119. Rodriguez, F. J., Lozano, M., García-Martínez, C., & González-Barrera, J. D. (2013). An artificial bee colony algorithm for the maximally diverse grouping problem. Information Sciences, 230, 183–196. Rubin, P. A., & Bai, L. (2015). Forming competitively balanced teams. IIE Transactions, 47(6), 620–633. 123 Annals of Operations Research (2024) 341:1247–1265 1265 Schulz, A. (2021). The balanced maximally diverse grouping problem with block constraints. European Journal of Operational Research, 294(1), 42–53. Schulz, A. (2022). A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values. Annals of Operations Research, 318(1), 501–530. Schulz, A. (2023). The balanced maximally diverse grouping problem with attribute values. Discrete Applied Mathematics, 335, 82–103. Uroševi´c, D. (2014). Variable neighborhood search for maximum diverse grouping problem. Yugoslav Journal of Operations Research, 24(1), 21–33. Weitz, R. R., & Lakshminarayanan, S. (1998). An empirical comparison of heuristic methods for creating maximally diverse groups. Journal of the Operational Research Society, 49(6), 635–646. Yalaoui, F., & Chu, C. (2002). Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76(3), 265–279. Yang, X., Cai, Z., Jin, T., Tang, Z., & Gao, S. (2022). A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem. European Journal of Operational Research, 302(3), 925–953. Zheng, S., Lai, X., & Gong, W. (2021). Neighborhood decomposition based variable neighborhood search for the capacitated p-median problem. In: 2021 China Automation Congress (CAC), IEEE, pp. 1101–1105 Zhou, Y., Kou, Y., & Zhou, M. (2023). Bilevel memetic search approach to the soft-clustered vehicle routing problem. Transportation Science, 57(3), 701–716. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123