# Variable Neighborhood Search in Hamming Space

Simon B Hengeveld, Antonio Mucherino

► To cite this version:

Simon B Hengeveld, Antonio Mucherino. Variable Neighborhood Search in Hamming Space. Lecture Notes in Computer Science 13952, I. Lirkov, S. Margenov (Eds.), Jun 2023, Sozopol, Bulgaria. pp.253-261. hal-04647131

HAL Id: hal-04647131

https://inria.hal.science/hal-04647131v1

Submitted on 13 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Variable Neighborhood Search in Hamming Space

S.B. Hengeveld, A. Mucherino

IRISA, University of Rennes, Rennes, France.

Email: {simon.hengeveld, antonio.mucherino}@irisa.fr

**Abstract.** Variable Neighbourhood Search (VNS) is one of the most used meta-heuristics for global optimization. We focus our attention on combinatorial problems and propose a new implementation of VNS in Hamming space. Together with the basic VNS approach initially proposed by Hansen and Mladenović, we present a comparison among the most known VNS variants and we adapt them for the Hamming space. Our VNS is coded in Java programming language and implements the interfaces of the BINMETA public project, where other meta-heuristics were previously included. Our computational experiments, on a small selection of combinatorial problems, show that our new VNS implementations outperform the other meta-heuristics present in BINMETA.

## 1 Introduction

Meta-heuristics are widely used for the solution of hard optimization problems [16]. Variable Neighbourhood Search (VNS) is one of the most known and useful meta-heuristics for global optimization. The very first paper introducing VNS [14] appeared in 1997 and was cited, accordingly to Google Scholar, more than 5000 times in about 25 years. VNS was in fact used for attempting the solution of several problems that are otherwise intractable, and this large use encouraged the proposition in the scientific literature of several VNS variants.

This work is based on the observation that, in spite of this vast use of VNS, and in particular for the solution of combinatorial problems, there exists, to date, no VNS implementation that is specialized for this kind of problems. By specialization we mean the possibility for the meta-heuristic search to manipulate solutions expressed in binary representation, and to generate and explore neighbourhoods by using a metric different from the classical Euclidean distance. In this work, we will employ the Hamming distance.

Given a binary representation for the solutions of a given optimization problem, the smallest piece of information that we can consider is the *bit*, while a bit string of fixed length *n* provides the full representation. Two solutions in this representation differ therefore if at least one of their bits, when placed in the same position in the bit string, have opposite value. The Hamming distance counts the number of such different bits in two given representations.

We point out that this is not the first contribution on meta-heuristics in Hamming space; the reader can refer for example to [1]. This is not the first contribution either where the Hamming distance is used in the conception of VNS. In [10], for example, it was already suggested to use binary strings to represent solutions when solving the
simple plant location problem, and hence to define neighborhoods by using the Hamming distance. Moreover, two examples of VNS in Hamming space can be found in the context of Mixed Integer Programming (MIPs) for scheduling jobs [7] and nurse rostering problems [6]. More recently, in 2014, a VNS implementation acting on binary strings was used to perform edge-ratio network clustering in [4]. However, to the best of our knowledge, ours is the first general-purpose VNS working with binary strings and exploring neighbourhoods defined in Hamming space.

The rest of the paper is organized as follows. In Section 2, we will briefly recall the main ideas behind VNS, and we will focus our attention on a set of well-known VNS variants. In Section 3, we will present our implementation of such variants. Notice that this implementation is publicly available on the BINMETA repository, together with the Java class used for running the experiments that we will present in Section 4. Finally, Section 5 will conclude the paper.

## 2 Basic VNS and variants

The basic idea behind VNS is very simple and very effective [9]. Given the current solution $x$ to a given optimization problem with objective function $f$, the search attempts discovering better quality solutions $x'$, i.e. solutions such that $f(x') < f(x)$, in a relatively small neighbourhood of $x$. When this is not possible (or it looks like it is not possible), larger and larger neighbourhoods can be taken into consideration. This initial phase of VNS is generally referred to as the *shaking procedure*, and it is often simply implemented by picking up a random solution in the current neighbourhood. When it fails to find better quality solutions, the neighbourhood is generally enlarged.

When a new solution $x'$ capable of improving the objective function $f$ is identified during the shaking phase, then the current neighbourhood may be recentered at $x'$, because $x'$ is then supposed to be the starting point for further explorations. If the neighbourhood had increased in size during the shaking phase, then it may also be reduced to its initial size, in order to focus the search around the nearest solutions to the current best one. We use the conditional form in this paragraph because many variants of VNS act in slightly different ways [12]; the behavior briefly mentioned here is the one of the basic VNS initially proposed in 1997 by Mladenović and Hansen [14].

