For a given graph G with vertex and edge weights, the authors partition the vertices into subsets to minimize the total weights for edges crossing the subsets under the constraint that the vertex weights are evenly distributed among the subsets. They adapt simulated annealing and tabu search to solve this problem based on a unique solution neighborhood design compromising aggressiveness and running time for each move. A new general optimization paradigm called stochastic probe is then proposed to integrate the advantages of both the aggressive searches and the stochastic searches. Extensive experimental study shows that all of the present three new algorithms produce significantly better solutions than the LPK algorithm, and the stochastic probe algorithm always produces the best solution among all the four algorithms with a running time comparable with that for the LPK algorithm.
