Titre du document / Document title

Variable neighborhood search for the linear ordering problem

Auteur(s) / Author(s)

GARCIA Carlos G. ⁽¹⁾ ; PEREZ-BRITO Dionisio ⁽¹⁾ ; CAMPOS Vicente ⁽²⁾ ; MARTI Rafael ⁽²⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Departamento de Economía de las Instituciones, Estadistica Económica, Universidad de La Laguna, ESPAGNE
⁽²⁾ Departamento de Estadistica e Investigacion Operativa, Universitat de València,C/Dr. Moliner 50, 46100 Burjassot, Valencia, ESPAGNE

Résumé / Abstract

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements. Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum. In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search.

Revue / Journal Title

Computers & operations research   ISSN 0305-0548   CODEN CMORAP 

Source / Source

2006, vol. 33, n^o12, pp. 3549-3565 [17 page(s) (article)] (15 ref.)

Langue / Language

Anglais

Editeur / Publisher

Elsevier, Oxford, ROYAUME-UNI  (1974) (Revue)

Mots-clés anglais / English Keywords

Hybridization ; Economics ; Input output ; Triangulation ; NP hard problem ; Global optimum ; Random search ; Local search ; Combinatorial problem ; Combinatorial optimization ; Tabu search ; Short term ; Hybrid model ; Search strategy ; Heuristic method ; Weighted graph ; Complete graph ; Tournament ; Acyclic graph ; NP complete problem ; Permutation ; Ordering ;

Mots-clés français / French Keywords

. ; Hybridation ; Sciences économiques ; Entrée sortie ; Triangulation ; Problème NP difficile ; Optimum global ; Recherche aléatoire ; Recherche locale ; Problème combinatoire ; Optimisation combinatoire ; Recherche tabou ; Court terme ; Modèle hybride ; Stratégie recherche ; Méthode heuristique ; Graphe pondéré ; Graphe complet ; Tournoi ; Graphe acyclique ; Problème NP complet ; Permutation ; Relation ordre ;

Mots-clés espagnols / Spanish Keywords

Hibridación ; Ciencias económicas ; Entrada salida ; Triangulación ; Problema NP duro ; Optimo global ; Investigación aleatoria ; Busca local ; Problema combinatorio ; Optimización combinatoria ; Búsqueda tabú ; Corto plazo ; Modelo híbrido ; Estrategia investigación ; Método heurístico ; Grafo pondero ; Grafo completo ; Torneo ; Grafo acíclico ; Problema NP completo ; Permutación ; Relación orden ;

Mots-clés d'auteur / Author Keywords

Combinatorial optimization ; Metaheuristics ; Linear ordering problem ;

Localisation / Location

INIST-CNRS, Cote INIST : 16412, 35400015665673.0130