2026-07-23T05:17:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22257 2024-12-05T15:32:41Z ddc:004 open_access

PACE Solver Description: CIMAT_Team Segura, Carlos Lugo, Lázaro Miranda, Gara Serrano Cárdenas, Edison David Memetic Algorithms Diversity Management One-sided Crossing Minimization This document describes MAEDM-OCM, a first generation memetic algorithm for the one-sided crossing minimization problem (OCM), which obtained the first position at the heuristic track of the Parameterized Algorithms and Computational Experiments Challenge 2024. In this variant of OCM, given a bipartite graph with vertices V = A ∪ B, only the nodes of the layer B can be moved. The main features of MAEDM-OCM are the following: the diversity is managed explicitly through the Best-Non-Penalized (BNP) survivor strategy, the intensification is based on Iterated Local Search (ILS), and the cycle crossover is applied. Regarding the intensification step, the neighborhood is based on shifts and only a subset of the neighbors in the local search are explored. The use of the BNP replacement was key to attain a robust optimizer. It was also important to incorporate low-level optimizations to efficiently calculate the number of crossings and to reduce the requirements of memory. In the case of the longest instances (|B| > 17000) the memetic approach is not applicable with the time constraints established in the challenge. In such cases, ILS is applied. The optimizer is not always applied to the original graph. In particular, twin nodes in B are grouped in a single node. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carlos Segura and Lázaro Lugo and Gara Miranda and Edison David Serrano Cárdenas 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.31 urn:nbn:de:0030-drops-222577 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode