Çizge bölümleme problemi için eniyileme tabanlı sezgisel yöntemler

The graph partitioning problem is concerned with partitioning the vertices of a graph into a prespecified number of clusters with given cardinalities so as to minimize the total weight of the edges that have two endpoints in different clusters. This problem has numerous applications in various fields, including parallel processing, power grids, social networks, biomedical networks, and VLSI design. Our focus in this study is on heuristic methods that yield good feasible solutions in a reasonable amount of time, especially for large-scale instances. Our heuristic methods are based on optimal solutions of linear programming relaxations of different integer linear programming formulations of the graph partitioning problem. In particular, these formulations employ binary variables for determining the assignment of each vertex to each cluster. We treat the optimal value of the relaxed version of each of these binary assignment variables as a measure of the likelihood of the assignment of each vertex to each cluster. Using this approach, we propose two different heuristic methods. In the first method, we aim to compute a good feasible solution of the graph partitioning problem by solving another linear programming problem whose parameters are given by the optimal values of the binary assignment variables in the linear programming relaxation of the original problem. The second method is a randomized algorithm, in which we treat the optimal value of each binary assignment variable in the original linear programming relaxation as a probability measure. We randomly assign each vertex to each cluster using the corresponding probabilities without taking into consideration the cardinality constraint on each cluster. We then apply a greedy feasibility restoration procedure in an attempt to satisfy the cardinality constraints of clusters. Since the quality of the final solutions heavily depends on the quality of the linear programming relaxation of the original integer linear programming problem, we consider adding several classes of valid inequalities in an attempt to strengthen the linear programming relaxation. We perform computational experiments on several classes of randomly generated graphs with different characteristics. In particular, we study the effects of different formulations and different valid inequalities on the quality of the resulting feasible solutions computed by our heuristic methods. We also compare the performance of our heuristic methods with the well-known Kernighan-Lin heuristic method (KL method). Our computational results reveal that our methods usually take considerably less CPU time than the KL method. For very large instances, solving the linear programming relaxation becomes a computational bottleneck. While our heuristic methods, in general, do not seem to outperform the KL method in terms of the solution quality, using the solutions generated by our heuristic methods as initial solutions for the KL method has the potential to lead to further improvements on several instances.