Resumen: Los algoritmos exactos eficientes para la optimización discreta (DO) dependen en gran medida de fuertes límites primarios y duales. Los diagramas de decisión relajados (DD) proporcionan un mecanismo versátil para derivar dichos límites duales sobreaproximando de forma compacta el espacio de la solución mediante la fusión de nodos. Sin embargo, la calidad de estos diagramas relajados, es decir, la rigidez de los límites duales resultantes, depende críticamente del ordenamiento de las variables y de las decisiones de fusión ejecutadas durante la compilación. Si bien las heurísticas dinámicas de ordenación de variables efectivamente ajustan los límites, a menudo incurren en una sobrecarga computacional cuando se evalúan globalmente en todo el conjunto de variables. Para mitigar esta compensación, este trabajo presenta un novedoso marco basado en agrupaciones para el ordenamiento de variables. En lugar de aplicar heurísticas de ordenamiento dinámico al conjunto completo de variables no fijadas, primero dividimos las variables en grupos. Luego aprovechamos esta descomposición estructural para guiar el proceso de pedido, reduciendo significativamente el espacio de búsqueda de la heurística. Dentro de este marco, investigamos dos estrategias distintas: Cluster-to-Cluster, que procesa clusters secuencialmente utilizando criterios agregados específicos del problema (como ponderaciones acumulativas de vértices en el Problema de conjunto independiente ponderado máximo (MWISP)), y Pick-and-Sort, que selecciona y clasifica iterativamente variables representativas de cada cluster para equilibrar la diversidad local con guía heurística. Posteriormente, desarrollando algunos resultados teóricos sobre el crecimiento del tamaño de los DD para MWISP, proponemos dos políticas diferentes para establecer el número de clusters dentro del marco propuesto. Incorporamos estas estrategias en un algoritmo de ramificación y enlace basado en DD y las evaluamos en el MWISP. En todas las instancias de referencia, la metodología propuesta reduce consistentemente los costos computacionales en comparación con la línea base de ordenación de variables dinámicas estándar.
Publicado originalmente en export.arxiv.org el 18 de diciembre de 2025.
Ver fuente original
