Does not seem to find a sub-optimal solution to the DIMACS graphs

[ShawalKassim1998]

No description provided.

[shah314]

Can you please describe the issue further? What DIMACS instances are you referring to? Have you tried increasing the number of iterations?

[ShawalKassim1998]

Most of them. It does not find the clique elements, although it finds the right size? And yes i used 1000 iterations as well for brock200_1,for example

[shah314]

I just tried the code on a few instances and there is no difference between the clique size found and the number of vertices in the output. Can you post your output? I used the instances from this page

[ShawalKassim1998]

That is so odd? Okay i will post a screenshot soon. May i ask how many generations you have used?
You used the instances from that page, but did you run the instances with your code? (Silly question)

[shah314]

Yes I ran it using my code. I used 100 generations. Can you try running the code on the instances on the page I just posted?

[shah314]

I ran the code on brock200_1 and I find the following results (both the clique size and the number of vertices in the output are 21). Is this not what you are seeing?

Generating Population...
94:21
95:21
96:21
97:21
98:21
99:21
Vertices in the Clique:
104 83 175 138 120 180 46 26 100 107 103 32 199 144 122 4 132 41 48 137 191 

[ShawalKassim1998]

When i run the same graph as you I get :
94:21
95:21
96:21
97:21
98:21
99:21
Time (precise) = 3.39596

Vertices in the Clique:
104 138 4 175 103 100 48 107 137 120 26 83 122 46 199 132 144 32 180 41 191

BUT the clique elements in this graph are:
133 17 92 177 38 19 84 134 107 89
185 91 67 141 149 72 101 135 86 93
80

[ShawalKassim1998]

From above you will see that it finds the clique size but does not seem to find the correct clique elements. Another issue is when i run certain graphs like sanr400_0.5 it gives me the following error:
Generating Population...
0:11
1:12
2:12
3:12
4:12
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)
Aborted

[shah314]

This is a randomized algorithm, so it might find other cliques (if they exist). I'll look into the out of range error.

[ShawalKassim1998]

I have been looking at hueristic algortithms that solve MCP and some of the algorithms either find the max clique or a sub-optimal of the max clique (meaning some elements are contained in the max clique). The same goes for evolutionary algorithms. So for the graph brock200_1, the biggest clique is 21, however, when run with a deterministic algorithm i only find one clique that has a size of 21? My apologies but I still dont see how any of the cliques reported by this evolutionary algorithm are a sub-optimal? Please help me understand

[ShawalKassim1998]

I understand its a randomized algorithm, but i dont find any other cliques of size 21 with a deterministic algorithm such as Cliquer by Patrick Oestergard

[shah314]

I wrote a small piece of code to check the clique in the brock200_1 graph.

The clique that you have mentioned has edges missing. For instance there is no edge from 133 to 177 or from 177 to 133. The cliques that my code finds are all valid. Am I doing something wrong?

[ShawalKassim1998]

Woah, I see that. Thats weird because i am using the instaces from here: http://archive.dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/

[ShawalKassim1998]

okay I think I understand now. The following clique is what I find using your code: 4 32 104 138 107 120 48 144 103 175 122 180 46 83 199 100 132 26 41 137 191 . And youre saying that the max clique mentioned in the text file for brock200_1 is not the only clique of size 21?

[ShawalKassim1998]

so essentially the clique: 4 32 104 138 107 120 48 144 103 175 122 180 46 83 199 100 132 26 41 137 191, is a clique in brock200_1?

[shah314]

Yes that is a clique (unless I am making some mistake).

[ShawalKassim1998]

Okay, lets hope you're not making some mistake haha. Thank you for your help! Please let me know when you fix the other error.

[shah314]

The number of nodes removed during mutation was more than the number of nodes in the clique. I changed the number of nodes removed to 1 and now it seems to work fine.

Thanks for looking into this! :)

[ShawalKassim1998]

One more question, is there a psuedo code avaible for your algorithm?

[shah314]

Here is a brief outline of the algorithm. Let me know if you have any questions.

Generate random population such that all cliques are valid
For specified number of generations:
  Save the global best clique
  Perform 2-opt local improvement on the global best individual
  Randomly choose two cliques and do intersection crossover on them such that the output is a valid clique
  Perform 2-opt local improvement on the offspring
  Perform mutation on the offspring (only if the offspring clique size is less than or equal to one of the parents)
  (In each of these steps, once the step has completed, make the clique valid and maximal using vertices in decreasing order of the degree)

[ShawalKassim1998]

Thanks for this! I was looking for a more formal one, thought maybe your research paper would contain this? Can you please explain in a little more detail how the crossover is calculated?

[shah314]

The code computes the intersection crossover (see method intersectionCrossover in the C++ code):

First compute the intersection of the two cliques and compute another clique from this intersection such that it is a valid clique (if the intersection is empty, compute greedyCrossover which adds vertices in decreasing order of the degrees)
After the intersection, try to add vertices to this clique in decreasing order of the degrees such that the clique is maximal

I have included comments in the code which should help you understand the algorithm if you need to go into more detail. You can start with the main method that is the entry point of the code. Let me know if you have more questions!