Problem description
Given a graph G=(V, E), where V is the set of vertex and E the set of edges
that determines the connectivity between the nodes. Both vertex and edges
can be weighted, where |v| is the weight of a vertex v, and
|e| is the weight of edge e. Then, the graph partitioning
problem consists on dividing G into k disjoint partitions. The goal
is minimize the number of cuts in the edges of the partition, and on the
other hand reduce the imbalance of the weight of the subdomains. The weight
of a subdomain is the sum of the weights of the vertex allocated in it.
All the graphs listed later have |v|=1 for all v in V and
|e|=1 for all e in E.
Our algorithm : MLrMSATS (MultiLevel refinated Mixed Simulated Anealing
and Tabu Search)
We have designed a new algorithm for graph partitioning that mixes the
multilevel paradigm with an hybrid heuristic based in Simulated Annealing
and Tabu Search. Results obtained indicate the good behaviour of our algorithm,
which can be compared with other software
for graph partitioning.You can download the executable file of our algorithm
(here).The execution must be performed under linux
with the syntax:
$ ./MLrMSATS graph_file k_partitions
During and after the execution, the algorithm return some statistics of
the partitioning proccess. Furthermore, it also gives two output files, Location_graph_k.dat
and Weight_graph_k.dat. Location_graph_k.dat is a file
that indicates the partition a vertex belongs to in graph (in the same format
as graph input file). Weight_graph_k.dat indicates the total weight
of the k partitions after the partitioning.
Graphs used to make the partitions, so as the best known solutions found
for them, can be downloaded from Walshaw
web page. Nevertheless, we list some of them.
|
Graph
|
|V|
|
|E|
|
min
|
Max
|
avg
|
File Size (KB)
|
|
add20
|
2395
|
7462
|
1
|
123
|
6.23
|
63
|
|
data
|
2851
|
15093
|
3
|
17
|
10.59
|
140
|
|
3elt
|
4720
|
13722
|
3
|
9
|
5.81
|
136
|
|
add32
|
4960
|
9462
|
1
|
31
|
3.82
|
90
|
|
wing_nodal
|
10937
|
75488
|
5
|
28
|
13.80
|
768
|
|
bcsstk29
|
13992
|
302748
|
4
|
70
|
43.27
|
1679
|
|
fe_sphere
|
16386
|
49152
|
4
|
6
|
6.00
|
540
|
|
cti
|
16840
|
48232
|
3
|
6
|
5.73
|
532
|
|
memplus
|
17758
|
54196
|
1
|
573
|
6.10
|
536
|
|
bcsstk31
|
35588
|
572914
|
1
|
188
|
32.2
|
6547
|
|
brack2
|
62631
|
366559
|
3
|
32
|
11.71
|
4358
|
|
finan512
|
74752
|
261120
|
2
|
54
|
6.99
|
3128
|
|
fe_tooth
|
78136
|
452591
|
3
|
39
|
11.58
|
5413
|
|
598a
|
110971
|
741934
|
5
|
26
|
13.37
|
9030
|
|
wave
|
156317
|
1059331
|
3
|
44
|
13.55
|
13479
|
|
m14b
|
214765
|
1679018
|
4
|
40
|
15.64
|
21996
|
where :
|V| : Total number
of vertex of the graph.
|E| : Total number
of edges of the graph.
Max : Number
of neighbors of the vertex with the highest neighborhood (most connected
vertex).
min : Number
of neighbors of the vertex with the lowest neighborhood (less connected
vertex).
Avg : Average connectivity
of the graph.
File Size : Size
of the file that describes the graph (in KB).
Our publications related with circuit and graph partitioning
References
-
B.W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning
Graphics”, The Bell Sys. Tech.a Journal, vol. 49, no.2, pp. 291-307, 1970.
-
C. Fiduccia and R. Mattheyses, “A Linear Time Heuristic for Improving Network
Partitions”, In Proc. 19th ACM/IEEE Design Automation Conference, 175-181,
1982.
-
K. A. Dowsland, "Simulated Annealing", in: C.R. Reeves (eds.), Modern Heuristic
Techniques for Combinatorial Problems, Blackwell, London, pp. 20-69, 1993.
-
F. Glover and M. Laguna, “Tabu Search”, C.R. Reeves (ed.), Modern Heuristic
Techniques for Combinatorial Problems, Blackwell Scientific Publications,
Oxford, pp. 70-150, 1993.
-
G. Karypis and V. Kumar, “Multilevel K-way Partitioning Scheme for Irregular
Graphs”. Journal of Parallel and Distributed Computing”, vol. 48, no. 1,
pp. 96-129, 1998.
-
C. Walshaw and M. Cross, “Mesh Partitioning: a Multilevel Balancing and
Refinement Algorithm”, SIAM J. Sci. Comput., vol. 22 , no. 1, pp. 63-80,
2000.
-
K. Schloegel, G. Karypis and V. Kumar, “Graph Partitioning for High Performance
Scientific Simulations”, CRPC Parallel Computing Handbook, Morgan Kaufmann
2000.
-
A. J. Soper, C. Walshaw and M. Cross, “A Combined Evolutionary Search and
Multilevel Optimisation Approach to Graph Partitioning”, Mathematics Research
Report 00/IM/58, University of Greenwich, 2000.
-
C. Gil, J. Ortega, M.G. Montoya, R. Baños: "A Mixed Heuristic for
Circuit Partitioning". Computational Optimization and Applications Journal.
23/2 (2002) pp.321-340.
-
R. Baños, C. Gil, J. Ortega, M.G. Montoya: "A Parallel Evolutionary
Algorithm for Circuit Partitioning". 11th Euromicro Workshop on Parallel
and Distributed Processing. Published by the IEEE Computer Society Press.
Genova (IT), February 2003. (pdf)
-
R. Baños, C. Gil, J. Ortega, F.G. Montoya: "Multilevel Heuristic
Algorithm for Graph Partitioning". 3rd European Workshop on Evolutionary
Computation in Combinatorial Optimization. Published by LNCS. Essex (UK),
April 2003. (abstract)
Graph Partitioning Links
METIS : Family of programs for partitioning
unstructured graphs and hypergraphs.
JOSTLE : Software package designed to partition
unstructed meshes for use on distributed memory parallel computers. It can also be used to repartition existing partitions.
CHACO : Algorithms to assign task to different processors in parallel
computation (load balancing).
SCOTCH : Static mapping, graph partitioning, and sparse matrix
block ordering package.
cgil@ace.ual.es