A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR THE 2-PARTITION PROBLEM

被引：29

作者：

LAGUNA, M

FEO, TA

ELROD, HC

机构：

[1] UNIV TEXAS,AUSTIN,TX 78712

[2] PRINCETON TRANSPORTAT CONSULTING GRP INC,BURLINGTON,MA

来源：

OPERATIONS RESEARCH | 1994年 / 42卷 / 04期

关键词：

D O I：

10.1287/opre.42.4.677

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：677 / 687

页数：11