Skip to content

zhumingpassional/Maxcut_CSCI

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

24 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Run algorithms

Commands:

python greedy.py           #Local Search
python random_walk.py
python simulated_annealing.py

Datasets

Take g14.txt (an undirected graph with 800 nodes and 4694 edges) as an example:

800 4694 # #nodes is 800, and #edges is 4694.

1 7 1 # node 1 connects with node 7, weight = 1

1 10 1 # node 1 connects node 10, weight = 1

1 12 1 # node 1 connects node 12, weight = 1

Results

Results will be written to a file xxx.txt in the folder "result". The first column is nodes, and the second column is label.

1 2 # node 1 in set 2

2 1 # node 2 in set 1

3 2 # node 3 in set 2

4 1 # node 4 in set 1

5 2 # node 5 in set 2

Performance

In the following experiments, we used GPU during training by default. The best-known results are labed in bold.

The results are stored in the folder "result". Take Gset as an example.

Gset was created by Stanford University.

graph #nodes #edges BLS DSDP KHLWG RUN-CSP PI-GNN Gurobi (0.5 h) Gurobi (1 h) Gap Ours Improvement
G14 800 4694 3064 2922 3061 2943 3034 3042 3.61% 3064 +0%
G15 800 4661 3050 2938 3050 2928 2990 3016 3033 3.33% 3050 +0%
G22 2000 19990 13359 12960 13359 13028 13181 13062 13129 28.94% 13359 +0%
G49 3000 6000 6000 6000 6000 6000 5918 6000 6000 0 6000 +0%
G50 3000 6000 5880 5880 5880 5880 5820 5880 5880 0 5880 +0%
G55 5000 12468 10294 9960 10236 10116 10138 10103 10103 11.92% 10298 +0.04%
G70 10000 9999 9541 9456 9458 - 9421 9489 9490 2.26% 9583 +0.44%

L2A's results are represented as strings. How to transfer the strings into binary results?

Take data/syn/powerlaw_100_ID0.txt as an example, the result is "4SuqhIaQimYjyk_sX" by L2A, which can be transferred to a binary vector by calling the function str_to_bool in EncoderBase64 in evaluator.py.

Releases

No releases published

Packages

No packages published

Languages