Go back to Charles-Edmond Bichot's home page

Partitions found with the Fusion Fission method

This page presents new best solutions for the multi-way (also called k-way) graph partitioning problem. This solution have been produced by an application of the Fusion Fission method to the multi-way graph partitioning problem.

The Fusion Fission method

The Fusion Fission method is a new metaheuristic based on the physical nuclear process created by Charles-Edmond Bichot. The Fusion Fission method has been presented at IEEE International Parallel & Distributed Processing Symposium [Bic06] and more precisely described in the Journal of Mathematical Modelling and Algorithms [Bic07]. In these papers it is applied to the Normalized-Cut graph partitioning problem. Although the bases of the Fusion Fission method are presented in these papers, the metaheuristic framework of the Fusion Fission method has not yet been published.

This page presents results of the Fusion Fission method applied to the multi-way graph partitioning problem. Because the Normalized-Cut graph partitioning problem and the multi-way graph partitioning problem are very different, our application of Fusion Fission is quite new. At this time, there is no publication which presents the application of Fusion Fission to the multi-way graph partitioning problem.

The multi-way graph partitioning problem

Given an undirected graph G = G(V,E) of vertices V and edges E, a partition P_k of the set of vertices V into k parts is a set of k pairwise disjoints subsets of vertices such that there union is V. The k-way graph partitioning problem is to partition the vertices of G into k roughly equal parts, such that the number of edges connecting vertices in different parts is minimized.

The multi-way graph partitioning problem is a combinatorial optimization problem. The objective function to minimize is the edge-cut objective function which computes the sum of the edge-weights between parts. The constraint of the problem is to find a partition with roughly equal parts. For this purpose, the balance of a partition is used. It is defined as the maximum weight of a part of the partition, divided by the average weight of the parts. Then, if S_opt is the average weight of the parts and W the weight of the weightiest part of the partition P_k, the balance is : Bal(P_k)=W/S_opt.

Results of Fusion Fission compared with best results of 20 algorithms

The following tables summarize the best partitions found by the Fusion Fission method. These partitions are compared to those of the Graph Partitioning Archive maintained by Dr. Chris Walshaw of the University of Greenwich. Graph Partitioning Archive's partitions are the best partitions found by 20 state-of-the-art algorithms. Each partition found by Fusion Fission which had at least the same edge-cut than the corresponding partition of the Graph Partitioning Archive is underlined and can be downloaded. Each partition found by Fusion Fission which had a lower edge-cut than the corresponding partition of the Graph Partitioning Archive is in bold.

Depending on partitions balances, four tables present the comparison between best partitions found by Fusion Fission and best partitions found by the 20 algorithms of the Graph Partitioning Archive:
Table I: A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.00
Bal=1.00 k=2 k=4 k=8
Graph Algorithm Cut FF Algorithm Cut FF Algorithm Cut FF
add20 PROBE 596 671 JE 1203 1207 iJ 1758 1819
data PROBE 189 193 iJ 429 391 iJ 728 728
3elt JE 90 90 JE 201 203 JE 349 369
uk mpM4 20 20 JE 44 44 JE 91 99
add32 Ch2 11 11 pM4 37 34 JE 75 72
bcsstk33 GCSVD 10171 10171 iJ 21956 22068 iJ 35088 36862
whitaker3 JE 127 127 JE 382 388 JE 664 713
crack JE 184 184 JE 368 370 JE 687 721
wingnodal JE 1707 1734 JE 3581 3717 JE 5443 5878
fe4elt2 MRSB 130 130 JE 349 351 JE 617 638
vibrobox JE 10343 11429 JE 19245 19766 iJ 25468 25903
bcsstk29 mpM4 2843 2843 MRSB 8786 8603 iJ 16832 17325
4elt JE 139 139 JE 327 338 JE 556 612
fesphere JE 386 386 NA 773 793 JE 1193 1289
cti JE 334 334 JE 977 963 JE 1812 1947
memplus PROBE 5513 5721 JE 9754 9819 iJ 12095 13110
cs4 JE 372 411 JE 964 1058 JE 1496 1746
bcsstk30 JE 6394 6394 JE 16652 16837 JE 34921 NA
bcsstk31 PROBE 2762 2782 iJ 8322 7667 pM4 14426 15934
bcsstk32 JE 4667 4890 JE 10578 10247 JE 22826 23537
t60k JE 80 85 JE 216 229 JE 480 561
wing MQI 791 925 JE 1666 1859 JE 2589 3018
brack2 JE 731 731 JE 3090 3154 JE 7269 7844
finan512 Ch2 162 162 Ch2 324 324 Ch2 648 729
fetooth mpM4 3850 3951 iJ 7605 7632 iJ 12850 13084
ferotor PROBE 2098 2135 Ch2 8097 7845 Ch2 14953 15712
598a PROBE 2398 2437 Ch2 8379 8277 Ch2 17223 17276
feocean PROBE 464 468 JE 1923 1944 NA 4760 5216
144 PROBE 6490 6998 NA 15964 16215 NA 27751 28254
wave PROBE 8692 8921 iJ 18774 18070 iJ 32204 32270
m14b MQI 3836 3919 Ch2 14013 13597 pM4 28128 28714
Go back to the list of tables. Go back to the top of this page.

