Metaheuristics for large-scale instances of the linear ordering problem

• ILS and GDA metaheuristics for the linear ordering problem are introduced.
• They are able to tackle large instances in line with real applications.
• Introduced methods are the first of their kind ever applied to large-sized instances.
• All best known solutions of the large-sized instances are improved.

This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura (2010) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances.