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.

Using pairwise precedences for solving the linear ordering problem

Santucci, Valentino;
2020-01-01

Abstract

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.
Linear ordering problem; Variable neighborhood search; Construction heuristic; Precedences
File in questo prodotto:
File Dimensione Formato  
_ASOC__REVISION__Using_Pairwise_Precedences_for_Solving_the_Linear_Ordering_Problem.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 592.63 kB
Formato Adobe PDF
592.63 kB Adobe PDF Visualizza/Apri
asoc2020.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: NON PUBBLICO - Accesso chiuso
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12071/15967
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact