SE
sergei-sl/MaxCliqueBranchAndCut
Implementation of branch and cut algorithm for maximum clique problem
MaxCliqueBranchAndCut
Description
Realisation of branch and cut algorithm for finding exact solution for the Maximum clique problem using greedy graph heuristics.
Project also contains Cliquer solver: https://users.aalto.fi/~pat/cliquer.html (can be used for debugging purposes)
This is C++ realization for branch-and-cut (for example, see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.9473&rep=rep1&type=pdf) algorithm for the maximum clique problem:
In every branch we solve the corresponding LP relaxation for the maximum clique problem using Cplex
Instructions
To run the executable you should write in the command line:
- [executable_name] [path_to_the_file] [time_limit_in_seconds]
Default timeout is 0
Test results (for those graphs, where clique was found before the program was terminated by 3600 sec timeout)
| Graph name | #Nodes | #Edges | Found clique size | Time (ms) |
|---|---|---|---|---|
| brock200_2.clq | 200 | 9876 | 12 | 2839031 |
| brock200_4.clq | 200 | 13089 | 17 | 1897371 |
| c-fat200-1.clq | 200 | 1534 | 12 | 1120 |
| c-fat200-2.clq | 200 | 3235 | 24 | 552 |
| c-fat200-5.clq | 200 | 8473 | 58 | 1252 |
| c-fat500-1.clq | 500 | 4459 | 14 | 10139 |
| c-fat500-2.clq | 500 | 9139 | 26 | 6534 |
| c-fat500-5.clq | 500 | 23191 | 64 | 3974 |
| c-fat500-10.clq | 500 | 46627 | 126 | 1436 |
| hamming6-2.clq | 64 | 1824 | 32 | 5 |
| hamming6-4.clq | 64 | 704 | 4 | 20 |
| hamming8-4.clq | 256 | 20864 | 16 | 981 |
| johnson8-2-4.clq | 28 | 210 | 4 | 0 |
| johnson8-4-4.clq | 70 | 1855 | 14 | 18 |
| johnson16-2-4.clq | 120 | 5460 | 8 | 33 |
| MANN_a9.clq | 45 | 918 | 16 | 8 |
| MANN_a27.clq | 378 | 70551 | 126 | 91761 |
| p_hat300_1.clq | 300 | 10933 | 8 | 433339 |
| p_hat500_1.clq | 500 | 31569 | 9 | 1637892 |
| san200_0.7_1.clq | 200 | 13930 | 30 | 200 |
| san200_0.7_2.clq | 200 | 13930 | 18 | 8526 |
| san200_0.9_1.clq | 200 | 17910 | 70 | 120 |
| san200_0.9_2.clq | 200 | 17910 | 60 | 65 |
| san200_0.9_3.clq | 200 | 17910 | 44 | 870755 |
| san400_0.5_1.clq | 400 | 39900 | 13 | 161552 |
| san400_0.9_1.clq | 400 | 71820 | 13 | 101479 |
| C125.9.clq | 125 | 6963 | 34 | 733421 |
| gen200_p0.9_55.clq.txt | 200 | 17910 | 55 | 2480 |
| keller4.clq | 171 | 9435 | 11 | 607662 |