Advanced Scatter Search for the Max-Cut Problem

Advanced Scatter Search for the Max-Cut Problem

0.00 Avg rating0 Votes
Article ID: iaor200952646
Country: United States
Volume: 21
Issue: 1
Start Page Number: 26
End Page Number: 38
Publication Date: Dec 2009
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: networks, heuristics
Abstract:

The max–cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP–hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter–search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter–search framework: (1) the solution of the maximum diversity problem to increase diversity in the reference set, (2) a dynamic adjustment of a key parameter within the search, and (3) the adaptive selection of a combination method. We perform extensive computational experiments to first study the effect of changes in critical scatter–search elements and then to compare the efficiency of our proposal with previous solution procedures.

Reviews

Required fields are marked *. Your email address will not be published.