logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro