Show simple item record

dc.contributor.authorCeberio Uribe, Josu ORCID
dc.contributor.authorMendiburu Alberro, Alexander ORCID
dc.contributor.authorLozano Alonso, José Antonio ORCID
dc.date.accessioned2014-01-08T14:38:47Z
dc.date.available2014-01-08T14:38:47Z
dc.date.issued2014-01-08T14:38:47Z
dc.identifier.urihttp://hdl.handle.net/10810/11178
dc.description.abstractThe Linear Ordering Problem is a popular combinatorial optimisation problem which has been extensively addressed in the literature. However, in spite of its popularity, little is known about the characteristics of this problem. This paper studies a procedure to extract static information from an instance of the problem, and proposes a method to incorporate the obtained knowledge in order to improve the performance of local search-based algorithms. The procedure introduced identifies the positions where the indexes cannot generate local optima for the insert neighbourhood, and thus global optima solutions. This information is then used to propose a restricted insert neighbourhood that discards the insert operations which move indexes to positions where optimal solutions are not generated. In order to measure the efficiency of the proposed restricted insert neighbourhood system, two state-of-the-art algorithms for the LOP that include local search procedures have been modified. Conducted experiments confirm that the restricted versions of the algorithms outperform the classical designs systematically. The statistical test included in the experimentation reports significant differences in all the cases, which validates the efficiency of our proposal.es
dc.language.isoenges
dc.relation.ispartofseriesEHU-KZAA-TR;2014-01
dc.rightsinfo:eu-repo/semantics/openAccesses
dc.subjectcombinatorial optimisationes
dc.subjectlinear ordering problemes
dc.subjectlocal optimaes
dc.subjectinsert neighbourhoodes
dc.titleThe Linear Ordering Problem Revisitedes
dc.typeinfo:eu-repo/semantics/reportes
dc.departamentoesCiencia de la computación e inteligencia artificiales_ES
dc.departamentoeuKonputazio zientziak eta adimen artifizialaes_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record