.png){kind=icon}
.png){kind=icon}
Return
Using pairwise precedences for solving the linear ordering problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2019.105998.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Linear ordering problem
Variable neighborhood search
Construction heuristic
Precedences
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W