GRASP and path relinking for 2-layer straight line crossing minimization

in this article, we develop a greedy randomized adaptive search procedure ( GRASP) for the problem of minimizing straight line crossings in a 2-layer g raph. The procedure is fast and is particularly appealing when dealing with low-density graphs. When a modest increase in computational time is allowe d, the procedure may be coupled with a path relinking strategy to search fo r improved outcomes. Although the principles of path relinking have appeare d in the tabu search literature, this search strategy has not been fully im plemented and tested. We perform extensive computational experiments with m ore than 3,000 graph instances to first study the effect of changes in crit ical search parameters and then to compare the efficiency of alternative so lution procedures. Our results indicate that graph density is a major influ ential factor on the performance of a solution procedure.