Un eficiente modelo de programación lineal entera mixta para el problema del árbol de expansión mínimo
Autores: Abdelmaguid, Tamer F.
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Un eficiente modelo de programación lineal entera mixta para el problema del árbol de expansión mínimo
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
árbol de expansión mínima
Problema de optimización combinatoria
Modelos de programación matemática
Programación lineal entera y mixta
Modelos MILP
Comparaciones computacionales
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 37
Citaciones: Sin citaciones
Encontrar un árbol de expansión mínimo en una red dada es un famoso problema de optimización combinatoria que aparece en diferentes aplicaciones de ingeniería. Aunque este problema es soluble en tiempo polinómico, tener modelos eficientes de programación matemática es importante, ya que pueden proporcionar ideas para formular modelos más grandes que integren otras decisiones en aplicaciones más complejas. En la literatura, hay diez modelos diferentes de programación lineal entera e mixta (MILP) para este problema. Son variantes de empaquetamiento de conjuntos, cortes, flujo de red y formulaciones a nivel de nodo. Además, este artículo introduce un modelo eficiente de MILP a nivel de nodo. Se proporcionan comparaciones de los once modelos. Primero, los modelos se comparan en términos del número de variables de decisión y el número de restricciones. Luego, se realizan comparaciones computacionales utilizando un solucionador MILP comercial en conjuntos de instancias generadas aleatoriamente de diferentes tamaños. Los resultados proporcionan evidencia de que el modelo MILP propuesto es competitivo en términos del tiempo computacional necesario para demostrar la optimalidad de las soluciones generadas para instancias con hasta 50 nodos. Mientras tanto, la relajación LP de un modelo MILP de flujo multicommodity que tiene politopo entero proporciona tiempos computacionales estables a pesar de su mayor tamaño.
Descripción
Encontrar un árbol de expansión mínimo en una red dada es un famoso problema de optimización combinatoria que aparece en diferentes aplicaciones de ingeniería. Aunque este problema es soluble en tiempo polinómico, tener modelos eficientes de programación matemática es importante, ya que pueden proporcionar ideas para formular modelos más grandes que integren otras decisiones en aplicaciones más complejas. En la literatura, hay diez modelos diferentes de programación lineal entera e mixta (MILP) para este problema. Son variantes de empaquetamiento de conjuntos, cortes, flujo de red y formulaciones a nivel de nodo. Además, este artículo introduce un modelo eficiente de MILP a nivel de nodo. Se proporcionan comparaciones de los once modelos. Primero, los modelos se comparan en términos del número de variables de decisión y el número de restricciones. Luego, se realizan comparaciones computacionales utilizando un solucionador MILP comercial en conjuntos de instancias generadas aleatoriamente de diferentes tamaños. Los resultados proporcionan evidencia de que el modelo MILP propuesto es competitivo en términos del tiempo computacional necesario para demostrar la optimalidad de las soluciones generadas para instancias con hasta 50 nodos. Mientras tanto, la relajación LP de un modelo MILP de flujo multicommodity que tiene politopo entero proporciona tiempos computacionales estables a pesar de su mayor tamaño.