Table II: A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.01
Bal=1.01 k=2 k=4 k=8
Graph Algorithm Cut FF Algorithm Cut FF Algorithm Cut FF
add20 GCSVD 594 656 JE 1203 1197 iJ 1758 1800
data AMG 188 189 iJ 425 383 iJ 719 693
3elt GrPart 89 89 JE 199 199 JE 349 353
uk AMG 19 19 JE 44 43 JE 86 96
add32 J2 10 10 JE 33 33 JE 69 66
bcsstk33 GrPart 10109 10097 iJ 21685 21662 iJ 35088 35063
whitaker3 JE 126 126 JE 380 383 JE 660 683
crack AMG 183 183 JE 368 367 NA 678 707
wingnodal MQI 1696 1704 JE 3572 3628 JE 5443 5747
fe4elt2 MRSB 130 130 JE 349 349 iJ 611 630
vibrobox JE 10310 11429 JE 19245 19418 iJ 25001 25604
bcsstk29 GrPart 2818 2818 MRSB 8786 8379 iJ 16505 14926
4elt GrPart 138 138 JE 327 327 JE 556 567
fesphere JE 386 386 NA 768 791 JE 1152 1256
cti JE 318 318 NA 967 948 JE 1812 1860
memplus JE 5492 5663 JE 9754 9792 iJ 11939 12582
cs4 JE 367 411 JE 940 1043 NA 1476 1693
bcsstk30 GrPart 6335 6335 NA 16622 16687 JE 34604 35372
bcsstk31 GrPart 2701 2703 pM4 7879 7554 pM4 14426 14193
bcsstk32 JE 4667 4799 JE 10578 9538 JE 22826 23537
t60k AMG 77 83 iJ 213 225 NA 467 506
wing MQI 787 896 JE 1666 1840 JE 2589 3001
brack2 GrPart 708 711 JE 3090 3102 JE 7269 7768
finan512 Ch2 162 162 Ch2 324 324 Ch2 648 648
fetooth SDP 3823 3946 iJ 7435 7433 iJ 12850 12725
ferotor GrPart 2049 2045 Ch2 8097 7795 iJ 14028 13786
598a MQI 2388 2423 NA 8311 8222 iJ 16594 17006
feocean GrPart 387 391 NA 1911 1878 NA 4760 4538
144 MQI 6479 6712 NA 15345 16046 NA 25818 27872
wave MQI 8682 8855 iJ 18058 17950 iJ 32204 31965
m14b MQI 3826 3902 JKM 13844 13430 pM4 28128 27815
Go back to the list of tables. Go back to the top of this page.

