In a discrete balanced graph partitioning problem (DBGPP), a simple undirected weighted graph in that both vertices and edges are weighted is given. The task is dividing vertices into two disjoint subsets such that the sum of the weights of cut edges is minimized and the sum of the weights of vertices in each subset must equal or be as close as possible to each other. Here in order to solve the DBGPP, we first transform the problem into continuous quadratic programming and then show that the new problem has a binary solution, which is the optimal solution for the DBGPP. We also give necessary and sufficient conditions of continuous quadratic programming to identify stationary and local optimal solutions. In addition, we propose a local search to find a binary solution of the continuous quadratic programming. An approximated solution of the DBGPP is obtained using a hybrid simulated annealing algorithm. In our proposed algorithm, the structure of the objective function in a continues problem is considered as the evaluator function. Due to the Dolan–Moré performance profiles and the non-parametric statistical one-sided Wilcoxon signed rank test, we demonstrate the efficiency of our proposed approach in comparison with other available methods.

Keywords