A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR THE 2-PARTITION PROBLEM
成果类型：
Article
署名作者：
LAGUNA, M; FEO, TA; ELROD, HC
署名单位：
University of Texas System; University of Texas Austin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.4.677
发表日期：
1994
页码：
677-687
关键词：
摘要：
We present a greedy randomized adaptive search procedure (GRASP) for the network 2-partition problem. The heuristic is empirically compared with the Kernighan-Lin (K&L) method on a wide range of instances. The GRASP approach dominates K&L with respect to solution value on a large percentage of the instances tested. The ability of GRASP to find optimal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.