Table III: A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.03
Bal=1.03 k=2 k=4 k=8
Graph Algorithm Cut FF Algorithm Cut FF Algorithm Cut FF
add20 GCSVD 576 647 JE 1188 1187 iJ 1720 1793
data AMG 185 186 iJ 383 380 iJ 708 684
3elt JE 87 87 JE 199 199 JE 336 341
uk JE 18 18 JE 41 43 JE 82 94
add32 J2 10 10 JE 33 33 JE 69 66
bcsstk33 AMG 10064 10064 iJ 21423 21355 iJ 34322 34940
whitaker3 JE 126 126 JE 380 381 JE 658 677
crack AMG 182 182 JE 360 366 JE 676 704
wingnodal SDP 1680 1699 JE 3566 3628 JE 5401 5715
fe4elt2 MRSB 130 130 JE 349 349 JE 603 630
vibrobox JE 10310 11279 JE 19245 19398 JE 24874 25234
bcsstk29 GrPart 2818 2818 J2 8541 8237 iJ 16505 14868
4elt JE 137 137 NA 319 327 NA 527 558
fesphere JE 384 384 JE 766 791 JE 1152 1253
cti JE 318 318 JE 917 934 JE 1716 1818
memplus JE 5407 5574 JE 9664 9710 iJ 11939 12439
cs4 AMG 362 404 JE 936 1038 NA 1472 1682
bcsstk30 JE 6251 6251 JE 16617 16588 JE 34559 35299
bcsstk31 MLSATS 2676 2686 pM4 7879 7440 pM4 14426 14008
bcsstk32 JE 4667 4799 JE 9728 9533 JE 21307 23537
t60k AMG 71 74 iJ 211 216 NA 467 496
wing MQI 774 870 JE 1636 1838 JE 2551 3001
brack2 JE 684 684 JE 2864 2899 JE 7080 7519
finan512 Ch2 162 162 Ch2 324 324 Ch2 648 648
fetooth SDP 3792 3877 iJ 7435 7404 iJ 12850 12725
ferotor SDP 1965 1966 Ch2 8097 7636 iJ 14028 13588
598a MQI 2367 2403 NA 7978 8220 NA 16031 17006
feocean GrPart 311 312 NA 1704 1856 NA 4019 4538
144 MQI 6438 6712 NA 15250 16046 NA 25611 27872
wave SDP 8616 8851 iJ 18058 17599 iJ 30895 31311
m14b MQI 3823 3882 JKM 13844 13317 iJ 27711 27815
Go back to the list of tables. Go back to the top of this page.

Table IV: A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.05
Bal=1.05 k=2 k=4 k=8
Graph Algorithm Cut FF Algorithm Cut FF Algorithm Cut FF
add20 GCSVD 550 633 iJ 1184 1179 iJ 1705 1783
data SDP 181 184 iJ 378 375 iJ 702 669
3elt JE 87 87 JE 199 199 iJ 334 343
uk JE 18 18 JE 41 41 JE 82 93
add32 J2 10 10 JE 33 33 JE 69 65
bcsstk33 iJ 9914 9914 iJ 21229 21002 iJ 34117 34686
whitaker3 JE 126 126 JE 380 381 JE 658 677
crack AMG 182 182 JE 360 365 JE 676 703
wingnodal SDP 1668 1685 JE 3566 3628 MLSATS 5387 5687
fe4elt2 MRSB 130 130 JE 349 343 iJ 597 625
vibrobox JE 10310 11279 JE 19245 19167 iJ 24158 24894
bcsstk29 GrPart 2818 2818 MLSATS 8088 8148 MLSATS 15314 14645
4elt JE 137 137 NA 319 325 NA 527 551
fesphere JE 384 384 JE 766 791 JE 1152 1253
cti JE 318 318 JE 917 897 JE 1716 1787
memplus iJ 5353 5392 MLSATS 9427 9453 iJ 11939 12316
cs4 AMG 356 383 JE 936 1038 NA 1472 1682
bcsstk30 JE 6251 6251 JE 16617 16438 JE 34559 34806
bcsstk31 MLSATS 2676 2686 pM4 7879 7399 iJ 13561 13950
bcsstk32 JE 4667 4695 JE 9728 9052 JE 21307 23202
t60k SDP 65 67 iJ 211 211 NA 467 496
wing MQI 770 870 JE 1636 1838 JE 2551 3001
brack2 SDP 660 660 MLSATS 2808 2755 JE 7080 7505
finan512 Ch2 162 162 Ch2 324 324 Ch2 648 648
fetooth SDP 3773 3877 MLSATS 7152 7404 iJ 12646 12725
ferotor SDP 1957 1966 Ch2 8097 7520 iJ 13184 13588
598a MQI 2336 2366 NA 7978 8195 NA 16031 16942
feocean GrPart 311 312 NA 1704 1822 NA 4019 4433
144 SDP 6362 6689 NA 15250 16046 NA 25611 27872
wave MQI 8563 8777 iJ 18058 17320 MLSATS 30583 31207
m14b MQI 3802 3878 JKM 13844 13317 iJ 27711 27815
Go back to the list of tables. Go back to the top of this page.

Go back to Charles-Edmond Bichot's home page
Last Update: 2007-07-12

[LOG Home]
[The Lab] [Research topics] [Publications] [Software]
[Partnerships] [Addresses] [Gamezone]
Contact .

Valid XHTML 1.1! Valid CSS!