Qinghua Wu, Jin-Kao Hao and Fred Glover. "Multi-neighborhood tabu search for the maximum weight clique problem". Annals of Operations Research 196(1): 611-634, 2012. (Download here)

Important note: Please make sure that the above paper is cited whenever our code is used in your research.

The source code (in C) for the MN/TS algorithm in the above paper can be found here. For a more detailed description of the MN/TS algorithm, please refer to the original paper.

We distribute the code for academic research, please inform Qinghua Wu (wu@info.univ-angers.fr) and Jin-Kao Hao (hao@info.univ-angers.fr) each time you download the code.

 Technical notes:

1. To run MN/TS, you can use the following command:

     mnts.exe   parameter1   parameter2   parameter3   paramter4

     where parameter1, parameter2, parameter3 and parameter4 are four parameters that we will describe in detail in the following.

2. parameter1 denotes the name of the iuput file (or the name of the instance). The format of the input file should be as follows (for instance):

   p 1000 449449

   e 2 1

   e 3 1

   e 3 2

   e 4 1


3. parameter2 denotes the objective value (or Wbest in the original paper) that the MN/TS algorithm tries to reach.

4. parameter3 is for allocating weight, for vertex i, of i mod parameter3 + 1. In the original paper, parameter3 is set to 200, 10 and 1 (unweighted case) respectively.

5. parameter4 is a very important parameter which denotes the search depth of the tabu search. In the original paper, parameter4 is set as follows. parameter4 = 4000 for the instances of the weighted case (MWCP). For the unweighted case (MCP), parameter4 = 10000 except for the brock and san families (DIMACS) for which parameter4 is equal to 100.

Contact Us

Please e-mail (wu@info.univ-angers.fr, hao@info.univ-angers.fr) under any of the following conditions:

Legal Information

The software is distributed for academic puposes only. If you wish to use this software for commercial applications, please obtain the prior permission from Jin-Kao Hao (hao@info.univ-angers.fr) and Qinghua Wu (wu@info.univ-angers.fr).