.png){kind=icon}
.png){kind=icon}
Return
Block-insertion-based algorithms for the linear ordering problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2019.104861.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The linear ordering problem (LOP) is an NP-hard combinatorial optimization problem with wide applications. As the problem is computationally intractable, the only practical alternative is to develop efficient heuristics to solve it. Here we present four new properties of block insertion for the LOP, and show that changing the node order in one sub-problem does not affect the objective values of the remaining sub-problems. Based on these properties, we then propose three local search schemes for solving the LOP. Our experimental results show that the block insert with the first strategy often outperforms other local search schemes within the same computational time. To further improve the performance of this local search scheme, we incorporate it into the iterated local search and genetic algorithm frameworks, and develop the block-insertion-based iterated local search (ILSb) and memetic algorithm (MA(b)), respectively. The computational results show that both the ILSb and MA(b) outperform the state-of-the-art meta-heuristics. Moreover, with appropriate parameter settings, the MA(b) frequently outperforms the ILSb. Finally, we design a parallel computing framework, which divides the LOP problem into independent subproblems that are solved in parallel by exact methods. This parallel framework can further improve the solutions derived by MAb or other heuristics. (C) 2019 Elsevier Ltd. All rights reserved.
Keywords:
Linear ordering problem
Block insertion
Iterated local search
Memetic algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W