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

Authors
LAGUNA M FEO TA ELROD HC
Citation
M. Laguna et al., A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR THE 2-PARTITION PROBLEM, Operations research, 42(4), 1994, pp. 677-687
Citations number
22
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
42
Issue
4
Year of publication
1994
Pages
677 - 687
Database
ISI
SICI code
0030-364X(1994)42:4<677:AGRASP>2.0.ZU;2-G
Abstract
We present a greedy randomized adaptive search procedure (GRASP) for t he 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 opti mal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.