ITERATED GREEDY PARA EL PARTIAL SET COVERING PROBLEM

Abstract

La optimización combinatoria es fundamental para resolver problemas complejos en diversas áreas. Los problemas de cobertura, como el clásico Problema de Cobertura de Conjuntos (SCP, del inglés Set Covering Problem), han sido extensamente estudiados. Sin embargo, exigir una cobertura total es a menudo inviable o ineficiente en aplicaciones del mundo real. El Problema de Cobertura Parcial de Conjuntos (PSCP) surge como una variante más flexible y práctica, buscando minimizar el número de subconjuntos necesarios para cubrir un umbral mínimo de elementos.

Este Trabajo de Fin de Grado aborda el PSCP, un problema NP-duro, mediante el diseño, implementación y validación empírica de una metaheurística basada en la estrategia Iterated Greedy (IG), hibridada con Búsqueda de Vecindad Variable Descendente (VND).