Fig. 1 shows, in our unique graph representation, the main steps for one iteration of the VNS variants considered in this work. The original VNS is given by the path starting with the shaking procedure, going through the local search, and then to the node performing the “sequential neighbourhood change”. Subsequently, a new iteration is performed if the stopping criteria is not yet verified.

For lack of space, we opt in this paper for a simple description of the VNS variants providing only some main ideas behind their conception; the reader interested in a more complete and formal description of the variants can make reference to [11, 12], as well as to citations given below for some specific variants.

The variations on the basic VNS basically consist in the choice on whether running or not the local search immediately after the shaking procedure, as well as in the choice of the approach for changing the current neighbourhood. In the cyclic approach [19], the size of the neighbourhoods is not reset to the initial size whenever better solutions $x'$
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** A complete path on this directed graph depicts the general iteration of one VNS variant. From the shaking node, the path may go through the local search, or to point directly to one of the possible ways to update the current neighbourhood. N.C. stands for Neighbourhood Change. The graph vertex named Nested is a little special, because it represents an independent call to a VNS variant (except itself). When the stopping criteria is satisfied, VNS stops; otherwise, it cycles back to the shaking procedure for beginning with another iteration.</figcaption></figure>

are found; the neighbourhood change only consists in recentering it at $x'$. The adjective “cyclic” is employed here to point out the fact that the growth of the neighbourhood sizes does not depend on the encountered solutions, but it may be reset to the initial size when the maximal size has been reached and the VNS stopping criteria is not yet satisfied.

The pipe neighbourhood change only differs from the cyclic approach by the fact that the latter avoids increasing the size of the neighbourhood when a better solution $x'$ has just been found [20]. Moreover, in the jump variant [11], the changes in the size of the neighbourhood are instead not linear: a random number of possible sizes is actually skipped, so that to produce a “jump” in the sequence of neighbourhoods.

The skewed neighbourhood change does not only take into account the values of the objective function in the previous $x$ and the current $x'$ solutions, but also their distance in the search domain [3]. The idea is to give the chance to solutions that are far from $x$ to be accepted even when they do not improve the objective function, but the deterioration is somehow acceptable. In fact, this may allow the search to discover a new region of the domain where better solutions may thereafter be identified.

The last (in order of presentation) VNS variant that we consider in this work is the nested VNS [18]. The idea is to replace the local search with another VNS call, where any of the variants presented above may be used. The nested variant can be particularly interesting to use when the problem at hand does not allow to devise a local search
to 1 because the implemented local search (see Section 4) is based on the idea to look
around the current solution by performing single bit flips in the binary representation.
In general, therefore, a lower bound $\ell$ and an upper bound $u$ on the Hamming distance
are involved in the definition of the neighbourhood. When $\ell < u$, we define the next
neighbourhood by approaching $\ell$ to $u$ (i.e. $\ell \leftarrow \ell + 1$). This allows us to intensify more
and more our searches around the region of the Hamming space where the solutions
admit $u$ bit flips w.r.t. the current solution $x$. When $\ell = u$, instead, we create the new
neighbourhood with lower bound $\ell \leftarrow 1$ and upper bound $u \leftarrow u + 1$, in order to reopen
the possibility to select closer solutions, and at the same time by enlarging the horizon.

We point out that necessary condition for an effective similarity (or dissimilarity)
measure by Hamming distance between pairs of solutions is that there exists no solution
that can be represented with two different binary strings. Other criteria may as well be
taken into consideration when defining the binary representations in order to improve
the search (we mention to one of these in Section 5).

4 Computational experiments

We present in this work a VNS implementation that is part of the BINMETA<fnref n="1" /> Java
project, which is conceived particularly to study meta-heuristic searches for global op-
timization problems for which a suitable binary representation can be supplied [15].
The reason for representing solutions as bit strings stems from the fact that several
combinatorial search spaces can admit such discrete representations, as for example it
is the case when dealing with search trees. The BINMETA project already implements
some meta-heuristic searches: the classical MultiStart heuristics [2], the Wolf Search
[17], as well as a simple Random Walk. All VNS variants discussed in Section 2 have
been implemented and added to the project while performing the work presented in this
article.

