Journal
OPTIMIZATION METHODS & SOFTWARE
Volume 17, Issue 6, Pages 1033-1058Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/1055678021000090033
Keywords
MAX-CUT; GRASP; variable neighborhood search; path-relinkings; metaheuristics
Ask authors/readers for more resources
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 article, 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available