Búsqueda de vecindad variable para el problema de la minimización del número de errores en ordenaciones líneales

Abstract

El problema de la minimizaci´on del n´umero de errores en ordenaciones lineales se define como un problema sobre un grafo con signos, donde las aristas est´an etiquetadas con signos positivos y negativos. De manera general, el objetivo del problema consiste en encontrar una ordenaci´on lineal, que sit´ue a cada v´ertice lo m´as cerca posible de sus v´ertices adyacentes con conexiones positivas y lo m´as lejos posible de sus v´ertices adyacentes con conexiones negativas. Espec´ıficamente, la funci´on objetivo tratar´a de minimizar el n´umero de conexiones negativas situadas antes que una conexi´on positiva. En este trabajo, se propone un algoritmo basado en la metodolog´ıa B´usqueda de Vecindad Variable, particularmente en la variante B´asica, para abordar el problema. El algoritmo propuesto ha sido comparado sobre diversos conjuntos de instancias y resulta competitivo con m´etodos previos en el estado del arte.

Abraham Duarte

Full Professor

Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.