The local search implemented in BINMETA, and used by most meta-heuristics, re-
sembles to the traditional gradient descent methods in continuous spaces. In Hamming
space, we initially attempt flipping each bit in the binary representation, one by one, and
analyze the variations on the objective function values. While bit flips that worsen the
objective values are discarded, the others are kept in memory and sorted by placing the
ones leading to the best improvements at the top of a stack S. When all bits have been
independently considered and the stack is complete, the procedure attempts to flip all
the bits in S. However, it is not guaranteed that the objective function will improve after
this change (the parallel with the continuous gradient is that a full step along the gradi-
ent direction may not lead to better solutions). When there is indeed no improvement,
then the bit appearing at the bottom of the stack is erased, and a new attempt with the
remaining bits is performed. And so on, until there is an improvement on the objective
function, or the stack is reduced to only one bit (this is the worst-case scenario). The
entire procedure is repeated then and stops if the initial stack is empty (we are stuck at
a local optimum).

For lack of space, we cannot describe in any detail the combinatorial problems that
we use in our computational experiments. The reader is referred to [13] for the com-

<footnote n="1">¹ https://github.com/mucherino/binMeta</footnote>
<table><caption>**Table 1.** A comparison among meta-heuristic searches and VNS variants.</caption><thead><tr><th colspan="2">instance</th><th colspan="10">objective function value in best found solution – known upper bound</th></tr><tr><th>objective</th><th>size</th><th>LocalOpt</th><th>RandomWalk</th><th>MultiStart</th><th>WolfSearch</th><th>basic VNS</th><th>cyclic VNS</th><th>pipe VNS</th><th>jump VNS</th><th>skewed VNS</th><th>nested VNS</th></tr></thead><tbody><tr><td>N.Partition</td><td>600</td><td>8094.0</td><td>0.0</td><td>1328.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>4.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>700</td><td>434.0</td><td>0.0</td><td>0.0</td><td>8.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>4.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>800</td><td>4764.0</td><td>0.0</td><td>174.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>900</td><td>15824.0</td><td>0.0</td><td>8624.0</td><td>6.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>12.0</td><td>0.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>1000</td><td>15836.0</td><td>0.0</td><td>9008.0</td><td>4.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>4.0</td><td>0.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>1100</td><td>25774.0</td><td>0.0</td><td>20578.0</td><td>48.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>2.0</td><td>2.0</td></tr><tr><td>N.Partition</td><td>1200</td><td>5004.0</td><td>0.0</td><td>40.0</td><td>14.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>2.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>1300</td><td>1884.0</td><td>0.0</td><td>32.0</td><td>78.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>N.Partition</td><td>1400</td><td>2816.0</td><td>2.0</td><td>54.0</td><td>44.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>600</td><td>25175.0</td><td>6230.0</td><td>20596.0</td><td>4093.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>3.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>700</td><td>53271.0</td><td>43528.0</td><td>47219.0</td><td>51249.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>1.0</td><td>0.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>800</td><td>75004.0</td><td>49977.0</td><td>70296.0</td><td>58027.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>1.0</td><td>3.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>900</td><td>35987.0</td><td>7510.0</td><td>32961.0</td><td>14417.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>3.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>1000</td><td>33828.0</td><td>2.0</td><td>30239.0</td><td>588.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>0.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>1100</td><td>131510.0</td><td>81459.0</td><td>128598.0</td><td>99258.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>1.0</td><td>1.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>1200</td><td>16670.0</td><td>0.0</td><td>12479.0</td><td>110.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>1.0</td><td>1.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>1300</td><td>34867.0</td><td>7.0</td><td>31626.0</td><td>5519.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td>SubsetSum</td><td>1400</td><td>197493.0</td><td>139443.0</td><td>191863.0</td><td>148870.0</td><td>1.0</td><td>0.0</td><td>0.0</td><td>2.0</td><td>1.0</td><td>0.0</td></tr><tr><td>Knapsack</td><td>600</td><td>69959.0</td><td>72771.2</td><td>65830.5</td><td>69959.0</td><td>-2945.5</td><td>-3948.8</td><td>-4325.0</td><td>-4729.7</td><td>-4905.2</td><td>-4976.7</td></tr><tr><td>Knapsack</td><td>700</td><td>43472.6</td><td>104697.0</td><td>39583.8</td><td>43472.6</td><td>-2308.5</td><td>-2688.2</td><td>-3126.8</td><td>-3432.5</td><td>-3592.9</td><td>-3592.9</td></tr><tr><td>Knapsack</td><td>800</td><td>55217.0</td><td>127543.9</td><td>50274.0</td><td>55217.0</td><td>-1758.5</td><td>-2462.4</td><td>-3104.9</td><td>-3346.2</td><td>-4584.4</td><td>-4584.4</td></tr><tr><td>Knapsack</td><td>900</td><td>177941.8</td><td>-207.0</td><td>173296.5</td><td>177941.8</td><td>15769.9</td><td>-4980.4</td><td>-6873.5</td><td>-7740.1</td><td>-9017.8</td><td>-9488.5</td></tr><tr><td>Knapsack</td><td>1000</td><td>219412.6</td><td>-229.6</td><td>215423.2</td><td>219412.6</td><td>67103.7</td><td>-4387.0</td><td>-6640.7</td><td>-8560.9</td><td>-10892.6</td><td>-11331.7</td></tr><tr><td>Knapsack</td><td>1100</td><td>135904.1</td><td>257963.6</td><td>131345.3</td><td>135904.1</td><td>-1140.5</td><td>-4212.6</td><td>-6463.7</td><td>-8253.0</td><td>-8995.3</td><td>-9564.9</td></tr><tr><td>Knapsack</td><td>1200</td><td>188546.0</td><td>318048.8</td><td>182676.6</td><td>188546.0</td><td>54283.7</td><td>-3602.8</td><td>-6217.9</td><td>-8645.4</td><td>-10117.0</td><td>-10272.2</td></tr><tr><td>Knapsack</td><td>1300</td><td>234320.5</td><td>380275.8</td><td>228962.0</td><td>234320.5</td><td>107652.4</td><td>-3604.4</td><td>-6160.9</td><td>-8346.4</td><td>-9627.6</td><td>-10497.3</td></tr><tr><td>Knapsack</td><td>1400</td><td>47633.4</td><td>427977.4</td><td>43082.7</td><td>47633.4</td><td>-1312.6</td><td>-1312.6</td><td>-1312.6</td><td>-2090.5</td><td>-2238.3</td><td>-2238.3</td></tr></tbody></table>
binational problems named SUBSETSUM, NUMBERPARTITION and KNAPSACK. The instances of such problems were artificially generated by using the Java constructors recently added to the corresponding classes.

