Skip to content

Implementation of branch and cut algorithm for maximum clique problem

Notifications You must be signed in to change notification settings

sergei-sl/MaxCliqueBranchAndCut

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

Releases

No releases published

Packages

No packages published