Optimization Methods and Software, vol. 7, pp. 1033-1058, 2002
ABSTRACT
Given an undirected graph with edge weights, the
MAX-CUT problem consists in finding a partition of the nodes into two
subsets, such that the sum of the weights of the edges having endpoints
in different subsets is maximized. It is a well-known NP-hard
problem with applications in several fields, including VLSI design and
statistical physics. In this paper, a greedy randomized adaptive
search procedure (GRASP), a variable neighborhood search (VNS), and a
path-relinking (PR) intensification heuristic for MAX-CUT are proposed
and tested. New hybrid heuristics that combine GRASP, VNS, and PR
are also proposed and tested. Computational results indicate that these
randomized heuristics find near-optimal solutions. On a set of
standard test problems, new best known solutions were produced for many
of the instances.