The experiments were performed on a laptop computer equipped with an proces-
sor Intel(R) Core(TM) i7-8665U CPU @1.90GHz, running Linux Ubuntu 20.04.6 LTS.
The codes were compiled and run by the free and open-source Java platform named
Openjdk, version 11.0.18 2023-01-17. The version of the Java codes used in the experi-
ments is the one related to the commit 2de34fc on the GitHub BINMETA repository. All
meta-heuristics were given 1 second of CPU time to solve each instance.

Our experiments are summarized in Table 1. In order to evaluate the quality of the
found solutions, we compute the difference between the objective function value in the
solution, and the known upper bound on the solutions. The latter is estimated by the
procedure that is implemented by the constructors. Therefore, when the reported values
are positive, this corresponds to runs where the optimal solutions were not identified; if
the reported value is instead zero or even negative, this means that the expected value
(or even a smaller value) was found for the objective function.

The reported experiments are rather simple to interpret. Even if there are exceptions,
as one may expect when working with meta-heuristics, VNS is generally the one that is
able to provide better results in the little time at disposal (recall, 1 second of CPU time
is given). For the instances of larger size, we can see that the jump, skewed and nested
VNS are the variants that are able to provide better results.

5 Conclusions

We have presented a short survey on VNS variants and adapted the most used ones to
work in Hamming space. We have implemented such variants in the context of the wider
BINMETA project, and our preliminary computational experiments evidently indicate
that VNS can attain better performances when compared to the other meta-heuristics in
the Java project.

In the near future, we intend to develop a more formal description of the meta-
heuristic searches in Hamming space, for example via the use of pseudo-boolean func-
tions. Our intention is to pay particular attention to the conception of the binary rep-
resentations, in order to make sure that the induced objective function *landscapes* are
smooth and hence easily inspected by the meta-heuristics. In parallel with these future
works, more combinatorial problems, as well as more meta-heuristic searches, will be
added to the repository.

Acknowledgments

First of all, we are thankful to all Master students that have contributed to the realization
of the BINMETA project. We also wish to thank the anonymous reviewers for their
fruitful comments. This work is partially supposed by the MULTIBIOSTRUCT project
(ANR-19-CE45-0019).
References

