Resumen

Presentamos enfoques exactos de programación entera mixta, incluyendo branch-and-cut y branch-and-cut-and-price para el problema del árbol de extensión de etiqueta mínima, así como una variante del mismo que tiene múltiples etiquetas asignadas a cada arista. Comparamos formulaciones basadas en flujos de red y cortes de conectividad dirigidos. Además, mostramos cómo utilizar desigualdades de agujeros impares y desigualdades adicionales para reforzar la formulación. Las variables de etiqueta pueden añadirse dinámicamente al modelo en el paso de fijación de precios. Se incorporan heurísticas primarias en el marco para acelerar el proceso de solución global. Tras una comparación poliédrica de las formulaciones implicadas, se presentan amplios experimentos computacionales para comparar y evaluar las formulaciones subyacentes y los bloques algorítmicos particulares del marco general de rama y corte (y precio).

• Materias:Algoritmos (Computadores) Lenguajes de programación (Computadores electrónicos) Algoritmos (Matemáticas) Matemáticas Redes multiclase
• Subjects:Computer algorithms Programming languages (Computer electronics) Agorithms (Math) mathematics Multiclass Networks
• Palabras claves:bloque de construcción algorítmica, formulación, proceso de soluciones globales, corte de conectividad dirigido, entero mixto exacto, enfoque de programación entera, experimento computacional integral, flujo de red, heurística primal, etiqueta mínima
• Keywords:algorithmic building block, formulation, overall solutions process, directed connectivity cut, exact mixed integer, integer programming approach, comprehensive computational experiment, network flow, primal heuristic, minimum label