Using pairwise precedences for solving the linear ordering problem

Valentino Santucci

doi:10.1016/j.asoc.2019.105998

2020-02-01

PRE

Valentino Santucci *

Josu Ceberio

DOI：10.1016/j.asoc.2019.105998

原文链接

原文求助

摘要

En 中文

It is an old claim that, in order to design a (meta)heuristic algorithm for solving a given optimization problem, algorithm designers need first to gain a deep insight into the structure of the problem. Nevertheless, in recent years, we have seen an incredible rise of new meta-heuristic paradigms that have been applied to any type of optimization problem without even considering the features of these problems. In this work, we put this initial claim into practice and try to solve a classical permutation problem: the Linear Ordering Problem (LOP). To that end, first, we study the structure of the LOP by focusing on the relation between the pairwise precedences of items in the solution and its objective value. In a second step, we design a new meta-heuristic scheme, namely CD-RVNS, that incorporates critical information about the problem in its three key algorithmic components: a variable neighborhood search algorithm, a construction heuristic, and a destruction procedure. Conducted experiments, on the most challenging LOP instances available in the literature, reveal an outstanding performance when compared to existing algorithms. Moreover, we also demonstrate (experimentally) that the developed heuristic procedures perform individually better than their state-of-the-art counterparts. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Linear ordering problem

Variable neighborhood search

Construction heuristic

Precedences