1. H. Banka, S. Dara, *A Hamming Distance based Binary Particle Swarm Optimization (HDBPSO) Algorithm for High Dimensional Feature Selection, Classification and Validation*, Pattern Recognition Letters **52**, 94–100, 2015.

2. K.D. Boese, A.B. Kahng, S. Muddu, *A New Adaptive Multi-Start Technique for Combinatorial Global Optimizations*, Operations Research Letters **16**(2), 101–113, 1994.

3. J. Brimberg, N. Mladenović, D. Urosević, *Solving the Maximally Diverse Grouping Problem by Skewed General Variable Neighborhood Search*, Information Sciences **295**, 650–675, 2015.

4. S. Cafieri, P. Hansen, N. Mladenović, *Edge-ratio Network Clustering by Variable Neighborhood Search*, The European Physical Journal B **87**(5), 1–7, 2014.

5. A. Casado, N. Mladenović, J. SánchezOro, A. Duarte, *Variable Neighborhood Search Approach with Intensified Shake for Monitor Placement*, Networks, 15 pages, 2022.

6. F. Della Croce, F. Salassa, *A Variable Neighborhood Search based Matheuristic for Nurse Rostering Problems*, Annals on Operational Research **218**, 185–199, 2014.

7. R. Driessel, L. Mönch, *Variable Neighborhood Search Approaches for Scheduling Jobs on Parallel Machines with Sequence-Dependent Setup Times, Precedence Constraints, and Ready Times*, Computers & Industrial Engineering **61**(2), 336–345, 2011.

8. K. Fleszar, K.S. Hindi, *Solving the Resource-Constrained Project Scheduling Problem by a Variable Neighbourhood Search*, European Journal of Operational Research **155**(2), 402–413, 2004.

9. P. Hansen, N. Mladenović, *Variable Neighborhood Search: Principles and Applications*, European Journal of Operational Research **130**(3), 449–467, 2001.

10. P. Hansen, N. Mladenović, *A Tutorial on Variable Neighborhood Search*, Les Cahiers du GERAD, Montréal QC H3T 2A7, Canada, 26 pages, 2003.

11. P. Hansen, N. Mladenović, J.A. Moreno Pérez, *Variable Neighbourhood Search: Methods and Applications*, Annals of Operations Research **175**, 367–407, 2010.

12. P. Hansen, N. Mladenović, R. Todosijević, S. Hanafi, *Variable Neighborhood Search: Basics and Variants*, European Journal on Computational Optimization **5**, 423–454, 2017.

13. B. Korte, *Combinatorial Optimization*, volume 1, Springer, 595 pages, 2011.

14. N. Mladenović, P. Hansen, *Variable Neighborhood Search*, Computers & Operations Research **24**(11), 1097–1100, 1997.

15. A. Mucherino, BINMETA: a New Java Package for Meta-Heuristic Searches, to appear in Lecture Notes in Computer Science, Proceedings of the 13th International Conference on Large-Scale Scientific Computations (LSSC21), Sozopol, Bulgaria, 2021.

16. A. Mucherino, O. Seref, *Modeling and Solving Real Life Global Optimization Problems with Meta-Heuristic Methods*. In: "Advances in Modeling Agricultural Systems", Springer Optimization and Its Applications **25**, P.J. Papajorgji, P.M. Pardalos (Eds.), 403–420, 2008.

17. R. Tang, S. Fong, X.S. Yang, S. Deb, *Wolf Search Algorithm with Ephemeral Memory*, IEEE Proceedings, 7th International Conference on Digital Information Management (ICDIM 2012), Macau, 165–172, 2012.

18. R. Todosijević, R. Benmansour, S. Hanafi, N. Mladenović, A. Artiba, *Nested General Variable Neighborhood Search for the Periodic Maintenance Problem*, European Journal of Operational Research **252**(2), 385–396, 2016.

19. R. Todosijević, A. Mjirda, M. Mladenović, S. Hanafi, B. Gendron, *A General Variable Neighborhood Search Variants for the Travelling Salesman Problem with Draft Limits*, Optimization Letters **11**, 1047–1056, 2017.

20. R. Todosijević, M. Mladenović, S. Hanafi, N. Mladenović, I. Crévits, *Adaptive General Variable Neighborhood Search Heuristics for Solving the Unit Commitment Problem*, International Journal of Electrical Power & Energy Systems **78**, 873–883, 2016.