Implementation branch and bound algorithm for maximum clique problem in formulation as an continuous nonconvex optimization problem.
Detailed information in this paper: http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/The%20Maximum%20Clique%20Problem.pdf
This is Python 3.5.2 realization
Required:
NetworkXlibraryCPLEX for Python 3.5
To run script you should specify following parameters:
--path- path to DIMACS-format graph--time- time limit in seconds
All this graphs are placed in samples folder.
More of them you can find here: http://mat.gsia.cmu.edu/COLOR/instances.html
Huge ones: http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark#detC125.9
| Graph name | #Nodes | #Edges | Found clique length | Time(ms) |
|---|---|---|---|---|
| MANN_a9.clq | 45 | 918 | 16 | 559.974 ms |
| c-fat200-1.clq | 200 | 1534 | 12 | 2488.318 ms |
| c-fat200-2.clq | 200 | 3235 | 24 | 294.705 ms |
| c-fat500-1.clq | 500 | 4459 | 14 | 27029.180 ms |
| C125.9.clq | 125 | 6963 | 34 | 855937.042 ms |
| c-fat200-5.clq | 200 | 8473 | 58 | 10224.952 ms |
| c-fat500-2.clq | 500 | 9139 | 26 | 7544476.644 ms |