/Max-Clique-Cplex-Python

Maximum Clique Problem solved by Branch and Bound method and Cplex Optimization.

Primary LanguagePython

Max-Clique-Cplex-Python

Requirements

  • Install Cplex for Python
  • Python >= 3.6
  • pip install -r requirements.txt

Evaluation on subset of DIMACS graphs

usage: max_clique_bnb_evaluator.py [-h] [--input_data_file INPUT_DATA_FILE]
                                   [--output_results_dump OUTPUT_RESULTS_DUMP]

optional arguments:
  -h, --help            show this help message and exit
  --input_data_file INPUT_DATA_FILE
                        path to file with input benchmarks data
  --output_results_dump OUTPUT_RESULTS_DUMP
                        path to output file

The sample of input data file.

GraphName,CorrectMaxClique,Level
johnson8-2-4.clq,4,E

Machine Characteristics Info

All graphs were evaluated on the machine with the following characteristics:

RAM - 64GB

Evaluation Results

BnB

Easy graphs

Graph Name Correct Max Clique Graph Complexity Found Max Clique Is Clique Consumed Time(seconds)
johnson8-2-4 4 E 4 True 0.244
johnson16-2-4 8 E 8 True 41.034
MANN_a9 16 E 16 True 1.128
keller4 11 E 11 True 175.136
hamming8-4 16 E 16 True 37.038

Meduim graphs

Graph Name Correct Max Clique Graph Complexity Found Max Clique Is Clique Consumed Time(seconds)
brock200_2 12 M 12 True 244.075
brock200_3 15 M 15 True 484.801
brock200_4 17 M 17 True 2680.945
C125.9 34 M 34 True 493.235
gen200_p0.9_44 44 M 44 True 2218.3
gen200_p0.9_45 55 M 55 True 34.521

BnC

Easy graphs

Graph Name Correct Max Clique Graph Complexity Found Max Clique Is Clique Consumed Time(seconds)
johnson8-2-4 4 E 4 True 0.272
johnson16-2-4 8 E 8 True 7.882
MANN_a9 16 E 16 True 2.571
keller4 11 E 11 True 248.607
hamming8-4 16 E 16 True 139.144

Meduim graphs

Graph Name Correct Max Clique Graph Complexity Found Max Clique Is Clique Consumed Time(seconds)
brock200_2 12 M 12 True 362.093
brock200_3 15 M 15 True 809.074
brock200_4 17 M 17 True 2064.928
C125.9 34 M 34 True 22.195
gen200_p0.9_44 44 M 44 True 6309.65
gen200_p0.9_45 55 M 55 True 181.005