A Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem

Manuel Laguna, Thomas A. Feo and Hal C. Elrod
Additional contact information
Manuel Laguna: University of Colorado, Boulder, Colorado
Thomas A. Feo: University of Texas, Austin, Texas
Hal C. Elrod: Princeton Transportation Consulting Group, Inc., Burlington, Massachusetts

Operations Research, 1994, vol. 42, issue 4, 677-687

Abstract: 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.

Keywords: networks/graphs; applications: two-partition problem; networks/graphs; heuristics: greedy randomized adaptive search procedures (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.4.677 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:4:p:677-687

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().