A PROBE-based algorithm for the max-cut problem

The max-cut problem is a classical combinatorial optimization problem. This paper uses a Population Reinforced Optimization Based Exploration (PROBE) as a framework for developing metaheuristic algorithm for solving the max-cut problem. A solution is constructed by a greedy construction method, then a local search procedure, which is based on the Fiduccia and Mattheyses heuristic, is used to improve the solution. Experimental tests are done on some instances taken from the literature. The experiment results and comparisons show that the proposed algorithm is efficient for these tested benchmarks.