Algoritmos para el problema de árbol de expansión mínima robusto con datos intervalares

UNIVERSIDAD DE TALCA

FACULTAD DE INGENIERÍA

ALGORÍTMOS PARA EL PROBLEMA DEL ÁRBOL

DE EXPANSIÓN ROBUSTO CON INCERTIDUMBRE

INTERVALAR

TESIS PARA OPTAR AL GRADO DE MAGÍSTER EN GESTIÓN DE OPERACIONES

Por

FRANCISCO JAVIER PÉREZ GALARCE

COMISIÓN INTEGRADA POR LOS PROFESORES:

Dr. Alfredo Candia Véjar Dr. Fernando Paredes Cajas

Dr. Rodrigo Herrera Leiva

Marzo, 2013

CURICÓ – CHILE

vi

vii

Esta tesis está dedicada a:

Las dos mujeres que me toleraron y acompañaron durante este proceso de intenso trabajo; Soledad Miranda y Francisca Pérez.

viii

Agradecimientos

A toda mi familia, la cual me ha apoyado en cada paso que he dado en mi vida. En especial a "mi

amor" Soledad y "mi pequeña" Francisca; por su amor, apoyo y comprensión.

A mi maestro Alfredo Candia, por su apoyo, motivación y confianza desde que comenzó mi

proceso de magister.

A Eduardo Álvarez, por ser mi compañero en este trabajo, brindarme su ayuda y apoyo, incluso

desde la distancia.

A mis compañeros de magister y pregrado, todos sin distinción son excelentes profesionales y aún

mejores personas.

ix

Resumen

Esta tesis aborda el Problema Árbol de Expansión con incertidumbre intervalar en los costos,

utilizando el criterio de Min-Max Regret.

Varios algoritmos son implementados, tanto exactos como heurísticos. Con respecto a los

algoritmos exactos, se implementan Descomposición de Benders y Branch and Cut, ambos

incluyen variantes. Branch and Cut logra superar al resto de los algoritmos, incluso obteniendo

gaps menores a un 10%, para 100 nodos, en un conjunto de instancias. En relación a las

heurísticas, se desarrolla una heurística constructiva, la que utiliza la información de los intervalos,

a diferencia de todas las aproximaciones de la literatura. Se proponen metaheurísticas basadas en

Búsqueda Local (Mejora iterativa, Simulated Annealing y GRASP), se obtienen gaps de calidad,

incluso para las instancias más complejas.

Se realiza una comparación desde un punto de vista experimental, mostrando un buen

desempeño, pues se igualan o mejoran los resultados existentes.

Palabras clave: Incertidumbre, Min-Max Regret, Árbol de expansión.

Abstract

This thesis addresses The Robust Spanning Tree Problem with interval uncertainty in data costs,

using the Min-Max Regret criterion.

Several algorithms are implemented, both exact as heuristic. With respect to exact algorithms are

implemented Benders decomposition and Branch and Cut, and both include some variants. Branch

and Cut can ourperform the rest of the algorithms, obtaining gaps below 10% for instances with 100

nodes in a set of instances. In relation to heuristics, a constructive heuristic is developed, which

uses the information of the intervals, and different to the known approaches from the literature, that

only work with scenarios. Metaheuristics based on Local Search (iterative improvement, simulated

annealing and GRASP) are proposed and they got quality gap, even for more complex instances .

A comparison is made from an experimental point of view, showing a good performance, improving

existing results for some group of instances.

Key Words: Uncertainty, Min-Max Regret, Spanning Tree.

x

ÍNDICE

CAPÍTULO I: INTRODUCCIÓN ...................................................................................................................... 14

1.1 Contextualización .............................................................................................................. 15

1.2 Manejo de Incertidumbre ................................................................................................... 17

1.3 Objetivos ............................................................................................................................ 18

1.3.1 Objetivos específicos ..................................................................................................... 18

1.4 Estructura de la tesis ......................................................................................................... 19

CAPÍTULO II: MODELO MINMAX REGRET ................................................................................................... 20

2.1 Descripción General .......................................................................................................... 21

2.2 Modelo Min-Max Regret ................................................................................................... 22

CAPÍTULO III: MIN-MAX REGRET SPANNING TREE ..................................................................................... 28

3.1 Formulaciones para MST ................................................................................................. 29

3.2 Definición del MMR-ST ..................................................................................................... 30

3.3 Algoritmos exactos ............................................................................................................ 32

3.4 Heurísticas para MMR-ST ................................................................................................ 35

3.5 Metaheurísticas para MMR-ST ........................................................................................ 36

3.5.1 Simulated annealing ...................................................................................................... 36

3.5.2 Búsqueda tabú .............................................................................................................. 38

CAPÍTULO IV: ALGORITMOS PROPUESTOS PARA MMR-ST ...................................................................... 41

4.1 Aporte de la Tesis.............................................................................................................. 42

4.1.1 Algoritmo exactos .......................................................................................................... 42

4.1.2 Algoritmos aproximados ................................................................................................ 46

CAPÍTULO V: EXPERIMENTACIÓN Y ANÁLISIS DE RESULTADOS .................................................................. 54

5.1 Descripción de instancias ........................................................................................................ 55

5.2 Preprocesamiento ............................................................................................................. 56

5.3 Algoritmos Exactos ............................................................................................................ 58

5.3.1 Evaluación de variantes de Descomposición de Benders ............................................ 58

5.3.2 Análisis MILP, EBD y B&C ............................................................................................ 63

xi

5.3.3 Análisis del comportamiento de B&C ............................................................................ 69

5.3.4 Análisis de instancias La ............................................................................................... 72

5.4 Experimentación de algoritmos aproximados. .................................................................. 73

5.4.1 Análisis de heurísticas básicas ..................................................................................... 73

5.4.2 Análisis de metaheurísticas ........................................................................................... 78

CAPÍTULO VI: CONCLUSIONES Y TRABAJOS FUTUROS ................................................................................ 84

Referencias Bibliografía ............................................................................................................................. 87

Anexo 1: Estadísticas de heurísticas ........................................................................................................... 93

Anexo 2: Parámetros GRASP ...................................................................................................................... 97

ÍNDICE DE TABLAS

Tabla 1. Estructura de costos instancias tipo yaman ........................................................................ 55

Tabla 2. Pre procesamiento de instancias He y Mo ......................................................................... 57

Tabla 3. Pre procesamiento de instancias Ya ................................................................................... 57

Tabla 4. Tiempos de ejecución He para variantes de Benders resueltas al óptimo ......................... 59

Tabla 5. Tiempo de ejecución para instancias Mo con variantes de Benders ................................. 59

Tabla 6. Tiempos de ejecución para instancias Ya con variantes de Benders ................................ 60

Tabla 7. Gap de instancias He y Mo para variantes de Benders sin optimalidad ............................ 61

Tabla 8. Gap para instancias Ya con variantes de Benders ............................................................. 61

Tabla 9. Tiempos de ejecución instancias He para MILP, EBD y B&C ............................................ 63

Tabla 10. Tiempo de ejecución instancias Mo para MILP, EBD y B&C ........................................... 64

Tabla 11. Tiempos de ejecución instancias Ya para MILP, EBD y B&C .......................................... 65

Tabla 12. Desviación porcentual instancias He para MILP, EBD y B&C .......................................... 66

Tabla 13. Desviación porcentual instancias Mo para MILP, EBD y B&C ......................................... 66

Tabla 14. Desviación porcentual instancias Ya para MILP, EBD y B&C .......................................... 66

Tabla 15. Análisis de tiempo de B&C para instancias Ya de mayor tamaño ................................... 69

Tabla 16. Análisis de tiempo instancias He de mayor tamaño para B&C ........................................ 70

Tabla 17. Análisis de tiempo instancias Mo de mayor tamaño para B&C ........................................ 70

Tabla 18. Gap de instancias Ya de mayor tamaño para B&C .......................................................... 71

Tabla 19. ANálisis de desviaciones porcentuales para B&C en instancias mayores tipo He .......... 72

Tabla 20. Análisis instancias MO para B&C en tamaños mayores ................................................... 72

Tabla 21. Análisis de tiempos instancias La ..................................................................................... 73

Tabla 22. Análisis de gap instancias La ............................................................................................ 73

xii

Tabla 23. Análisis de heurísticas instancias Ya(C,C) ....................................................................... 74

Tabla 24. Análisis de heurísticas instancias Ya(C,2C) ..................................................................... 75

Tabla 25. Análisis de heurísticas instancias Mo ............................................................................... 75

Tabla 26. Análisis de heurísticas instancias He ................................................................................ 75

Tabla 27. Muestra de estadísticas de heurísticas para Ya(C,C) ...................................................... 76

Tabla 28. Muestra de estadísticas de heurísticas para Ya(C,2C) .................................................... 76

Tabla 29. Muestra de estadísticas de heurísticas para He ............................................................... 77

Tabla 30. Muestra de estadísticas para heurísticas de Mo .............................................................. 78

Tabla 31. Mínima (min), promedio (av.) y máxima desviación porcentual desde solución de

referencia para instancias con 100 nodos. ....................................................................................... 80

Tabla 32. Mínima (min), promedio (av.) Y máxima desviación porcentual desde solución de

referencia para instancias con 80 nodos. ......................................................................................... 81

Tabla 33. Mínima (min), promedio (av.) Y máxima desviación porcentual desde solución de

referencia para instancias con 60 nodos. ......................................................................................... 82

Tabla 34. Estadísticas de heuríticas Ya(c,c) ..................................................................................... 93

Tabla 35. Estadísticas de heurísticas Ya(C,2C) ............................................................................... 94

Tabla 36. Estadísticas heurísticas He ............................................................................................... 95

Tabla 37. Estadísticas heurísticas Mo .............................................................................................. 96

Tabla 38. Resultados de GRASP para 100 nodos con distintos conjuntos de parámetros por familia

de instancias...................................................................................................................................... 97

ÍNDICE DE ILUSTRACIONES

Ilustración 1. Cálculo del regret parte I ............................................................................................. 24

Ilustración 2. Cálculo del regret parte II ............................................................................................ 25

Ilustración 3. Cálculo del regret parte III ........................................................................................... 25

Ilustración 4. Cálculo del regret parte IV ........................................................................................... 25

Ilustración 5. Grafo G con datos intervalares .................................................................................... 48

Ilustración 6. Grafo con nuevo criterio de optimización .................................................................... 48

Ilustración 7. Composición del regret local ....................................................................................... 49

Ilustración 8. Cálculo de regret local parte 1 ..................................................................................... 49

Ilustración 9. Cálculo del regret local parte II .................................................................................... 50

Ilustración 10. Definición de vecindario parte I ................................................................................. 52

Ilustración 11. Definición de vecindario parte II ................................................................................ 52

Ilustración 12. Definición de vecindario parte III ............................................................................... 53

Ilustración 13. Definición de vecindario parte IV ............................................................................... 53

xiii

ÍNDICE DE GRÁFICOS

Gráfico 1. Porcentaje de instancias resueltas para un tiempo dado................................................. 62

Gráfico 2. Porcentaje acumulado de instancias para un gap dado .................................................. 62

Gráfico 3. Porcentaje acumulado de instancias v/s tiempo para MILP, EBD Y B&C ....................... 68

Gráfico 4. Porcentaje acumulado de instancias v/s gap para MILP, EBD Y B&C ............................ 68

CAPÍTULO I: INTRODUCCIÓN

Este capítulo tiene por objetivo dar a conocer la problemática, en particular, con la que se trabaja, posteriormente se presentan los objetivos del trabajo. Finalmente, se describe la contribución que se realizó.

15

1.1 CONTEXTUALIZACIÓN

Dentro de la Investigación de Operaciones (IO) una de las áreas más desarrolladas es la

optimización en redes. Los problemas del área han cautivado el interés de los investigadores de

ésta y muchas otras áreas de investigación, que incluso escapan del contexto de la ingeniería,

tales como ciencias de la computación, matemática y biología, por nombrar algunas. Dicha

relevancia se debe principalmente a la gran variedad de situaciones que pueden ser modeladas en

redes. Los estudios de optimización en redes se pueden relacionar con diversas áreas de

aplicación, que van desde problemáticas básicas de logística, hasta el modelamiento de redes

sociales. Los problemas en redes tienen la propiedad de poder ser representados de forma simple

a través de grafos. Para mayor detalle al respecto de los conceptos y propiedades básicas de la

teoría de grafos ver (Godsil & Royle, 2001).

Una gran cantidad de problemas en grafos pueden ser modelados a través de la

optimización combinatorial (CO), donde las restricciones buscan dar una topología particular a la

solución, por ejemplo: un tour para el caso del problema del vendedor viajero (TSP), un camino

para el caso del problema del camino más corto (SP) o un árbol para el caso del problema del árbol

de expansión mínima (MST). La función objetivo busca optimizar una función de costos asociada a

dicha estructura.

Dentro de los problemas de optimización combinatorial en redes, uno de los más

estudiados es el MST. Este problema se define sobre un grafo conexo y no dirigido ,

donde es un conjunto finito de vértices, que dependiendo de la aplicación pueden representar

terminales, estaciones de telecomunicaciones, etc.; corresponde al conjunto de aristas, que

representan los enlaces entre los vértices, cada una de estas conexiones tiene un número positivo-

real asociado, el cual se denota como , que asocia el peso de ir del vértice al , el cual puede

representar costo, tiempo, distancia, etc. Un árbol de expansión (ST) corresponde a un conjunto de

n nodos y aristas, con la propiedad de conectar todos los vértices del grafo , luego un

MST es el conjunto de aristas que conectan todos los vértices del grafo al menor costo

posible.

Este problema fue propuesto en diferentes contextos antes del siglo XX, sin embargo, su

primera formulación matemática se presentó en 1926, por Boruvka (1926), quién según la historia,

tuvo que aprender de dicho problema por petición de un amigo (Jindrich Saxel, empleado de un

planta eléctrica), durante la electrificación del sur de Moravia, en la República Checa. Fue para

resolver esta problemática, netamente práctica, donde se proporcionó el primer algoritmo conocido

para resolver el MST; convencido del gran aporte realizado, Boruvka, el mismo año, publicó otro

artículo en donde abordó con mayor detalle la contribución realizada (Boruvka, 1926b).

Posteriormente, Vojtech Jarník, otro matemático checo, al darse cuenta de la importancia del

16

trabajo realizado por Boruvka (1926) y considerando que la solución propuesta en dicho trabajo,

desde su punto de vista era muy complicada, trabajó por lo tanto en una solución alternativa, para

posteriormente enviarla a través de una carta a Boruvka y, finalmente, publicar un artículo con el

mismo nombre de (Boruvka, 1926) con el subtítulo From the letter to Mr. Boruvka (Jarník, 1930).

Traducciones de los trabajos de Boruvka y Jarník son presentadas en (Nesetril et al., 2001) y

(Korte & Nesetril, 2001b) respectivamente. En la década de los 50’, con la aparición de los

primeros computadores, surgieron numerosos estudios importantes, donde destacan los realizados

por (Prim, 1957), quien de forma independiente a (Jarník, 1930) propone una alternativa

semejante y (Kruskal, 1956) el cual propone una tercera alternativa de solución a la problemática.

Si bien hasta la fecha se siguen proponiendo nuevos algoritmos, son estos trabajos los que juegan

el rol principal en la historia del MST. Para una revisión completa de los aportes realizados

respecto al MST ver (Graham & Hell, 1985), (Magnanti & Wolsey, 1995), (Nesetril, 1997) y (Nesetril

et al., 2001).

Los problemas de árbol han llamado el interés de la investigación de operaciones por

diversas razones, en primer lugar por su gran aplicabilidad, debido a que las aplicaciones naturales

de dicho problema están relacionadas con sistemas de comunicación, tales como: redes

telefónicas, eléctricas, hidráulicas, de televisión por cable, computacionales y de transporte. Sin

embargo, con el transcurso del tiempo este modelo ha sido propuesto para resolver problemáticas

de diferente índole. Algunos trabajos en donde se muestra la diversidad de aplicaciones son:

Reconocimiento de filogenia de imágenes en (Rocha & Dias, 2012), Análisis de Jerarquía celular

en (Kiranyaz & Gabbouj, 2007), Problemas de localización (Tamir, 2000), diseño de algoritmos

para clustering dentro del contexto de data mining (Huang & Li, 2007), diseño de sistemas

energéticos eficientes (Zhang, Li, & Lim, 2010), (Li et al., 2011), análisis de crisis financieras

(Zhang, et al., 2011), telecomunicaciones (Santos et al. 2008). Otras aplicaciones básicas se

pueden encontrar en (Ahuja et al., 1995).

Otro factor que ha gatillado el profundo estudio de árboles está dado por la facilidad

(algoritmos de tiempo polinomial) con la que se puede resolver el MST clásico, esto ha permitido

que todas las aplicaciones antes nombradas hayan sido viables computacionalmente. Un tercer

punto de gran importancia es que los árboles están presentes en un área de gran importancia

como lo es la optimización en redes, es más, los árboles representan uno de los modelos más

básicos para el diseño de redes.

Finalmente, los modelos de árbol representan un problema tipo para muchos problemas de

optimización combinatorial, por lo que las técnicas estudiadas en éste pueden ser replicadas para

esta clase de problemas. Para mayor detalle de las propiedades del MST que han despertado el

interés de los investigadores ver (Magnanti & Wolsey, 1995).

17

1.2 MANEJO DE INCERTIDUMBRE

Una de las discusiones presentes desde los orígenes de la investigación de operaciones es la

incerteza en los parámetros. Los modelos en forma clásica trabajan bajo el supuesto de que los

datos son conocidos, es decir, su naturaleza es determinista. En la práctica trabajar bajo este

supuesto es poco realista, la forma tradicional para obviar dicho supuesto es la programación

estocástica, sin embargo, esta metodología implica realizar otra afirmación importante, pues

requiere definir una distribución de probabilidad, lo cual muchas veces es una tarea titánica y

asumir una equivocada, puede generar errores de gran magnitud. Algunos factores que pueden

llevar a tener una incorrecta distribución de probabilidad son: poca cantidad de observaciones,

muestra inadecuada, errores en proceso de muestreo, desconocimiento del tomador de decisión de

la gama de distribuciones de probabilidad existentes, etc.

Dada la dificultad para determinar una distribución de probabilidad, durante las últimas

décadas ha tomado gran importancia una nueva línea de investigación, la cual trabaja la

incertidumbre mediante datos intervalares, donde no se tiene conocimiento con respecto a su

distribución de probabilidad. Dicha propuesta de modelamiento de la incertidumbre ha recibido el

nombre de optimización robusta.

Los acercamientos a la Optimización Robusta han sido diversos y se pueden observar a lo

menos 4 fuentes de investigación, cada una con sus propias características. El modelo MinMax (y

Minmax Regret) es presentado en la década de los 90’ en términos de optimización robusta, este

trabaja los datos de forma intervalar y consideran diferentes criterios para la evaluación de la

optimalidad, una compilación de resultados importante es mostrada en (Kouvelis & Yu, 1997). Otra

importante fuentes de investigación relevante, es la propuesta por Bertsimas en sus trabajos

(Bertsimas & Sim, 2003) y (Bertsimas & Sim, 2004), este se ha convertido en uno de los más

importantes modelos en el contexto de la optimización robusta. La característica principal de este

enfoque con datos intervalares es que deriva en un modelo de programación lineal entera que

conserva la complejidad del problema original. Un tercer acercamiento para el tratamiento de la

incertidumbre es el realizado por Ben-Tal, Nemirovski y Ghaoui (2009), donde se trabaja la

incertidumbre como perteneciente a elipsoides, conformando un problema de optimización

convexa, una excelente referencia se presenta en el libro (Ben Tal et al., 2009). El último y más

reciente acercamiento, es el propuesto por (Chen et al., 1997) con un enfoque un tanto distinto, el

cual tiene por objetivo minimizar el riesgo. Para mayor detalle del último acercamiento, ver los

siguientes trabajos (Chen et al., 2009), (Chen, et al., 2009b), (Álvarez-Miranda et al., 2010) y

(Álvarez-Miranda et al., 2011).

En este trabajo se profundizará en el modelo Min-Max Regret (MMR) que en particular ha

capturado gran atención; diferentes modelos han sido estudiados bajo este concepto; Camino más

18

corto, de ahora en adelante SP (Shortest Path) (Karasan et al. 2001), MST (Yaman et al., 2001),

problemas de localización, de ahora en adelante LP (Location Problem) (Averbakh & Berman,

2005), vendedor viajero, de ahora en adelante TSP (Traveling Salesman Problem) (Montemanni et

al., 2007). Una característica importante de los Modelos de tipo MMR es que usualmente modelos

que en la versión clásica son fáciles de resolver (tiempo polinomial) en la contraparte robusta se

convierten en problemas NP-Hard.

El MMR-ST (MinMax Regret Spanning Tree) es un problema que merece ser estudiado, por

diversas razones: desafío algorítmico dado por la complejidad del problema, estructura particular

que le permite ser un problema tipo (problema anidado MinMax). Luego, las técnicas utilizadas en

este pueden ser replicadas a una gran cantidad de problemas en redes, fácil interpretación de la

modelación, facilidad de obtención de los parámetros de entrada a diferencia de la programación

estocástica, etc.

1.3 OBJETIVOS

Estudiar y resolver el problema del Árbol de Expansión Robusto con datos intervalares a través del

modelo Min-Max Regret (MMR-ST), mediante algoritmos heurísticos, meta-heurísticas y métodos

exactos.

1.3.1 OBJETIVOS ESPECÍFICOS

Revisión bibliográfica de los métodos de optimización robusta con incertidumbre intervalar,

con énfasis en el criterio de MMR.

Revisión bibliográfica de algoritmos exactos para solución del MMR-ST e implementar la

(s) mejores alternativas.

Revisión bibliográfica y/o meta-heurísticas para la solución del MMR-ST e Implementar la

(s) mejores alternativas.

Diseñar e implementar variantes de los algoritmos encontrados en la literatura, tanto para

algoritmos heurísticos, meta-heurísticas como métodos exactos.

Analizar y confrontar los resultados obtenidos por los diferentes algoritmos heurísticos y

exactos implementados.

19

1.4 ESTRUCTURA DE LA TESIS

El presente trabajo está organizado de la siguiente forma: en la sección 2 se entregan los

fundamentos generales de la optimización robusta con especial énfasis en el modelo MMR, se

muestran las motivaciones de su uso, se presenta la generalización matemática de un modelo de

optimización combinatorial (CO) bajo este modelo. Además, se presenta una recopilación de

estudios de su complejidad. En la sección 3, se formaliza el MMR-ST, primero, entregando los

fundamentos de las formulaciones matemáticas del problema clásico, y luego, presentando una

revisión de los algoritmos exactos y las heurísticas propuestas para la resolución de éste. En la

sección 4, se presenta el aporte de esta tesis, es decir, se da una descripción detallada de los

algoritmos tanto exactos como heurísticos propuestos para la resolución del problema en estudio.

Los resultados de la experimentación son expuestos en la sección 5, acá se presenta además el

conjunto de instancias utilizado para el análisis, en este apartado se entrega un análisis exhaustivo

de los diferentes algoritmos utilizados. Finalmente, en la sección 6 se despliegan las conclusiones

y los posibles trabajos futuros relacionados.

CAPÍTULO II: MODELO MINMAX REGRET

En este capítulo se introduce la teoría actual de la optimización robusta con incertidumbre

intervalar, dando especial énfasis en la metodología MMR.

21

2.1 DESCRIPCIÓN GENERAL

Desde los orígenes de la investigación de operaciones la incerteza ha despertado el interés por parte

de los investigadores. Los modelos de investigación de operaciones en forma clásica trabajan bajo el

supuesto de que los datos son conocidos, es decir, su naturaleza es determinista, esta condición es

convencionalmente aceptada, sin embargo en ocasiones no considerar la incerteza puede no ser lo

más adecuado, el primer acercamiento a la incerteza en un modelo matemático fue realizado por

(Dantzig, 1955); a partir de este trabajo nació una de las técnicas más tradicionales para trabajar

incerteza, como lo es la programación estocástica, excelentes referencias para profundizar en el tema

se presentan en los libros (Uryasev & Pardalos, 2001), (Schneider & Kirkpatrick, 2006) y (Marti, 2008).

Esta metodología implica realizar otra afirmación importante, pues requiere definir una distribución de

probabilidad; en ocasiones asumir un distribución de probabilidad es una tarea titánica y asumir una

equivocada puede generar errores de gran magnitud.

Otra aproximación para el tratamiento de la incerteza corresponde a la incertidumbre difusa, la

cual se basa en la determinación de una pertenencia gradual, que está dada por una función (función

de pertenencia). Este acercamiento al igual que la programación estocástica requiere de una

definición de parámetros, el origen de estos modelos está en el trabajo presentado por (Bellman &

Zadeh, 1970), un poco de la historia de esta línea de investigación se puede revisar en el libro de

(Zimmermann, 2005).

Durante las últimas dos décadas ha surgido una nueva línea de investigación que trabaja la

incertidumbre de forma determinística, también conocida como optimización robusta (OR). La

característica principal es que tanto eventos con alta probabilidad de ocurrencia como eventos con

baja probabilidad de ocurrencia tienen la misma importancia. El origen de esta aproximación a la

incertidumbre es variado y sus principales precursores pertenecen a las ciencias aplicadas, donde

destacan la estadística robusta (Huber & Ronchetti, 2009), el aprendizaje automático (Mitchell, 1997),

el control robusto (Dullerud & Paganini, 2010) y obviamente la teoría de optimización. El objetivo de

esta rama de investigación es buscar soluciones que entreguen cierta protección al tomador de

decisión ante escenarios poco favorables.

Los acercamientos a la optimización robusta han sido diversos y se pueden observar a lo

menos 4 fuentes de investigación, cada una con sus propias características. El modelo MinMax es

presentado en la década de los 90’ en términos de optimización robusta. Éste trabaja los datos de

forma intervalar y considera diferentes criterios para la evaluación de la optimalidad. Una compilación

de resultados importante es mostrada en (Kouvelis & Yu, 1997), quienes fueron pioneros en la

adaptación de robustez a problemas de optimización combinatorial. Otra fuente de información de

22

gran relevancia, y más actualizada para este tipo de modelos, es la presentada por (Kasperski A.

,2008).

En este trabajo se estudiará en más detalle el modelo MMR, en tanto, continuación se

profundizará en sus características.

2.2 MODELO MIN-MAX REGRET

Los modelos MMR han capturado gran atención dentro de la investigación de operaciones, diferentes

aplicaciones han sido estudiadas bajo este concepto: camino más corto (SP) (Karasan et al. 2001),

Árbol de expansión (ST) (Yaman et al., 2001), Problemas de localización (LP) (Averbakh & Berman,

2005), vendedor viajero (TSP) (Montemanni et al., 2007), por mencionar algunos. En éstos y en un

gran conjunto de trabajos adicionales, se ha analizado el modelo MMR desde diferentes perspectivas,

tales como complejidad computacional, algoritmos exactos y heurísticas. Más adelante se verán en un

mayor detalle los principales aportes en cada una de las perspectivas.

En relación a las aplicaciones se han realizado numerosos esfuerzos para resolver situaciones

reales. Ejemplos de esto son algunos trabajos que se mostrarán inmediatamente. En (Luolou &

Kanudia, 1999) se utiliza una formulación para un problema relacionado con estrategias de

disminución de emisiones de gas en invernaderos, Dicho estudio se llevó a cabo en la provincia de

Québec en Canadá. En esta investigación se realizan interesantes comparaciones con una

formulación de programación estocástica para el mismo problema. En los trabajos de (Chang &

Davila, 2006) y (Chang & Davila, 2007) se utiliza el modelo MMR para abordar la problemática de la

gestión de residuos sólidos. En el trabajo del año 2006 se utilizan técnicas de grey programming

combinadas con una formulación MMR; posteriormente en (Chang & Davila, 2007) abordan el

problema utilizando una formulación MIP para el modelo MMR, la metodología fue aplicada en el Valle

Rio Grande (TX, USA). Otro trabajo interesante es presentado en (Kasakci et al., 2007) donde es

desarrollado un modelo híbrido a través de Programación Lineal Intervalar (ILP) y la formulación del

modelo MMR. En este estudio se analizó la localización de granjas destinadas a la fabricación de

biocombustible en Francia.

El modelo MMR pertenece a la familia de modelos Min-Max donde se modela la incertidumbre a

través de datos intervalares o escenarios discretos. Para el caso de los datos intervalares, a cada

parámetro se conoce el valor de su lower y upper bound, pudiendo tomar un valor dentro de este

intervalo, que por lo demás, es independiente de los valores del resto de los parámetros. Cuando un

conjunto de parámetros toma valores, se obtiene un escenario, lo que significa que cada combinación

de parámetros determina un escenario particular, se tiene entonces un conjunto de escenarios que

corresponde al producto cartesiano de los intervalos de incerteza. Con respecto a los escenarios

discretos se tiene un conjunto que corresponde a una lista de escenarios .

23

Otro criterio conocido para el manejo de la robustez a través de MinMax es el llamado MinMax

absolut, el cual es un criterio bastante más conservador.

MMR también conocido como desviación robusta, busca el escenario donde se obtiene la mejor

peor desviación robusta, es decir, donde el máximo regret es mínimo. El término regret viene del

inglés y significa arrepentimiento; en el contexto de optimización es encontrar la solución que minimice

la brecha de la solución bajo cualquier escenario. Este problema puede ser modelado de la siguiente

forma:

Donde es el conjunto de soluciones factibles, es el conjunto de escenarios posibles, es la

función objetivo y la solución optima bajo un escenario particular .

El principal desarrollo de este modelo se ha realizado en el área de la CO. A continuación se

definirá la notación utilizada para explicar MMR en problemas combinatoriales. Esta fue extraída

desde (Averbakh & Lebedev, 2004). Lo primero es definir un problema combinatorial estándar (COP).

= sea un conjunto finito de soluciones factibles y una función definida sobre con la

propiedad de que el óptimo valor del problema: , siempre existe.

Asumiendo que existe incerteza en la función objetivo, es decir, es miembro de una familia de

funciones para algún conjunto de escenarios. Considerando independiente del conjunto

de escenarios, se denota el óptimo valor para el siguiente problema.

= , se obtiene que este problema para algún escenario se

reduce a un problema clásico de COP.

Luego, para algún y , la función se denomina regret para

bajo el escenario . El regret del peor caso para algún y el respectivo escenario inducido se

denotará por la función de que está definida por.

Se puede observar que . Luego la versión MMR-COP está dada es:

Para un problema MMR-COP se considera un conjunto finito base y el

conjunto factible de soluciones. Luego cada elemento toma valores dentro de un intervalo

24

, . A partir de lo anterior se pueden deducir las siguientes definiciones y el

teorema 1.

Definición 1: Un escenario es obtenido a través de la asignación de un costo

.

Definición 2: La desviación robusta para una solución factible de un problema combinatorial

en un escenario , es la diferencia entre el costo de y el costo de la solución óptima para el

escenario .

Definición 3: una solución se dice solución robusta relativa (relative robust solution), si este

tiene la mínima (entre todas las soluciones) máxima (entre todos los escenarios) desviación robusta.

El siguiente teorema es la base para todos los estudios de formulación matemática propuestos

a la fecha.

Teorema 1: (Yaman et al., 2001). Dada una solución y un escenario , la desviación

robusta máxima se produce cuando

y

, donde representa

el escenario inducido por la solución .

A continuación se presenta un ejemplo del cálculo del regret para una solución . Dado el

grafo mostrado de la ilustración 1 a la 4.

En primer lugar, en la ilustración 1, se tiene un grafo con datos intervalares, luego, en la

ilustración 2 se tiene una solución . En la ilustración 3 se genera el peor escenario de

acuerdo al teorema 1 y se calcula el costo de la solución Finalmente, en la ilustración 4,

se procede a calcular la solución óptima en el peor escenario y se calcula su costo 7, y el

respectivo regret .

ILUSTRACIÓN 1. CÁLCULO DEL REGRET PARTE I

25

LUSTRACIÓN 2. CÁLCULO DEL REGRET PARTE II

ILUSTRACIÓN 3. CÁLCULO DEL REGRET PARTE III

ILUSTRACIÓN 4. CÁLCULO DEL REGRET PARTE IV

En (Candia-Véjar et al.,, 2011) se muestra un MIP genérico para MMR-COP con restricciones y

función objetivo lineal, basado en el teorema antes mencionado y algunos supuestos que se

presentarán a continuación. Una característica que resaltan los autores es que este modelo asocia un

número polinomial de restricciones y variable.

Una variable binaria es definida diciendo si es una parte de la solución

construida. Un vector característico de un conjunto de elementos es un vector binario

tal que 1 si y solo si .

26

Ahora se asocia al conjunto de soluciones con el de vectores binarios , éste

satisface las siguientes condiciones:

Si es un vector característico de una solución factible , entonces y

Si es un vector característico de un subconjunto además en tanto

existe un tal que

Luego contiene todos los vectores característicos de todas las soluciones factibles en

y éste también puede contener vectores característicos de un subconjunto , tal que, . Sin

embargo, en este caso debe contener una solución factible tal que

A continuación se asumirá que puede ser descrito como un conjunto de ecuaciones

lineales de la siguiente forma:

Donde corresponde a un vector de variables auxiliares, que son utilizadas si es necesario,

es una matriz y corresponde al vector de costos, primero se asume que la matriz es totalmente

unimodular (cada sub matriz cuadrada de tiene determinante 1, 0 ó -1), luego se puede definir la

siguiente función:

En (Candia-Véjar et al.,, 2011) se muestra que un MMR-COP puede ser expresado de la

siguiente forma.

Claramente este problema no es lineal, sin embargo considerando la propiedad de total

unimodularidad de la matriz es posible transformarlo en un problema lineal con variables binarias,

para mayor detalle de esta transformación ver el artículo mencionado.

Si bien el problema puede ser expresado como un modelo lineal, su complejidad es una arista

de gran importancia, pues problemas que en su versión clásica son fáciles de resolver (en tiempo

polinomial), como lo son: MST, SP, asignación, etc., en la versión robusta se transforman en

problemas del tipo NP-Hard. Un estudio detallado de la complejidad computacional de los modelos

MMR-CO es mostrada en (Kouvelis & Yu, 1997). Varios han sido los trabajos donde se ha estudiado

27

la complejidad del modelo MMR. Una buena referencia se puede encontrar en (Aissi et al., 2005). A

continuación se presentan algunos resultados relevantes de dichos trabajos.

MMR-P = NP-Hard incluso con redes de dos capas de ancho y con solamente 2 escenarios.

MMR-ST = NP-Hard inclusive si .

MMR-Knapsack (en versión robusta absoluta): Fuertemente NP-Hard para conjuntos de

escenarios no acotado.

MMR-Allocation = NP-Hard inclusive si .

MMR-Assigment = NP-Hard inclusive si .

28

CAPÍTULO III: MIN-MAX REGRET SPANNING TREE

En este capítulo se entrega la principios matemáticos del MMR-ST, además de una extensa

revisión de los principales aportes algorítmicos realizados a la fecha.

29

3.1 FORMULACIONES PARA MST

Para definir el problema MMR-ST y además conocer las distintas aproximaciones algorítmicas

propuestas a la fecha, es necesario conocer algunas formulaciones básicas del problema clásico

(MST). Las formulaciones matemáticas para el MST se pueden clasificar en dos grandes grupos. Por

un lado se tienen las formulaciones naturales o directas y por el otro las formulaciones derivadas. Con

respecto a las formulaciones naturales se mostrarán dos, una basada en un subconjunto de

restricciones que previenen circuitos (prevención de subtours) y otra basada en el aseguramiento de

la conectividad (cut-set inequalities).

Considere la variable binaria (para todo ) que toma valor 1, si el arco está

dentro de la solución del MST. Se tiene la siguiente formulación:

Restricciones de conectividad

La restricción de cardinalidad (2.2) asegura que para cada nodo en el conjunto existe un

arco incidente. Para los subconjuntos , se consideran las siguientes definiciones

, cuando se tiene que , luego . Para asegurar la

conectividad usualmente se utiliza o restricciones de eliminación de subtour, como en la restricción

(2.4) o la inclusión de cut-set inequalities como en la restricción (2.5).

Es importante mencionar que las cut-set se implementan sobre una versión bidirigida del grafo

original, donde cada arista es reemplazada por el arco y cada arista

es remplazada con dos arcos y arco , generando el conjunto de arcos

, estos arcos heredan el costo o peso de la arista originaria

Este tipo de formulación tiene la desventaja de que el número de restricciones de conectividad

crece de forma exponencial con el tamaño del problema, pero también se han presentado

formulaciones compactas.

30

A continuación se presenta una extensión de formulación de este tipo basada en la

formulación del problema de flujo multi-producto. En esta formulación adicionalmente a las variables

se utilizarán las variables de decisión (para todo y ), lo cual especifica si

el arco es usado en el camino desde el nodo raíz a La formulación del flujo multi-producto se

presenta a continuación.

, ,

Las restricciones de conservación del flujo (2.6), (2.7) y (2.8) establecen que la solución debe

tener un camino, entre el nodo 0 y el nodo (para todo ), la restricción (2.9) asegura que solo

es posible enviar flujo a través del nodo a través del arco si este arco se encuentra dentro de la

solución. Estos conjuntos de restricciones permiten asegurar la conectividad de la solución.

3.2 DEFINICIÓN DEL MMR-ST

El MMR-ST es definido sobre un grafo , donde es el conjunto de vértices y es el

conjunto de aristas. Un intervalo

con se asocia a cada arista . Los intervalos

representan rangos de pesos posibles, pueden estar asociados a costos, distancias, tiempo, etc.

Definición 1: Un escenario es obtenido a través de la asignación de un costo

.

Definición 2: La desviación robusta para un ST en un escenario , es la diferencia entre el

costo de y el costo de la solución optima para el escenario .

Definición 3: un ST se dice solución robusta relativa (relative robust solution), si éste tiene las

más pequeña (entre todas las soluciones) máxima (entre todos los escenarios) desviación robusta.

31

El siguiente teorema es la base para todos los estudios de formulación matemática propuestos

a la fecha.

Teorema 1: (Yaman et al., 2001). Dado un ST un escenario , la desviación robusta

máxima se produce cuando

y

, donde representa el

escenario inducido por la solución .

Con respecto a la complejidad de este problema (Aron & Van Hentenryck, 2004) probaron que

es NP-Hard inclusive si el intervalo de incerteza es igual a , polinomial si el número de aristas con

intervalo de incerteza es fijo o acotado por el logaritmo de una función polinomial de el número total de

aristas. En este mismo trabajo se generaliza el resultado antes mostrado. La clasificación de NP-Hard

del MMR-ST fue probada independientemente por (Aissi et al., 2005). En este trabajo también se

probó para intervalos de costo y además si el grafo es completo.

La primera formulación matemática del modelo MMR-ST fue presentada por (Yaman et al.,

2001), en dicho trabajo también presentan técnicas de pre-procesamiento, el modelo se basa en dos

formulaciones matemáticas, la primera propuesta por (Magnanti & Wolsey, 1995) es la formulación

single commodity model (F1), el segundo modelo utilizado es el problema dirigido de flujo multi-

producto (F2) (Yaman et al., 2001) utiliza ambas formulaciones para representar el MMR-ST, para

representar las aristas de un ST utiliza F1 y para modelar el arrepentimiento del ST utiliza el dual de

F2. Luego la formulación resultante se presenta a continuación.

Irrestricta

32

Esta formulación se aplicó a grafos completos con 10, 15, 20 y 25; la técnica de

preprocesamiento utilizada consistió en identificar aristas fuertes y débiles (strong y weak), con esto

se logró eliminar un porcentaje de éstas, sin embargo los tiempos de ejecución son bastante altos

para instancias de pequeño tamaño como los son las de experimentación.

Con respecto al preprocesamiento, una arista es llamada strong si pertenece a un MST

en algún escenario , donde es el conjunto de escenarios. Una arista es llamada weak si

pertenece a un MST para todos los escenario .

3.3 ALGORITMOS EXACTOS

Posterior al trabajo de (Yaman et al., 2001), se han propuesto algunas alternativas de resolución

exactas; en (Aron & Van Hentenryck, 2004) se muestra un branch and bound (B&B). Este método

mejoró el trabajo de (Yaman et al., 2001) permitiendo resolver instancias de un tipo particular con

tamaño de hasta 40 nodos. Un nuevo algoritmo B&B fué propuesto en (Montemanni & Gambardella,

2005) el cual consideró las instancias utilizadas por los trabajos previos e incluyó un grupo con

metodología de generación distinta. Para ambos grupos de instancias se mejorarón los resultados

obtenidos por (Aron & Van Hentenryck, 2004), según los autores este B&B su esquema de

ramificación fue más fuerte.

Un acercamiento de gran importancia en relación a algoritmos exactos para la resolución del

MMR-ST es el realizado por (Montemanni, 2006). En éste se presenta un algoritmo de

descomposición de Benders, cuya formulación es similar a la de (Yaman et al., 2001) con la única

salvedad de que cambia F1 por una formulación con menos variables pero con más restricciones,

basada en cut-set inequalit. Luego la formulación matemática se presenta a continuación (F3).

Irrestricta

33

La descomposición de Benders es un método clásico de resolución de problema de gran

escala, fue propuesta por primera vez por (Benders, 1962). Para ver detalles de la teoría ver también

(Geoffrion, 1972). A grandes rasgos, esta metodología consiste en dividir el problema general en dos,

un problema maestro y un subproblema. Los resultados de ambos problemas se alimentan de forma

iterativa, luego el problema maestro recibe cortes en cada iteración, los cuales se forman a partir del

resultado obtenido por el dual del subproblema. La solución de este problema se obtiene cuando el

valor del maestro se hace igual al valor del subproblema, pues estos representan la cota inferior y

superior del problema original respectivamente. Aplicaciones de esta metodología han sido muchas y

en variadas áreas ver (Richardson, 1976), (Magnanti et al., 1986), (Cordeau et al., 2000). Estudios

para mejorar el desempeño del algoritmo se muestran en (McDaniel & Devine, 1977) y (Magnanti &

Wong, 1981).

En relación al problema en estudio (MMR-ST), el subproblema primal recibe una solución

que satisfacen las restricciones (4.13) y (4.14) en la primera iteración. Luego deben corresponder a la

solución óptima que satisface las restricciones antes mencionadas más los cortes que se van

generando. Éste puede ser presentado de la siguiente forma:

Irrestricta

Se puede realizar una transformación a la función objetivo y puede ser ajustada a la siguiente

expresión, con el objetivo de tener un problema dual de la forma del MST.

En tanto el modelo del subproblema primal queda de la siguiente forma:

34

irrestricto

Al plantear el dual del subproblema, se obtiene un problema de árbol clásico con un vector de

costos modificado, en la formulación flujo multi-bien. Mayor detalle ver en (Magnanti & Wolsey, 1995).

Finalmente, el problema maestro puede ser formulado como se muestra a continuación, para

mayor detalle ver (Montemanni, 2006).

corresponde a una región factible del problema dual, en tanto corresponde a los puntos

extremos de esta región, además se introduce una variable para extender la definición del problema

maestro.

En (Montemanni, 2006) se compara el rendimiento del Benders propuesto, con el algoritmo

presentado en (Yaman et al. 2001), que se basó en eficientes técnicas de preprocesamiento del

35

modelo, antes de ser entregado a CPLEX (versión 12.3). El segundo parámetro de comparación es el

algorítmo branch and bound propuesto en (Aron & Van Hentenryck, 2002), el tercer y último parámetro

de comparación es el algorítmo branch and bound propuesto por (Montemanni & Gambardella, 2005).

Los resultados presentados en este trabajo demuestran que el número de iteraciones del algorítmo de

descomposición de Benders se incrementa con el número de nodos, como se esperaba, sin embargo

su eficiencia decrece a medida que el paramétro difusor (utilizado para generar instancias) aumenta

su valor. Con respecto a los algoritmos de comparación, Benders es el que obtiene los mejores

resultados.

3.4 HEURÍSTICAS PARA MMR-ST

Como se ha mencionado anteriormente, la alta complejidad del problema MMR-ST no permite obtener

resultados de instancias de tamaño aun pequeño (40 nodos máximo) en un tiempo razonable. Lo

mismo sucede con un grupo no menor de problemas combinatoriales, en mayor (ej. MMR-TSP) o

menor grado (ej. MMR-P). Por el motivo antes presentado, han sido diversas las aproximaciones al

problema a través de heurísticas, sin duda una de las propuestas heurísticas de mayor impacto para

este tipo de problema ha sido la realizada por (Kasperski & Zielinski, 2006), quienes proponen un

algoritmo (Hm) con cota de aproximación 2, esto significa que la peor solución obtenida no tendrá un

valor mayor al doble del óptimo, con la ventaja de conservar la complejidad del problema clásico.

Los algoritmos propuestos por (Kasperski & Zielinski, 2006) se basan en la definición de un

escenario particular, luego se usa este escenario para obtener la solución óptima de un problema

clásico, que también corresponde a una solución factible de un problema MMR. Dos escenarios han

sido propuestos para la aplicación de esta heurística, el escenario del límite superior y el escenario

del punto medio

En la realidad estas heurísticas son complementarias, es decir, dado su bajo tiempo de

ejecución se ejecutan ambas y se selecciona la mejor. Además queda un espacio para probar

distintos escenarios dentro del intervalo de costos y seleccionar la solución que genera el menor

arrepentimiento.

Otra heurística propuesta, en primera instancia para el MMR-TSP en (Mardones, 2010), pero

que puede ser fácilmente generalizada a otros problemas de Optimización combinatorial robusta, es

, esta se fundamenta en el buen rendimiento de la heurística en experimentaciones previas

y en el trabajo realizado por (Montemanni et al., 2007) La idea fundamental de esta heurística es

generar un ranking creciente de costo de soluciones en el escenario . A continuación se muestra el

pseudocódigo de las heurísticas de 1 escenario y de la .

36

Algoritmo Hm (G,c) Algoritmo Hu (G,c)

Input: Grafo G y función de costos c.

Output: Una solución factible Y para MMR-

ST y su arrepentimiento

1. for all do

2.

3. end for

4. Y OPT( )

5. Z(Y) computeRegret(Y)

6. Return Y, Z(Y)

Input: Grafo G y función de costos c.

Output: Una solución factible Y para

MMR-ST y su arrepentimiento 1. for all do

2.

3. end for

4. Y OPT( )

5. Z(Y) computeRegret(Y)

6. Return Y, Z(Y)

Algoritmo n-Hu (G,c)

Input: Grafo G y función de costos c. Output: La mejor solución factible Y para MMR-ST y su arrepentimiento

1. for all do

2.

3. end for

4. OPT( )

5. computeRegret( )

6. Return ,

Ambas metodologías pueden ser generalizadas para cualquier escenario, el único paso que

se debe modificar para esto, es el 2 y se debe reemplazar por .

3.5 METAHEURÍSTICAS PARA MMR-ST

Con respecto a los algoritmos metaheurísticos, para el problema MMR-ST las propuestas de este tipo

han sido escasas, siendo las de mayor impacto las propuestas por (Nikulin, 2008) donde se mostró un

simulated annealing y la propuesta por (Kasperski et al., 2012) donde se propuso una algoritmo tabu

search. En SA se utilizaron instancias de 10, 20 y 30 nodos obteniendos resultados razonables,

donde en TS se utilizaron 6 conjuntos de instancias y se demostró la superioridad en relación a SA. A

continuación se explicarán en detalle ambas aproximaciones metaheurísticas.

3.5.1 SIMULATED ANNEALING

Simulated Annealing (SA) en una metaheurístca probabilística, propuesta en (Kirkpatrick, Gellat, &

Vecchi, 1983) y en (Kirkpatrick A. , 1984), generalmente SA encuentra soluciones cercanas al óptimo

en conjuntos de soluciones factibles extensos. SA al igual que Tabu Search (TS) pertenece al

conjunto de heurísticas de búsqueda local, este tipo de algoritmos son una de las alternativas más

37

prominentes para la obtención de soluciones de calidad en POC complejos, este tipo de algoritmos se

basa en la exploración de soluciones vecinas, intentando mejorar la solución actual a través de

cambios locales, el tipo de cambio local es definido por una estructura de vecindario. El algoritmo de

búsqueda local más básico es la mejora iterativa, este algoritmo comienza en una solución inicial y de

forma iterativa intenta mejorar la solución actual, hasta que se cumpla un criterio de parada,

típicamente un número máximo de iteraciones. A continuación se presenta el pseudocódigo de dicho

algoritmo.

Algoritmo Mejora iterativa (G,c)

Input: Graph G(V, E) Output: Solution S.

1. Compute an initial solution of G

2.

3. while stop criterion = false

4. Find a solution and cost

5. if then

6.

7. end if

8. end while

9. Return ,

SA se diferencia de este algoritmo de mejora iterativa básico, en primer lugar porque permite

salir de óptimos locales a través del criterio de aceptación en base probabilística, es decir, acepta

soluciones peores a la actual en la búsqueda, además para su aplicación se debe especificar el

espacio de búsqueda, estructura de vecindad, función de probabilidad de aceptación, factor de

descenso de temperatura, temperatura inicial, temperatura final y ciclos internos.

En la propuesta hecha por (Nikulin, 2008) los principales aportes están en la definición del

subespacio de búsqueda y la estructura de vecindad, y a continuación se presenta en detalle.

i. Espacio de búsqueda: Un subconjunto del conjunto de aristas puede ser representado

por un vector de variables booleanas donde , donde si la arista

pertenece al actual subconjunto y en caso contrario. En consecuencia un vector

representa el espacio de búsqueda y este es variable en cada iteración.

ii. Estructura de vecindad: Sea el actual espacio de búsqueda, se debe escoger

aleatoriamente , luego se construye el espacio de búsqueda del vecindario

a través de la intervención de .

donde

si y

en caso contrario. La solución inicial utilizada fue .

38

Tanto la estructura de vecindad como el espacio de búsqueda presentados anteriormente

presentan restricciones, relacionadas con el pre procesamiento del grafo.

Algoritmo Simulated Annealing (G,c)

Input: Graph G(V, E) Output: Solution .


2. , ,

3. ComputeRegret( ),

4. while do

5.

6. while do

7. Find a solution and cost

8. ComputeRegret( )

9. if then

10.

11. if then

12.

13. end if

14. end if

15. else

16. ,

17. if then

18.

19. end if

20. end else

21.

22. end while

23. end while

24. Return ,

3.5.2 BÚSQUEDA TABÚ

La metaheurística Búsqueda Tabú (Tabú Search - TS) fue propuesta en Glover (1986), en este

mismo trabajo se introdujo además el término metaheurística, donde la característica principal de TS

es el uso de memoria adaptativa. En relación a la memoria adaptativa de TS, ésta hace uso del

historial del procedimiento de solución, dando énfasis en 4 aristas fundamentales como lo son:

propiedad de ser reciente, frecuencia, calidad e influencia. El pseudocódigo del algoritmo TS se

muestra en seguida.

39

Algoritmo Búsqueda Tabú (G,c)

Input: Graph G(V, E) Output: Solution .


2.

3. ComputeRegret( ),

4. while stop criterion = false do

5. the move to is not forbidden or

6. Find a spanning tree of the smallest value of

7.

8. if then

9. , /* A better solution has been found*/

10.

11.

12. end if

13. if then

14. compute a random spanning tree of

15. if then

16. , /* A better solution has been found*/

17. end if

18. Go to line 4 /* Restart the algorithm*/

19. else

20. /* performe the move*/

21. Update TABU

22. end if

23. end while

24. Return ,

Posterior a conocer la estructura general del algoritmo, es importante conocer las características

principales del algoritmo TS propuesto por (Kasperski et al., 2012) para el MMR-ST, estas se

presentan a continuación.

i. Lista Tabú: En el algoritmo TS al igual que SA es posible explorar soluciones con

, con el objetivo de no permanecer en mínimos locales. Una forma de evitar las

oscilaciones alrededor de mínimos locales es almacenar información relacionada con el

desempeño de los movimientos, información que es almacenada en la llamada Lista Tabú.

Esta lista contiene información acerca de movimientos que son prohibidos por un cierto

número de iteraciones.

Sea la solución actual, se realiza un movimiento agregando a la arista a y

se elimina la arista desde , se obtiene la solución desde Con el fin

de evitar volver a estar en , se agrega a la lista dos elementos y

. Esto significa que se prohíbe agregar la arista a la actual solución por

iteraciones y eliminar la arista por iteraciones.

40

ii. Criterio de aspiración: El criterio de aspiración es una condición que permite realizar un

movimiento aunque este esté prohibido, en (Kasperski et al., 2012) se utiliza un criterio donde

siempre se permite mover a soluciones mejores .

iii. Función de memoria a largo plazo: La lista tabú y el criterio de aspiración son consideradas

funciones de memoria a corto plazo de TS. Esto significa que la información almacenada en

estas es perdida después de un número pequeño de iteraciones. Con el fin de lograr una

diversificación global algunas funciones de memoria a largo plazo pueden ser incorporadas.

En (Kasperski et al., 2012) se incorpora un nuevo conjunto de aristas , en la solución

inicial y cada vez que se mejora la solución actual se agrega a todo el conjunto de aristas

que pertenece a . Después que un número de iteraciones se ha cumplido y la solución

actual no mejora, se restaura la solución actual, generando una solución aleatoria del

subgrafo .

Es importante mencionar que en TS se utilizó una solución inicial aleatoria. Según los autores,

después de un proceso de experimentación se llegó al consenso que el esfuerzo computacional para

lograr salir de ese óptimo local es mayor al esfuerzo realizado para converger a una solución de

calidad como las entregadas por estas heurísticas.

41

CAPÍTULO IV: ALGORITMOS PROPUESTOS PARA

MMR-ST

En este capítulo se describe la propuesta de investigación de este trabajo, mencionando aportes esperados, metodologías de trabajo y modelos implementados.

42

4.1 APORTE DE LA TESIS

Los aportes principales de este trabajo están enfocados en la implementación de nuevos

algoritmos para la resolución de problemas robustos bajo el criterio Min-Max Regret,

particularmente el problema MMR-ST y evaluar su desempeño con respecto a lo propuesto en la

literatura. Adicionalmente, se encuentran mejores soluciones para el conjunto de instancias

propuestas en (Kasperski et al, 2012).

Como se pudo ver en la revisión bibliográfica, los aportes realizados para resolver este tipo de

problemas desde el punto de vista algorítmico no son extensos, en relación a algoritmos exactos

sólo se muestran propuestas de algoritmos Branch & Bound y Descomposición de Benders. Con

respecto a los algoritmos aproximados lo más destacado es Tabu Search, Simulated Annealing y

las heurísticas de un escenario (Hu y Hm). A continuación se presentan los aportes de este trabajo

divididos en dos grupos algoritmos exactos y algoritmos aproximados.

4.1.1 ALGORITMO EXACTOS

Como se ha comentado anteriormente la descomposición de Benders es el algoritmo exacto que

ha entregado los mejores resultados, en tanto es natural proponer alguna variante que pudiese

mejorar su desempeño. El aporte específico que se realizará en este aspecto es implementar

variantes al algoritmo Benders con la formulación cut set inequality mostrada en la literatura en

(Montemanni, 2006), a continuación se presenta el pseucódigo del Benders básico.

Descomposición de Benders Básica (G,c)

Input: Grafo G y función de costos c. Output: Solución óptima y su arrepentimiento 1. Inicialización

1.1 FOMaestro MIN_INT, FOSubP MAX_INT

1.2 Inicializar Maestro con restricciones no complicantes

1.3 ,

2. while (FOMaestro<FOSubP) do

2.1 Resolver Maestro

2.2 Resolver dual del problema clásico (MST clásico).

2.3 Agregar corte de benders

3. end while

4. Return ,

Las dos extensiones del algoritmo de Benders están inspiradas en el trabajo realizado por

(Pereira & Averbakh, 2011) en el estudio del problema Set Covering robusto. La primera variante

está relacionada con el ingreso de más de un corte por iteración, a diferencia del problema de

Benders básico. Para esto se utilizan n búsquedas locales (n = número de cortes agregados)

43

donde se realice un k-opt para encontrar soluciones similares y posteriormente se genera el corte

por cada solución encontrada. Abajo se muestra el pseudocódigo del algoritmo descomposición de

Benders con múltiples cortes.

Descomposición de Benders con n cortes k-opt (G,c)




1.3 ,


2.1 Resolver Maestro


2.3 Agregar corte de Benders básico

2.4 Encontrar n soluciones similares a través k-opt

2.5 Ingresar cortes de soluciones similares

3. end while

4. Return ,

La segunda extensión de Benders está relacionada con el uso de las soluciones

incumbentes de CPLEX en la resolución del maestro, es decir, en cada iteración se agrega el corte

del problema básico y los cortes generados por cada solución incumbente encontrada en el

maestro.

Descomposición de Benders con cortes incumbentes (G,c)




1.3 ,


2.1 Resolver Maestro (guardando soluciones

incumbentes)


2.3 Agregar corte de Benders básico

2.4 Ingresar cortes de soluciones incumbentes

3. end while

4. Return ,

Cabe destacar que el maestro de cada variante es resuelto con un algoritmo Branch and Cut,

implementando heurísticas primales, las cuales se alimentan de la información de cada nodo del

proceso de Branch and Bound. Además, se utilizan los cortes que posee CPLEX por defecto,

44

finalmente las cut-set inequalities son manejadas a través de un algoritmo de flujo máximo de

acuerdo a lo mostrado en (Álvarez-Miranda et al., 2012).

Con respecto a algoritmos exactos en base a ramificación implementados para MMR-ST sólo

se tienen las propuestas de Branch and Bound realizadas en (Aron & Van Hentenryck, 2002) y

(Montemanni & Gambardella, 2005), sin embargo, los resultados no fueron alentadores. Por otra

parte en (Averbakh & Berman, 2005) y (Pereira & Averbakh, 2011) se proponen algoritmos del tipo

Branch and Cut para otros problemas del tipo MMR, basados en Benders cuts. En este trabajo se

propone implementar este tipo de algoritmo al problema MMR-ST, considerando una doble

separación de las restricciones, específicamnente, se dividen las restricciones topológicas del

problema árbol y las restricciones asociadas a la robustez.

En relación a la separación de las restricciones de robustez, luego de una pequeña adaptación

en la formulación la restricción se puede expresar como se muestra en la restricción .

Para este grupo de restricciones se utiliza un conjunto de inicialización que

corresponden a las soluciones inducidas por los escenarios del límite inferior ( ), punto medio ( )

y límite superior ( ). Dentro del proceso de ramificación en cada nodo se buscan cortes violados

utilizando el valor del conjunto de variable para generar , que es calculado como , el

valor de es utilizado como peso de las aristas para aplicar un algoritmo para solución de

, para cada solución encontrada se genera el peor escenario (Teorema 1) y para este

escenario se encuentra la solución óptima . Las soluciones entregadas por corresponden

a la solución actual y soluciones en las cuales se distorsiona el valor de a través de la

multiplicación por un número aleatorio entre

. Adicionalmente se generan soluciones

aleatorias con la generación de escenarios donde cada arista toma un valor entre

.

Para manejar la topología del problema se manejan dos conjuntos de restricciones

iniciales, las in dregree contraint y las restricciones de subtour basic

La topología dentro del proceso de ramificación es manejado a través cut-set inequalities

que son separadas a través de un algoritmo de flujo máximo como se describe en (Álvarez-Miranda

et. al, 2012).

45

El pseudocódigo del algoritmo se muestra a continuación.

Algoritmo Branch and Cut con cortes de Benders (G,c)

Input: Problema entero con un subconjunto de restricciones. Output: Solución óptima y su arrepentimiento

1. Ingresar cortes iniciales

2. Encontrar solución factible inicial ,

3. Resolver la relajación lineal (LP)

4. Hasta aquí se cumple

5. Comenzar el proceso de B&B

6. En cada nodo del B&B ingresar cortes asociado a la robustez y a la topología

7. En cada nodo del B&B aplicar heurísticas primales

8. El proceso termina cuando , cuando esto se cumpla se retorna la solución óptima.

9. Return ,

Una propuesta de mejora para este algoritmo es mejorar la calidad de los cortes de Benders

ingresados en el proceso de Branch and Bound (B&B), esta idea se basa en el apareamiento de

restricciones, para esto se utiliza un procedimiento propuesto en (Guan et al., 2005).

El esquema de apareamiento se basa en un conjunto de vectores no negativos , luego

un vector define una restricción válida si:

Dadas las dos ecuaciones válidas definidas por los vectores y , la primera definida por

domina a la definida por si para todo y , esta situación se denota

como . De acuerdo a estudios la estructura de los cortes de Benders, no es posible encontrar

dominancia entre diferentes cortes de este tipo, además se descarta que se puedan utilizar las

propiedades para restricciones anidadas (nested) y disjuntas (disjoint).

Al no contar con los casos de restricciones anidadas y disjuntas, no es posible asegurar la

dominancia de la restricción resultante en relación a las restricciones originales, pues existe un

número exponencial de secuencias de apareamiento. Sin embargo, de todas formas se

implementará un procedimiento de apareamiento, que es mostrado a continuación.

Definición: Dados con , se define el pareo de y como,

46

El pseudocódigo implementado para el algoritmo Branch and cut (B&C) con cortes de Benders

y apareamiento de restricciones es el siguiente.

Algoritmo Branch and Cut con cortes de Benders y apareamiento de cortes (G,c)

Input: Problema entero con un subconjunto de restricciones. Output: Solución óptima y su arrepentimiento

1. Ingresar cortes iniciales

2. Encontrar solución factible inicial ,

3. Resolver la relajación lineal (LP)

4. Hasta aquí se cumple

5. Comenzar el proceso de B&B

6. En cada nodo del B&B ingresar cortes asociado a la robustez y a la topología, aparear cortes

robustos.

7. En cada nodo del B&B aplicar heurísticas primales

8. El proceso termina cuando , cuando esto se cumpla se retorna la solución óptima.

9. Return ,

4.1.2 ALGORITMOS APROXIMADOS

Como se evidenció en la revisión bibliográfica, los aportes heurísticos se reducen a dos

metaheurísticas del tipo búsqueda local (SA y TS) y a las heurísticas de un escenario (hu y hm). En

relación a las metaheurísticas en el trabajo de (Kasperski et al., 2012) se menciona el esfuerzo

requerido para salir de las soluciones iniciales hu y hm. En este trabajo se propone una

metaheurísica con la capacidad demostrada de no caer en óptimos locales como lo es GRASP y

una heurística constructiva que utiliza la naturaleza del problema MMR-ST a diferencia de las

heurísticas de un escenario, esta puede ser utilizada complementariamente con GRASP o de

forma individual. Adicionalmente se implementan dos metaheurísticas de búsqueda más simples,

como lo son la mejora iterativa simple y Simulated Annealing. También son implementadas las

heurísticas de un escenario (Hu y Hm).

La metodología GRASP (Greedy Randomized Adaptive Search Procedures) es una

metaheurística para problemas de optimización combinatorial, la cual se fundamenta en la

combinación de heurísticas constructivas y de búsqueda local. Consiste básicamente en aplicar k

búsquedas locales, donde en cada búsqueda se debe partir desde una solución inicial distinta

generada a través de un proceso constructivo con aleatoriedad incorporada. Este metodología fue

47

introducida en los 80' por (Feo & Resende, 1989) y luego se formalizó en (Feo & Resende, 1995),

para revisiones detalladas de la literatura ver (Festa & Resende, 2001), (Festa & Resende, 2008) y

(Festa & Resende, 2008b).

La fase constructiva consiste en generar de forma iterativa una solución factible, añadiendo un

elemento en cada paso. Una función greedy determina la elección del elemento que se añadirá a la

solución en cada iteración, dicha función mide el beneficio de añadir cada uno de los elementos.

Adicionalmente, se dice que el heurístico greedy es adaptativo porque en cada iteración debe

actualizar los beneficios de añadir cada elemento a la solución parcial. La heurística es

aleatorizada (randomized) porque no, necesariamente, se selecciona el mejor candidato según la

función greedy adaptativa, sino que con el objetivo de dar diversidad de soluciones iniciales, se

construye una lista con los mejores candidatos seleccionando uno al azar. Luego el pseudocódigo

del algoritmo GRASP se presenta a continuación.

Algoritmo GRASP (G,c)

Input: Grafo G y función de costos c. Output: Una solución factible y su arrepentimiento 1. Fase constructiva

1.1 Generar una lista de candidatos mediante una función greedy

1.2 Considerar una lista restringida de los mejores candidatos

1.3 Seleccionar aleatoriamente un elemento de la lista restringida

2. Fase de mejora

2.1 Hacer un proceso de búsqueda local a partir de la solución

construida hasta que no se pueda mejorar más.

3. Actualización

3.1 Si la solución obtenida mejora a la mejor almacenada,

actualizarla.

Return ,

En la literatura no existe una heurística para el MMR-ST con las características que

requiere GRASP (adaptativa, aleatorizada, greedy y constructiva ), luego en este trabajo se

propone una heurística que cumple los requisitos, para poder explicar dicha heurística se deben

considerar los siguientes conceptos.

La idea inicial consiste en generar un criterio de optimización utilizando los datos

intervalares, luego se propone pasar de un grafo con costos

(Figura 1) a

un grafo con costos (Figura 2).

48

ILUSTRACIÓN 5. GRAFO G CON DATOS INTERVALARES

ILUSTRACIÓN 6. GRAFO CON NUEVO CRITERIO DE OPTIMIZACIÓN

Definición 1 (Regret local): Se tiene un grafo , donde se asume que falta agregar

sólo un nodo a la solución. Luego el aporte al regret (o regret local) de cada arista se puede

estimar como la máxima diferencia entre el límite superior de dicha arista con el límite inferior del

resto de las aristas que conectan el nodo. El regret local de cada arista se compone de dos aportes

(uno por cada nodo perteneciente a la arista), como se muestra en la figura 3.

49

ILUSTRACIÓN 7. COMPOSICIÓN DEL REGRET LOCAL

A continuación se muestra el cálculo del regret para la arista .

ILUSTRACIÓN 8. CÁLCULO DE REGRET LOCAL PARTE 1

Luego la segunda componente del Regret local se muestra en la figura 4.

50

ILUSTRACIÓN 9. CÁLCULO DEL REGRET LOCAL PARTE II

Finalmente el regret local de la arista se calcula de la siguiente forma:

Utilizando este criterio se puede generar una matriz con el aporte al regret de cada arista,

luego, una alternativa válida consiste en aplicar los algoritmos clásicos para resolver problemas de

árbol (PRIM, KRUSKAL, etc.), a esta matriz. En la experimentación se mostrará el desempeño de

dicha alternativa. Sin embargo el método mostrado anteriormente no cumple con los requisitos

para poder implementar GRASP, luego se genera un método dinámico que cada vez que se

agregue un nodo a la solución se actualice la matriz de aporte al regret, esto en base a que las

aristas ingresadas ya no deben ser utilizadas para el cálculo de los aportes, es importante

mencionar que este algoritmo también puede ser utilizado de forma individual. El pseudocódigo de

este algoritmo se presenta a continuación.

Heurística constructiva (G,c)

Input: Grafo G y función de costos c. Output: Una solución factible y su arrepentimiento

1. Generar matriz R (aporte al regret)

2. Aplicar algoritmo Prim o Kruskal para ingresar la primera arista.

3. Actualizar matriz R

4. Repetir 2 y 3 hasta que todos los nodos estén en la solución.

Return ,

51

Matemáticamente la generación de la matriz de Regret locales y la respectiva versión

dinámica se realizan siguiendo los pseudocódigos que se presentan a continuación.

Generación de Matriz

Input: Grafo , costos y matriz Output: Matriz

1. forall (i,j) E

2.

3.

4.

5.

6.

7. end forall

8. return

Algoritmo constructivo dinámico

Input: Grafo , costos y matriz Output: solution

1. forall (i,j) E

2.

3.

4.

5.

6.

7. end forall

8. select

9. add ( , ) to solution, add and to nodesolution

10. size solution = 1

11. while size

12. forall (i,j) E

13. ,

14. ,

15.

16.

17.

18. end forall

19. select in

20. add to nodesolution, add ) to solution

21. Size solution = size solution + 1

22. end while

23. return solution

52

Otro aspecto importante de los algoritmos metaheurísticos propuestos es la definición de

vecindad. En este trabajo se utilizará la propuesta en (Kasperski et al., 2012), es pseudocódigo de

esta se presenta a continuacón.

Vecindad

Input: Grafo , árbol de expansión de Output: Vecino

1.

2. Seleccionar aleatoriamente (i,j) E

3. Determinar el conjunto de aristas que están sobre el camino de a en

4. Seleccionar

5. Agregar a

6. return

Gráficamente la descripción de la vecindad se representa en las siguientes imágenes.

ILUSTRACIÓN 10. DEFINICIÓN DE VECINDARIO PARTE I

Agregar aleatoriamente una arista .

ILUSTRACIÓN 11. DEFINICIÓN DE VECINDARIO PARTE II

53

Encontrar el camino que une los nodos .

ILUSTRACIÓN 12. DEFINICIÓN DE VECINDARIO PARTE III

Seleccionar aleatoriamente una arista dentro del camino y eliminarla.

ILUSTRACIÓN 13. DEFINICIÓN DE VECINDARIO PARTE IV

Es importante mencionar que el costo de la nueva solución puede ser calculada de una forma

eficiente en función de la solución anterior de la siguiente forma.

Donde corresponde a la arista agregada a la nueva solución y corresponde a la arista

eliminada.

54

CAPÍTULO V: EXPERIMENTACIÓN Y ANÁLISIS DE

RESULTADOS

En este capítulo se estudia el desempeño de los diferentes algoritmos implementados, además se describen los diferentes conjuntos de instancias estudiadas.

55

5.1 DESCRIPCIÓN DE INSTANCIAS

Para la experimentación se utilizó un subconjunto de las instancias propuestas en (Kasperski et al.,

2012), se utilizaron aquellas instancias clasificadas como dificiles (Ya, He0, He1, La y Mo) en el

trabajo antes mencionado, a continuación se describirán los cinco conjuntos de instancias

utilizadas.

Ya( , )- : Grafo completo con nodos. Para cada arista es uniformemente

distribuido en y es uniformemente distribuido en el intervalo

, esta clase de instancias

fue propuesta en (Yaman et al., 2001). Existen dos estructuras de costos dentro de este grupo de

instancias (Ya(C,C) y Ya(C,2C)), que por lo demás tienen un impacto en el rendimiento de los

algoritmos, especialmente es el caso de los exactos, en la siguiente tabla se presentan las

variantes utilizadas en la literatura para este conjutno.

TABLA 1. ESTRUCTURA DE COSTOS INSTANCIAS TIPO YAMAN

Set 1 Set 2 Set 3 Set 4 Set 5 Set 6

[0,10) [0,15) [0,20) [0,10) [0,15) [0,20)

( , 10] ( , 15] ( , 20] ( , 20] ( , 30] ( , 40]

He0-n : Esta clase de instancias fue introducida en (Aron & Van Hentenryck, 2002). Un

Grafo representa una red de dos niveles. El nivel inferior consiste de clusters (grafos completos)

de 5 nodos cuyas aristas son generadas como en la clase Ya(10,10)- . El nivel superior vincula los

clusters y estas aristas tienen costos más altos de acuerdo a Ya(10,10)- desplazado por una

constante. En esta clase los grafos son completos y representa el número de nodos en G, que a

la vez representa un múltiplo entero de 5, estas instancias son mostradas en (Kasperski et al.,

2012) como He1-n.

He1-n : Esta clase de instancias también fue introducida en Aron & Van Hentenryck (2002).

y son similares a He0-n, con la excepción de que los vínculos del nivel inferior con el nivel superior

están organizados como un árbol binario, estas instancias son mostradas por (Kasperski et al.,

2012) como He2-n.

Mo(p)-n: Grafo completo con nodos. Estos nodos son aleatoriamente localizados

sobre una grilla de 50 x 50. Para cada arista es seleccionado aleatoriamente en el

intervalo y es generado aleatoriamente en el intervalo

, donde

es la distancia euclidiana entre y , y es el parámetro de distorsión. Esta clase instancia fue

estudiada e introducida en (Montemanni & Gambardella, 2005).

La-n : Grafo con nodos, se compone de tres capas. La primera capa está formada por

un grafo completo . La segunda capa está compuesta por nodos, cada nodo de esta

56

capa se conecta con dos nodos (elegidos aleatoriamente) de la primera capa. Finalmente la tercera

capa, contiene un nodo que es conectado con cada nodo de la segunda capa. Todos los intervalos

de costos son . Grafos de este tipo aparecen en (Averbakh & Lebedev, 2004) . En (Kasperski

et al., 2012) clasifican este conjunto de instancias como las más complejas del grupo estudiado.

Cabe mencionar que cada uno de los grupos de instancias posee 10 instancias generadas

bajo el mismo criterio además los tamaños de las instancias que se estudiarán van desde 10 nodos

hasta 100 nodos, éstas fueron entregadas directamente por los autores del trabajo (Kasperski et

al., 2012)1.

Todos los algoritmos fueron implementados en C++ utilizando Leda en su versión libre2,

para los algoritmos exactos se utilizó la versión IBM ILOG CPLEX Optimization Studio V12.3 y la

máquina utilizada tiene un procesador Intel Core i7-3610QM con 8 GB de RAM.

5.2 PREPROCESAMIENTO

Este análisis consiste en la evaluación del efecto del pre procesamiento, en los diferentes

conjuntos de instancias lo cual también se ha analizado en otros trabajos. Para esto se consideran

promedios de los conjuntos de instancias. Los indicadores utilizados para el análisis son; tamaño

del problema , número de aristas iniciales , promedio de aristas finales , porcentaje promedio

de reducción de aristas , promedio de aristas fuertes y porcentaje promedio de aristas

fuertes . Un segmento de los resultados del pre procesamiento se presentan en las tablas 2 y

3.

Las instancias Mo(0.15) son las que tienen un mayor promedio de aristas fuertes, seguido

por Mo(0.5). Los conjuntos de instancias que tienen menor promedio de aristas fuertes son las Ya.

Con respecto al tamaño del grafo reducido, el conjunto de instancias donde se obtiene el menor

número de aristas son Mo(0.15) y Mo(0.5), transformándose en los conjuntos de instancias más

favorecidos con el pre procesamiento, por ejemplo para Mo(0.15)-30 se tiene en promedio un grafo

final de 38 aristas (solución con 29 aristas) y además 22 aristas están fijas en la solución (aristas

fuertes). Los conjuntos de instancias donde se reduce en menor grado el número de aristas son la

Ya, luego este conjunto de instancias es donde el pre procesamiento tiene un menor impacto.

Con respecto a las instancias He, se puede decir que se encuentran en una posición

intermedia entre Mo(0.15) y las instancias Ya. En el subconjunto He1 el pre procesamiento,

específicamente la reducción, tiene un mayor impacto que en He0, en relación al número de aristas

fuertes se observa un impacto similar. En las instancias Mo(0.85) el pre procesamiento tiene un

1 http://mariusz.makuchowski.staff.iiar.pwr.wroc.pl/www/research/robust.tree/

2 http://www.algorithmic-solutions.com/leda/

http://mariusz.makuchowski.staff.iiar.pwr.wroc.pl/www/research/robust.tree/

57

impacto similar (levemente mejor) a las instancias Ya. Es importante mencionar que para el

conjunto de instancias La el pre procesamiento no tiene ningún efecto.

Al ordenar de mayor a menor impacto del pre procesamiento los conjuntos analizados, se

tiene la siguiente lista: Mo(0.15), Mo(0.5), He1, He0, Mo(0.85), Ya y La. Posteriormente en el

análisis de los algoritmos estudiados se observará que este orden se relaciona casi perfectamente

con el orden en relación a la dificultad del tipo de instancia.

TABLA 2. PRE PROCESAMIENTO DE INSTANCIAS HE Y MO

N

He0-20 20.00 190.00 58.20 69.37% 4.90 2.58%

He0-30 30.00 435.00 98.70 77.31% 8.30 1.91%

He0-40 40.00 780.00 158.20 79.72% 9.90 1.27%

He1-20 20.00 190.00 45.10 76.26% 4.40 2.32%

He1-30 30.00 435.00 72.10 83.42% 6.00 1.38%

He1-40 40.00 780.00 97.80 87.46% 7.70 0.99%

Mo(0.15)-20 20.00 190.00 24.50 87.11% 15.10 7.95%

Mo(0.15)-30 30.00 435.00 38.20 91.22% 22.30 5.13%

Mo(0.15)-40 40.00 780.00 52.20 93.31% 29.60 3.79%

Mo(0.50)-20 20.00 190.00 44.60 76.53% 8.20 4.32%

Mo(0.50)-30 30.00 435.00 70.20 83.86% 12.00 2.76%

Mo(0.50)-40 40.00 780.00 98.00 87.44% 16.20 2.08%

Mo(0.85)-20 20.00 190.00 76.30 59.84% 3.90 2.05%

Mo(0.85)-30 30.00 435.00 133.20 69.38% 4.60 1.06%

Mo(0.85)-40 40.00 780.00 193.80 75.15% 7.40 0.95%

TABLA 3. PRE PROCESAMIENTO DE INSTANCIAS YA

N

Ya(10-10)-20 20.00 190.00 79.70 58.05% 0.90 0.47%

Ya(10-10)-30 30.00 435.00 148.80 65.79% 0.50 0.12%

Ya(10-10)-40 40.00 780.00 229.50 70.58% 0.80 0.10%

Ya(15-15)-20 20.00 190.00 114.00 40.00% 0.60 0.32%

Ya(15-15)-30 30.00 435.00 213.40 50.94% 0.40 0.09%

Ya(15-15)-40 40.00 780.00 331.90 57.45% 0.30 0.04%

Ya(10-20)-20 20.00 190.00 76.50 59.74% 1.40 0.74%

Ya(10-20)-30 30.00 435.00 137.90 68.30% 1.50 0.34%

Ya(10-20)-40 40.00 780.00 215.80 72.33% 1.10 0.14%

Ya(15-30)-20 20.00 190.00 105.70 44.37% 1.00 0.53%

Ya(15-30)-30 30.00 435.00 214.80 50.62% 0.60 0.14%

Ya(15-30)-40 40.00 780.00 330.30 57.65% 0.80 0.10%

58

5.3 ALGORITMOS EXACTOS

Debido a que se tiene una propuesta amplia de algoritmos exactos, su análisis se realizará de

manera parcializada, la primera etapa consiste en evaluar la bondad de las variantes de los

algoritmos de descomposición de Benders. Recordando la propuesta algorítmica se tienen tres

alternativas, el algoritmo de Descomposición de Benders básico (BBD), la versión con la

incorporación de cortes heurísticos (HBD) y la alternativa que incorpora los cortes de las soluciones

incumbentes en la resolución del maestro en cada iteración (EBD). La segunda etapa consistirá en

evaluar el mejor algoritmo del tipo Benders con el algoritmo B&C y el MILP, finalmente la tercera y

última etapa consiste en evaluar el rendimiento del algoritmo B&C para instancias de mayor

tamaño. Para las instancias del tipo La, se presenta un análisis separado, donde se compara la

eficiencia del B&C y el MILP para instancias de hasta 50 nodos; es importante recordar que este

conjunto de instancias es el conjunto que generó mayores problemas a (Kasperski, et al., 2012).

5.3.1 EVALUACIÓN DE VARIANTES DE DESCOMPOSICIÓN DE BENDERS

La experimentación se realiza con instancias de 10, 20 y 30 nodos, para las instancias del tipo

(He0, He1, Mo(0.15), Mo(0.5), Mo(0.85), Ya(10,10), Ya(10,20), Ya(15,15) y Ya(15,30)), cada una

de estas familias de instancias se conforma por 10 instancias generadas bajo las mismas

condiciones. Los análisis para cada familia de instancias (He, Ya y Mo) se realizan por separado,

debido a las diferencias en los desempeños de los algoritmos para cada familia.

En primer lugar se hace un análisis de los tiempos de ejecución para aquellas instancias

donde se logra llegar al óptimo dentro del tiempo límite; en este análisis se considera la instancia

resuelta en el menor tiempo para cada grupo (min), el promedio de los tiempos de las instancias

resueltas dentro del tiempo límite (Av.), la instancia que se resuelve en el tiempo mayor (Max) y

por último se muestra el número de instancias que son resueltas dentro del tiempo límite. Se

considera un tiempo límite de 3.600 segundos.

De la tabla 4 se puede observar que la versión básica del algoritmo de Benders (BBD) es la

que presenta el peor desempeño, siendo dominada en todas las dimensiones evaluadas por

ambas variantes (EBD y HBD). En relación a las variantes propuestas no existe una dominación

por parte de ninguno de los algoritmos. Por ejemplo para las instancias del tipo He1 tanto para 20

como para 30 nodos la versión de Benders con cortes heurísticos (HBD) es la que presenta un

mejor desempeño, tanto en los promedio como en el tiempo máximo. Para las instancias del tipo

He0 los rendimientos son similares con un pequeño margen de ganancia para la versión de

Benders con cortes de soluciones incumbentes (EBD).

Para las instancias del tipo Mo (tabla 5), el desempeño de la versión básica del Benders

(BBD) es dominado en todas las dimensiones por las variantes propuestas, al igual que para el

59

caso de las instancias He. En relación a las variantes, existe un pequeño margen de dominancia

por parte de EBD tanto en los tiempos mínimos como en los promedios. En los tiempos máximos

para gran parte de las instancias es mejor, salvo en los grupos de instancias Mo(0.85) para 20 y 30

nodos donde HBD supera a EBD por aproximadamente 100 y 200 segundos respectivamente,

cabe destacar que el conjunto de instancias (Mo(0.85)) ya con 30 nodos comienza a mostrar su

complejidad. Más adelante se mostrará como uno de los más complejos en estudio.

TABLA 4. TIEMPOS DE EJECUCIÓN HE PARA VARIANTES DE BENDERS RESUELTAS AL ÓPTIMO

BBD EBD HBD

Min Av. Max N Min Av. Max N Min Av. Max N

He0-10 0.12 0.45 1.9 10 0.11 0.34 1.33 10 0.06 0.32 1.19 10

He0-20 1.31 63.12 275.39 10 0.64 46.63 214.56 10 1.25 51.22 240.47 10

He0-30 170.31 1445.07 3176.55 6 104.71 1089.13 2403.56 6 121.51 1045.1 2450.07 6

He1-10 0.13 0.45 1.98 10 0.1 0.31 1.32 10 0.08 0.31 1.18 10

He1-20 2.55 56.92 353.47 10 1.46 34.12 220.6 10 1.4 33.11 197.26 10

He1-30 119.92 1064.08 3443.77 7 56.78 811.69 2740.43 7 65.06 706.5 2471.73 7

Las instancias Ya (tabla 6) se pueden subdividir en dos tipos, Ya(C,C) y Ya(C,2C), luego se

puede observar que la dificultad de las primeras es significativamente superior para los algoritmos

analizados en este momento. En relación al número de instancias resueltas en tiempo límite cabe

destacar que EBD es el ganador, en primer lugar en las instancias Ya(15-30)-30 resuelve 6

instancias y los otros algoritmos sólo resuelven 2, además no es dominado en ningún grupo de

instancias en esta dimensión. Las instancias del grupo Ya(10,10)-30 son de gran dificultad y ningún

algoritmo logra resolver alguna. La versión básica BBD es dominada en el número de instancias

resueltas para los grupos Ya(15,15)-20 y Ya(10,20)-20. En general los tiempos de EBD son

menores, pero esto se ve acentuado en algunos grupos de instancias (por ejemplo en Ya(15,30)-

20, Ya(10,20)-30 y Ya(10,20)-20).

TABLA 5. TIEMPO DE EJECUCIÓN PARA INSTANCIAS MO CON VARIANTES DE BENDERS

BBD EBD HBD


Mo(0.15)-10 0.02 0.05 0.16 10 0.02 0.03 0.08 10 0.02 0.03 0.05 10

Mo(0.15)-20 0.02 0.13 0.41 10 0.02 0.09 0.22 10 0.02 0.09 0.18 10

Mo(0.15)-30 0.05 1.03 3.53 10 0.03 0.66 2.01 10 0.04 0.72 2.32 10

Mo(0.50)-10 0.03 0.1 0.23 10 0.03 0.09 0.19 10 0.04 0.09 0.23 10

Mo(0.50)-20 0.61 7.57 42.7 10 0.36 5.72 35.24 10 0.49 6.07 36.31 10

Mo(0.50)-30 11.57 144.65 528.34 10 4.73 94.36 357.58 10 7.52 98.53 390.93 10

Mo(0.85)-10 0.03 0.22 0.8 10 0.03 0.16 0.52 10 0.03 0.18 0.71 10

Mo(0.85)-20 2.08 208.28 1803 10 0.84 167.59 1502.53 10 1.94 164.1 1419.39 10

Mo(0.85)-30 67.64 653.65 1924.25 6 48.27 496.09 1672.29 6 62.75 522.81 1484.06 6

60

TABLA 6. TIEMPOS DE EJECUCIÓN PARA INSTANCIAS YA CON VARIANTES DE BENDERS

BBD EBD HBD


Ya(10-10)-10 0.28 1.9 9.776 10 0.26 1.31 6.19 10 0.18 1.47 7.13 10

Ya(10-10)-20 158.51 770.17 1815.06 3 84.83 472.81 1125.96 3 115.26 547.18 1291.93 3

Ya(15-15)-10 0.08 4.56 26.55 10 0.08 2.94 16.52 10 0.1 3.13 17.31 10

Ya(15-15)-20 169.65 1515.54 3585.49 6 64.15 1203.96 2385.04 7 103.64 1351.43 3363.17 7

Ya(15-15)-30 1439.93 1439.93 1439.93 1 800.37 800.37 800.37 1 1449.05 1449.05 1449.05 1

Ya(10-20)-10 0.29 4.13 12.91 10 0.18 2.76 9.01 10 0.22 3.12 10.99 10

Ya(10-20)-20 41.69 393.2 1244.02 9 17.58 355.57 1847.4 10 22.96 561.59 2575.91 10

Ya(10-20)-30 1326.47 1583.7 1840.93 2 927.16 1052.19 1177.22 2 1275.3 1395.9 1516.5 2

Ya(15-30)-10 0.56 7.87 53.79 10 0.26 5.86 42.44 10 0.41 7.08 51.39 10

Ya(15-30)-20 45.18 205.75 532.51 10 27.56 111.13 316.54 10 40.92 228.23 665.91 10

Ya(15-30)-30 553.92 1005.93 1457.93 2 332.93 1710.65 3089.89 6 488.3 1008.55 1528.8 2

El siguiente análisis es complementario y corresponde a la evaluación de los gaps de

aquellas instancias donde no se logró llegar al óptimo, luego en éste se indica el número de

instancias que llegaron al óptimo de un total de 10 por grupo, se muestra además el gap relativo

entre el UB y LB del algoritmo y finalmente se muestra el gap en relación al mejor de los tres

algoritmos. A continuación se presenta el cálculo de ambos gaps.

El cálculo de las desviaciones utilizadas está dado por, y

, donde corresponde al valor de la mejor solución; puede ser la mejor solución

conocida o la mejor en relación a los algoritmos analizados, para este análisis corresponde a la

mejor en relación a los tres algoritmos analizados.

Para las instancias del tipo He como para las Mo son pocos los grupos donde no se logran

resolver todas (2 He y 1 Mo), adicionalmente los gaps entregados son bastante buenos. De la

tabla 7 se puede apreciar que para estos grupos de instancias el LB provisto por BBD es de menor

calidad, lo cual se fundamenta en el hecho de que el gap de este algoritmo es 0 para los tres

grupos de instancias. Luego su UB es similar al de HBD, por lo que su gap* es mayor por tener un

LB menor.

De la tabla 8 se puede observar que EBD domina a los dos algoritmos restantes en la

dimensión gap* en la mayoría de los grupos de instancias, salvo en Ya(15-15)-20. Entonces, esto

indica que el LB provisto por este algoritmo es superior al de los dos restantes más aun si se

considera que existen grupos donde los otros algoritmos tienen mejor UB (Ya(10-10)-20, Ya(10-

10)-30 y Ya(15-15)-30). En relación al UB medido a través del gap, la versión que obtiene los

mejores resultados para la mayor parte de las instancias (salvo Ya(10-10)-20 y Ya(15-15)-20) es

EBD.

61

TABLA 7. GAP DE INSTANCIAS HE Y MO PARA VARIANTES DE BENDERS SIN OPTIMALIDAD

BBD EBD HBD

N GAP* GAP N GAP* GAP N GAP* GAP

He0-30 6 2% 0% 6 2% 1% 6 1% 0%

He1-30 7 3% 0% 7 2% 0% 7 2% 0%

Mo(0.85)-30 6 1% 0% 7 1% 0% 6 1% 0%

TABLA 8. GAP PARA INSTANCIAS YA CON VARIANTES DE BENDERS

BBD EBD HBD


Ya(10-10)-20 3 4% 0% 3 3% 1% 3 3% 0%

Ya(10-10)-30 0 22% 1% 0 21% 2% 0 23% 2%

Ya(15-15)-20 6 2% 0% 7 2% 1% 7 1% 0%

Ya(15-15)-30 1 20% 2% 1 17% 2% 1 20% 3%

Ya(10-20)-30 2 14% 3% 3 10% 2% 2 13% 3%

Ya(15-30)-30 2 13% 7% 6 6% 1% 2 12% 6%

Otro análisis importante puede ser realizado graficando el porcentaje de instancias

resueltas en el tiempo; en el Gráfico 1 se presenta una agregación de todas las instancias

evaluadas bajo este análisis. Se puede observar que EBD (cruz roja) se encuentra durante todo el

intervalo evaluado sobre el resto de los algoritmos (BBD y HBD), adicionalmente se aprecia que es

el algoritmo que resuelve en el óptimo el mayor porcentaje de instancias. Por otra parte se observa

que la versión básica de Benders se encuentra por debajo de los otros algoritmos en todo el

intervalo evaluado. Cabe destacar que este análisis es complementario al de porcentaje acumulado

de instancias en función del gap final, es decir, el porcentaje acumulado de instancias para un gap

dado. Del gráfico 2 se puede observar, al igual que en el gráfico 1, que el algoritmo EBD es el que

presenta un mejor desempeño. Esto se basa principalmente en el hecho que siempre tiene un

porcentaje acumulado de instancias mayor para todo gap y además tiene un umbral de gap menor,

pues tiene el 100% de las instancias con gap menor o igual a un 45% (última cruz roja). De

acuerdo al análisis anterior (tablas y gráficos), considerando la dominancia en los tiempos para la

mayor parte de las instancias, la bondad de ambos indicadores de desviación porcentual (gap y

gap*) y el análisis gráfico, se puede concluir que de las variantes de Benders la que presenta un

mejor desempeño es EBD, por lo que de manera natural será el algoritmo seleccionado para medir

su desempeño con B&C y MILP.

62

GRÁFICO 1. PERFIL DE DESEMPEÑO DE LOS TIEMPOS DE RESOLUCIÓN

GRÁFICO 2. PORCENTAJE ACUMULADO DE INSTANCIAS PARA UN GAP DADO

63

5.3.2 ANÁLISIS MILP, EBD Y B&C

Como se mencionó anteriormente la siguiente etapa consiste en comparar el rendimiento del mejor

representante de los algoritmos tipo Benders (EBD), con el MILP y el algoritmo Branch and Cut

(B&C). Este análisis considera instancias de tamaño 20, 30 y 40, para los mismos conjuntos de

instancias que la etapa 1, esto principalmente debido a que es, en este intervalo, donde todos los

algoritmos exactos propuestos en la literatura comienzan a perder efectividad. A continuación se

presenta un análisis de tiempos para cada una de las familias de instancias antes mencionadas.

Para la familia de instancias del tipo He (tabla 9) se puede hacer un primer análisis en

relación al B&C comparado con el EBD, en este contexto se puede observar que EBD es dominado

completamente por B&C y esto se ve reflejado en el número de instancias resueltas dentro del

tiempo límite (He0-30, He0-40, He1-30 y He1-40). Otro análisis está relacionado al rendimiento del

MILP en comparación con el B&C, acá no se observa dominancia, pues para las instancias del He0

B&C logra un desempeño notoriamente superior al MILP, por ejemplo en He0-20 se observa una

diferencia significativa en los tiempos promedio, luego para He0 con 30 y 40 nodos el MILP explota

y no logra resolver ni siquiera una instancia donde el B&C resuelve las 10 y 7, respectivamente.

Para el subconjunto He1 el MILP tiene un rendimiento mejor a B&C obteniendo mejores tiempos y

más importante aún, resolviendo una mayor cantidad de instancias en He1-40. Si bien B&C no

logra dominar al MILP las ocasiones donde el MILP explota son bastante más drásticas que las

oportunidades donde el B&C es superado.

TABLA 9. TIEMPOS DE EJECUCIÓN INSTANCIAS HE PARA MILP, EBD Y B&C

MILP EBD B&C


He0-20 4.41 25.38 142.29 10 0.64 46.63 214.56 10 0.08 1.93 5.68 10

He0-30 - - - 0 104.71 1089.13 2403.56 6 4.98 114.67 578.11 10

He0-40 - - - 0 2220.6 2220.6 2220.6 1 189.28 1759.71 3069.07 7

He1-20 0.3 3.1 8.92 10 1.46 34.12 220.6 10 0.19 1.41 7.07 10

He1-30 4.28 38.88 145.24 10 56.78 811.69 2740.43 7 3.39 306.03 1487.95 10

He1-40 21.81 312.2 1227.26 9 600.24 600.24 600.24 1 46.3 1218.34 2154.09 5

Para las instancias del tipo Mo (tabla 10) se puede observar que existe una dominancia

absoluta por parte del B&C tanto en relación al MILP como al EBD, esto se ve reflejado tanto en las

dimensiones de tiempo como en el número de instancias resueltas dentro del tiempo límite. Se

pueden observar diferencias dramáticas por ejemplo en los tiempos mínimos para los grupos de

instancias Mo(0.85)-40, Mo(0.85)-30 y Mo(0.50)-40, caso similar ocurre en los tiempos promedios

en las instancias Mo(0.85)-30 y Mo(0.50)-40.

64

TABLA 10. TIEMPO DE EJECUCIÓN INSTANCIAS MO PARA MILP, EBD Y B&C

MILP EBD B&C


Mo(0.15)-20 0.03 0.05 0.09 10 0.02 0.09 0.22 10 0.02 0.02 0.03 10

Mo(0.15)-30 0.06 0.61 3.7 10 0.03 0.66 2.01 10 0.02 0.06 0.17 10

Mo(0.15)-40 0.19 2.69 15.99 10 0.11 2.93 23.72 10 0.03 0.35 2.39 10

Mo(0.50)-20 0.19 2.33 11.08 10 0.36 5.72 35.24 10 0.05 0.25 1.14 10

Mo(0.50)-30 2.62 31.69 93.33 10 4.73 94.36 357.58 10 0.47 3.14 7.64 10

Mo(0.50)-40 73.04 811.52 3533.03 9 43.46 309.94 777.03 7 6.66 139.63 776.26 10

Mo(0.85)-20 1.39 31.99 177.84 10 0.84 167.59 1502.53 10 0.11 2.53 16.97 10

Mo(0.85)-30 124.16 591.97 1699.9 10 48.27 496.09 1672.29 6 1.16 40.3 104.47 10

Mo(0.85)-40 1300.52 2264.99 3229.47 2 481.03 1375.58 2270.13 2 29.03 324.37 1131.38 7

En las instancias Ya (tabla 11) a diferencia de lo que sucede en las instancias He0 y en la

línea de lo observado en He1, se observa que el algoritmo EBD es claramente superado por el

MILP, esto se puede corroborar analizando el número de instancias resueltas dentro del tiempo

límite (EBD 39/120 y MILP 97/120), adicionalmente en las ocasiones donde logra resolver las diez

de algún grupo (Ya(10-20)-20 y Ya(15-30)-20)) las diferencias en los indicadores (Min, Av. y Max)

son notoriamente favorables para el MILP.

En relación al B&C, éste logra obtener un número similar de instancias (Ya) resueltas

dentro del tiempo límite (97/120), sin embargo se observa una clara diferencia entre el desempeño

para las subcategorías de la familia Ya (Ya(C,C) y Ya(C,2C)). MILP logra mejores resultados en las

Ya(C,C) y el B&C en Ya(C,2C), sin embargo los tiempos mínimos son obtenidos en la mayoría de

los conjuntos de instancias (salvo Ya(15,15)-40) por B&C.

A la luz de los resultados, específicamente en el número de instancias resueltas dentro del

tiempo límite, se pueden inferir algunas cosas; por ejemplo los incrementos en el tamaño, afectan

de forma dramática al MILP y en menor grado al B&C, esto se basa en el hecho de que no son

poco frecuentes los casos donde se pasa de 10 a un número menor a 4 en la columna N, a

diferencia del B&C donde los cambios no son tan bruscos. Complementario a ésto, en el MILP se

observan cambios en los tiempos mínimos de hasta dos órdenes de magnitud al aumentar el

tamaño del problema.

En el caso del las instancias Ya(10-10) se puede observar algo interesante: para 10 nodos

el MILP es notoriamente superior en tiempos, luego para 20 nodos es superior en tiempo e incluso

en la cantidad de instancias resueltas. Sin embargo, al aumentar a 30 nodos se observa el

deterioro dramático del MILP pues el rendimiento en número de instancias resueltas es similar al

del B&C e incluso este último obtiene mejores tiempos.

65

A favor del MILP se puede decir que en general para este algoritmo existe una menor

diferencia entre el tiempo mínimo y máximo.

TABLA 11. TIEMPOS DE EJECUCIÓN INSTANCIAS YA PARA MILP, EBD Y B&C

MILP EBD B&C


Ya(10-10)-20 2.71 35.51 78.562 10 84.83 472.81 1125.96 3 3.7 108.62 358.6 10

Ya(10-10)-30 83.91 367.65 887.802 10 - - - 0 33.41 623.2 1377.49 6

Ya(10-10)-40 1653.33 1701.32 1749.3 2 - - - 0 781.77 802.62 823.47 2

Ya(15-15)-20 3.81 23.49 80.75 10 64.15 1203.96 2385.04 7 2.65 66.9 208.62 10

Ya(15-15)-30 26.41 527.29 2664.37 10 800.37 800.37 800.37 1 14.13 983.02 3414.71 7

Ya(15-15)-40 716.18 2010.39 3551.5 8 - - - 0 810.24 2417.9 3298.3 4

Ya(10-20)-20 3.7 17.37 38.64 10 17.58 355.57 1847.4 10 1.86 11.71 48.34 10

Ya(10-20)-30 241.97 489.96 896.43 10 927.16 1052.19 1177.22 2 10.2 269.82 1853.79 10

Ya(10-20)-40 1698.34 2426.23 3331.62 3 - - - 0 64.99 977.33 3468.06 9

Ya(15-30)-20 6.19 24.46 74.26 10 27.56 111.13 316.54 10 1.22 7.32 21.51 10

Ya(15-30)-30 92.06 354.11 672.57 10 332.93 1710.65 3089.89 6 14.87 97.48 240.37 10

Ya(15-30)-40 1673.33 2277.24 2878.31 4 - - - 0 52.07 1079.29 3487.28 9

En relación al gap se puede observar que el MILP muestra grandes problemas de

convergencia en las instancias del tipo He0 (tabla 12), pues se muestra que los indicadores de

desviación porcentual son incluso superiores al 100% cuando se analizan sus cotas (LB y UB),

para el caso de He0-30 se observa un caso particular (gap*=117% y gap=0%), después de un

análisis se confirmó que la situación se debe a que la cota inferior (LB) toma valores muy malos y

esta desviación es producto de esta cota, pues el UB es similar al encontrado por el mejor

algoritmo (B&C). Para este tipo de instancias (He0) incluso se observa que el algoritmo de Benders

(EBD) entrega mejores resultados que el MILP, pero B&C siempre es mejor al EBD. Para el

conjunto He1-40 MILP es quien entrega los mejores resultados.

Para las instancias Mo (tabla 13) se puede observar claramente el impacto de la

incertidumbre (amplitud del intervalo) en la dificultad del problema, pues para un parámetro de

distorsión de 0.15 ningún algoritmo presenta problemas incuso con 40 nodos, sin embargo ya con

un parámetro de distorsión de 0.5 tanto el EBD como el MILP comienzan a presentar dificultades

para obtener la solución óptima dentro del tiempo límite. Con un parámetro de distorsión mayor o

igual a 0.85 tanto el MILP como EBD logran resolver un porcentaje muy pequeño de instancias y lo

que es aún peor entregan gaps mayor al 10%. La distorsión porcentual en relación al LB (gap*) es

en promedio de un 2% lo que entrega información respecto a la calidad del LB del algoritmo.

66

TABLA 12. DESVIACIÓN PORCENTUAL INSTANCIAS HE PARA MILP, EBD Y B&C

MILP EBD B&C


He0-30 0.00 117% 0% 6.00 2% 1% 10.00 0% 0%

He0-40 0.00 207% 42% 1.00 27% 21% 7.00 3% 0%

He1-40 9.00 0% 0% 1.00 21% 11% 4.00 4% 2%

TABLA 13. DESVIACIÓN PORCENTUAL INSTANCIAS MO PARA MILP, EBD Y B&C

MILP EBD B&C


Mo(0.50)-40 9.00 0% 0% 7.00 6% 6% 10.00 0% 0%

Mo(0.85)-40 2.00 15% 14% 2.00 22% 11% 7.00 2% 0%

Para las instancias del tipo Ya (20 a 40 nodos) en primer lugar se puede observar (tabla

14) que EBD es dominado completamente por B&C en todas las dimensiones a evaluar, también

se puede apreciar que los indicadores de desviación en el B&C son menores que para el MILP

para el caso del subconjunto Ya(C,2C) y mayores en el subconjunto Ya(C,C), un caso particular

sucede en Ya(10-20)-40 donde el MILP en 2 instancias no logra encontrar una solución factible (*).

TABLA 14. DESVIACIÓN PORCENTUAL INSTANCIAS YA PARA MILP, EBD Y B&C

MILP EBD B&C


Ya(10-10)-20 10.00 0% 0% 3.00 3% 1% 10.00 0% 0%

Ya(10-10)-30 10.00 0% 0% 0.00 21% 17% 6.00 2% 0%

Ya(10-10)-40 2.00 4% 0% 0.00 34% 20% 2.00 7% 0%

Ya(15-15)-20 10.00 0% 0% 7.00 2% 1% 10.00 0% 0%

Ya(15-15)-30 10.00 0% 0% 1.00 17% 13% 7.00 1% 0%

Ya(15-15)-40 8.00 0% 0% 0.00 30% 24% 3.00 5% 5%

Ya(10-20)-30 10.00 0% 0% 3.00 10% 10% 10.00 0% 0%

Ya(10-20)-40 3(2*) 7% 3% 0.00 23% 20% 9.00 3% 0%

Ya(15-30)-30 10.00 0% 0% 6.00 6% 6% 10.00 0% 0%

Ya(15-30)-40 4.00 9% 5% 0.00 30% 28% 9.00 0% 0%

En los gráficos 3 y 4 se presentan las instancias de forma agregada, en primer lugar se

presenta el gráfico de porcentaje de instancias resueltas versus tiempo y posteriormente se analiza

el gráfico de porcentaje acumulado de instancias para un gap dado. Del gráfico 3 se puede

observar, en primer lugar que B&C es el algoritmo que resuelve la mayor cantidad de instancias

dentro del tiempo límite (85%). Además, es el algoritmo que domina al MILP y EBD para todo el

intervalo evaluado. El algoritmo que presenta un peor desempeño es el EBD.

De la ilustración 4 de forma complementaria se puede observar lo que sucede con los gaps

de aquellas instancias que no son resultas en el óptimo, luego se aprecia que los gaps del B&C

67

son menores pues el 100% de las instancias tiene un gap menor o igual 25% (aprox.) en

comparación con al 65% del EBD y dramático 200% del MILP. Por otra parte se aprecia que el

EBD a través de un análisis de gaps finales agregados de las instancias logra superar al MILP,

pues sus gaps máximos son menores.

A través de esta experimentación se pudo observar en primer lugar que el algoritmo B&C

es superior al EBD para todos los conjuntos de instancias y en todas las dimensiones evaluadas.

Es posible constatar también que para cierto conjunto de instancias el algoritmo B&C es

notoriamente superior al MILP (Ya(C,2C), He0 y Mo). Sin embargo, para dos grupos de instancias

no se nota con claridad la supremacía del B&C (Ya(C,C) y He1). También se pudo verificar que el

incremento en el tiempo del MILP tiende a crecer más bruscamente que en el caso del B&C; por

ende se puede inferir que su eficiencia disminuye en mayor proporción, lo que se complementa con

el análisis gráfico del gap donde el MILP muestra que para un porcentaje de instancias puede

generar gaps muy grandes.

Luego es posible concluir que el EBD deja de ser competitivo para instancias de más de 40

nodos como se menciona en la literatura. Además, el MILP tiene conjuntos de instancias para los

cuales simplemente deja de ser alternativa como lo son Ya(C,2C) y He0, pues para el primer caso

existen instancias donde no se obtiene solución factible y para el segundo caso entrega gaps sobre

el 100%, que de acuerdo a lo descrito en la experimentación radican principalmente en la calidad

del LB.

68

GRÁFICO 3. PORCENTAJE ACUMULADO DE INSTANCIAS V/S TIEMPO PARA MILP, EBD Y B&C

GRÁFICO 4. PORCENTAJE ACUMULADO DE INSTANCIAS V/S GAP PARA MILP, EBD Y B&C

69

5.3.3 ANÁLISIS DEL COMPORTAMIENTO DE B&C

Un tercer análisis consiste en analizar el rendimiento del algoritmo branch and cut y la variante con

pairing inequalities para instancias de mayor tamaño. Para este análisis se considerarán todo el

conjunto de instancias seleccionadas en un principio hasta 50 nodos y un subconjunto (He0,

Mo(0.85), Ya(10-20) y Ya(10-10)) incluye instancias de 60, 80 y 100 nodos. El primer análisis

consiste en determinar indicadores en relación al tiempo y además evaluar si el procedimiento de

pairing ayuda o no a la convergencia del algoritmo. En la tabla 15 en relación al tiempo y número

de instancias resueltas, se resuelven instancias de tamaño 50 (Ya(20-20)). Según la literatura, ésto

no era posible con los algoritmos propuestos. Por otra parte el procedimiento de pairing ayuda en

un alto porcentaje de la veces incluso en ocasiones aumenta el número de instancias resueltas

dentro del tiempo límite (Ya(20-20)-30 y Ya(10-20)-40), sin embargo se observó un grupo donde el

pairing fue perjudicial pues disminuyó el número de instancias resueltas dentro del tiempo límite.

TABLA 15. ANÁLISIS DE TIEMPO DE B&C PARA INSTANCIAS YA DE MAYOR TAMAÑO

B&C B&C p

Ayuda

Min Av. Max N Min Av. Max N

Ya(10,10)-30 33.41 623.2 1377.49 6 29.87 585.31 1243 6 Si

Ya(10,10)-40 781.77 802.62 823.47 2 598.34 672.38 746.42 2 Si

Ya(15,15)-30 14.13 983.02 3414.71 7 14.29 742.07 2291.78 7 Si

Ya(20,20)-30 404.84 1021.73 2046.8 7 436.29 1143.26 3442.33 8 Si

Ya(20,20)-40 1580.04 2097.86 2615.68 2 1372.23 1372.23 1372.23 1 No

Ya(20,20)-50 1714.59 1714.59 1714.59 1 2463.18 2463.18 2463.18 1 No

Ya(10,20)-30 10.2 269.82 1853.79 10 11.48 173.08 905.27 10 Si

Ya(10,20)-40 64.99 977.31 3468.06 9 57.3 1052.72 3494.53 10 Si

Ya(10,20)-50 293.89 1467.07 3314.26 5 263.39 1236.63 2702.55 5 Si

Ya(10,20)-60 665.49 665.49 665.49 1 1089.71 1089.71 1089.71 1 No

Ya(15,30)-30 14.87 97.48 240.37 10 20.98 116.17 417.88 10 No

Ya(15,30)-40 52.07 1079.29 3487.28 9 39.59 863.53 2138.77 9 Si

Ya(20,40)-40 203.53 552.45 1451.12 8 222.83 488.94 1219.76 8 Si

Ya(20,40)-50 324.55 1469.63 2715.87 5 253.33 1392.81 2157.26 5 Si

Para el caso de las instancias He1 (tabla 16), el pairing no genera un impacto significativo

en relación a los tiempos de ejecución del algoritmo e incluso se resuelve un número menor de

instancias dentro del tiempo límite (He0-40 y He1-40).

70

TABLA 16. ANÁLISIS DE TIEMPO INSTANCIAS HE DE MAYOR TAMAÑO PARA B&C

B&C B&C p

Ayuda


He0-30 4.98 114.67 578.11 10 3.88 106.83 497.71 10 Si

He0-40 189.28 1759.71 3069.07 7 163.88 1664 3000.84 6 No

He1-30 3.39 306.03 1487.95 10 3.7 339.59 1630.26 10 No

He1-40 46.3 1218.34 2154.09 5 38.27 1304.33 3006.41 4 No

He1-50 376.06 376.06 376.06 1 331.3 331.3 331.3 1 Si

TABLA 17. ANÁLISIS DE TIEMPO INSTANCIAS MO DE MAYOR TAMAÑO PARA B&C

B&C B&C p

Ayuda


Mo(0.15)-50 0.08 0.82 3.79 10 0.06 0.76 3.81 10 No

Mo(0.50)-40 6.66 139.63 776.26 10 6.02 146.02 860.22 10 No

Mo(0.50)-50 123.52 586.17 1465.58 7 142.52 583.15 1431.99 7 Si

Mo(0.85)-30 1.16 40.3 104.47 10 1.09 45.36 144.74 10 No

Mo(0.85)-40 29.03 324.37 1131.38 7 35.6 339.09 1194.27 7 No

Para las instancias del tipo Mo (tabla 17) en realidad no se produce ningún efecto con la

incorporación de pairing, luego es importante mencionar que para el subconjunto Mo(0.15) con

incluso 50 nodos se resuelven todas las instancias con un tiempo máximo de 3.79 segundos; para

las Mo(0.5) se resuelven solo 7 y finalmente para las Mo(0.85) no se logra resolver ni siquiera una

instancia, lo que demuestra el impacto de la fuente de robustez (longitud del intervalo) en la

complejidad del problema; a continuación se presenta una tabla con instancias de este tipo para 40

y 50 nodos.

En relación a la desviación porcentual respecto al óptimo, sorprendentemente para

instancias del tipo Ya (tabla 18), incluso para 100 nodos, se obtienen desviaciones porcentuales

respecto a la cota inferior (gap*) bajo el 16% con promedios en torno al 10%. Es posible observar

en este tipo de instancias que no existe un aumento en las desviaciones porcentuales (min, av. y

max) al aumentar el tamaño del problema, cualidad muy particular del algoritmo en estas

instancias. Respecto a la diferencia entre el B&C puro y con pairing se puede observar que no

existe mayor diferencia, salvo lo mencionado anteriormente en relación a aquellas instancias donde

se aumenta el número de instancias resueltas dentro del tiempo límite.

Con respecto a las instancias He (tabla 19) se puede observar que sí existe un aumento

significativo en la desviación porcentual a medida que se aumenta el tamaño del problema, sin

embargo para instancias de tamaño 100 se observa un promedio en torno al 30%, si bien es un

porcentaje alto, está lejos de los dramáticos porcentajes (superior al 100%) obtenidos por el MILP

71

para incluso 30 nodos. Se puede mencionar además que el pairing no ayuda en este conjunto de

instancias tanto en relación a las desviaciones porcentuales como al número de instancias

resueltas dentro del tiempo límite.

En relación a las instancias Mo, se observa que sus desviaciones porcentuales son

inferiores a un 23% y para 100 nodos llegan a un promedio de un 20%, adicionalmente se observa

que el incremento con el aumento de tamaño es menor al de las instancias He, no obstante es

mayor que el de las instancias Ya. Por otra parte se observa que no existe un impacto producto de

la incorporación de cortes pareados (pairing).

Considerando lo mostrado anteriormente se puede concluir que el B&C propuesto es un

algoritmo que no deja de ser competitivo incluso para las instancias más difíciles y de mayor

tamaño propuestas en la literatura.

TABLA 18. GAP DE INSTANCIAS YA DE MAYOR TAMAÑO PARA B&C

B&C B&Cp

N GAP* GAP GAPmin GapMax N GAP* GAP GAPmin GapMax

Ya(10,10)-30 6.00 2% 0% 0% 7% 6.00 2% 0% 0% 7%

Ya(10,10)-40 2.00 7% 0% 0% 12% 2.00 7% 0% 0% 13%

Ya(10,10)-50 0.00 9% 0% 4% 13% 0.00 9% 0% 4% 13%

Ya(10,10)-60 0.00 11% 0% 9% 14% 0.00 11% 0% 9% 14%

Ya(10,10)-80 0.00 10% 0% 8% 13% 0.00 10% 0% 8% 13%

Ya(10,10)-100 0.00 9% 0% 7% 11% 0.00 10% 0% 7% 11%

Ya(15,15)-30 7.00 1% 0% 0% 6% 7.00 1% 0% 0% 6%

Ya(15,15)-40 4.00 4% 0% 0% 12% 4.00 4% 0% 0% 11%

Ya(15,15)-50 0.00 9% 0% 7% 13% 0.00 9% 0% 6% 13%

Ya(20,20)-30 8.00 2% 0% 0% 12% 9.00 1% 0% 0% 13%

Ya(20,20)-40 2.00 6% 0% 0% 10% 1.00 7% 0% 0% 11%

Ya(20,20)-50 1.00 9% 0% 0% 16% 1.00 9% 0% 0% 16%

Ya(10,20)-40 9.00 0% 0% 0% 1% 10.00 0% 0% 0% 0%

Ya(10,20)-50 5.00 2% 0% 0% 5% 5.00 2% 0% 0% 5%

Ya(10,20)-60 1.00 5% 0% 0% 10% 1.00 5% 0% 0% 10%

Ya(10,20)-80 0.00 6% 0% 4% 8% 0.00 6% 0% 4% 8%

Ya(10,20)-100 0.00 6% 0% 4% 7% 0.00 6% 0% 4% 7%

Ya(15,30)-40 9.00 0% 0% 0% 3% 9.00 0% 0% 0% 4%

Ya(15,30)-50 7.00 1% 0% 0% 5% 7.00 1% 0% 0% 6%

Ya(20,40)-40 8.00 1% 0% 0% 6% 8.00 1% 0% 0% 6%

Ya(20,40)-50 5.00 2% 0% 0% 5% 5.00 2% 0% 0% 5%

72

TABLA 19. ANÁLISIS DE DESVIACIONES PORCENTUALES PARA B&C EN INSTANCIAS MAYORES TIPO HE

B&C B&Cp


He0-40 7.00 3% 0% 0% 16% 7.00 3% 0% 0% 16%

He0-50 0.00 11% 0% 4% 17% 0.00 11% 1% 3% 18%

He0-60 0.00 16% 0% 4% 23% 0.00 17% 1% 3% 23%

He0-80 0.00 22% 0% 19% 29% 0.00 25% 3% 22% 29%

He0-100 0.00 29% 0% 24% 32% 0.00 29% 0% 26% 32%

He1-40 5.00 4% 0% 0% 9% 4.00 4% 0% 0% 12%

He1-50 1.00 10% 0% 0% 23% 1.00 11% 0% 0% 23%

TABLA 20. ANÁLISIS INSTANCIAS MO PARA B&C EN TAMAÑOS MAYORES

B&C B&Cp


Mo(0.50)-50 7.00 1% 0% 0% 8% 7.00 2% 0% 0% 9%

Mo(0.85)-40 7.00 2% 0% 0% 11% 7.00 2% 0% 0% 13%

Mo(0.85)-50 0.00 7% 0% 2% 12% 1.00 7% 0% 0% 13%

Mo(0.85)-60 0.00 12% 0% 7% 17% 0.00 13% 1% 9% 19%

Mo(0.85)-80 0.00 18% 0% 12% 21% 0.00 18% 1% 13% 21%

Mo(0.85)-100 0.00 20% 0% 17% 23% 0.00 20% 1% 17% 23%

5.3.4 ANÁLISIS DE INSTANCIAS LA

Para este conjunto de instancias sólo se estudian el MILP y el algoritmo de B&C sin pairing. En las

tablas 21 y 22 se presentan un análisis de tiempos y de las desviaciones porcentuales

respectivamente.

De la tabla 21 se puede observar que el MILP es capaz de resolver, en el óptimo,

instancias de mayor tamaño, ya que resuelve todas las instancias de hasta 20 nodos e incluso una

de tamaño 30. El B&C en tanto sólo es capaz de resolver en una ocasión instancias de tamaño 20.

En relación a las desviaciones porcentuales, en la tabla 22 se puede observar que el B&C

para 20 nodos obtiene una desviación porcentual del 8.5%, la que está dada en la totalidad por la

calidad del LB. A medida que aumenta el tamaño del problema las desviaciones porcentuales del

B&C aumentan significativamente, llegando a un promedio del 30% para 50 nodos, lo que

transforma a las instancias LA en el conjunto más complejo, desde el punto de vista exacto.

En relación al MILP este funciona de forma eficiente hasta 30 nodos con gaps menores al

10% y entregando los mejores LB. El paso a 40 nodos es crítico para el MILP, pues no es capaz de

encontrar soluciones factibles en este conjunto, en tanto se transforma en un algoritmo inviable sin

realizarle una intervención en la obtención de soluciones factibles.

73

Es importante mencionar que el B&C logra mejorar el UB obtenido por (Kasperski et al.,

2012) de dos instancias (1221-X2C-N1-15-N2-14-K-2-R-1 y 1223-X2C-N1-15-N2-14-K-2-R-3), lo

que deja en evidencia lo comentado en el trabajo antes citado, acerca de la complejidad de sus

algoritmos para resolver este tipo de instancias.

TABLA 21. ANÁLISIS DE TIEMPOS INSTANCIAS LA

MILP B&C


La-5 0.14 0.32 0.98 10 0.20 0.58 1.78 10

La-10 50.26 990.12 2836.36 10 3315.52 3315.52 3315.52 1

La-15 2573.69 2573.69 2573.69 1 - - - 0

TABLA 22. ANÁLISIS DE GAP INSTANCIAS LA

MILP B&C

N GAP* GAP N GAP* GAP

La-10 10.00 0% 0% 1 8.55% 8.55%

La-15 1 10.41% 0% 0 15.03% 6.99%

La-20 (*10) - - 0 23.69% 0%

La-25 (*10) - - 0 27.69% 0%

5.4 EXPERIMENTACIÓN DE ALGORITMOS APROXIMADOS.

Esta sección se divide en dos análisis, el primero está relacionado con las heurísticas básicas, y el

segundo está dirigido a la experimentación y análisis de las metaheurísticas propuestas.

5.4.1 ANÁLISIS DE HEURÍSTICAS BÁSICAS

El siguiente análisis consiste en la contrastación del desempeño de heurísticas de un escenario

(Hu y Hm) con la heurísticas propuestas en este trabajo, las que fueron explicadas en capítulos

anteriores, la nomenclatura utilizada para las nuevas heurísticas es la siguiente, Hc : heurística

constructiva simple y Hcd: heurística constructiva dinámica.

Se realizan dos análisis, una enfocado en el aporte real de las heurísticas y otro en las

desviaciones porcentuales. Como se mencionó anteriormente el primer análisis está relacionado

con la constatación del aporte de las nuevas heurísticas, esto desde el punto de vista de la

obtención de mejores soluciones respecto a las heurísticas de un escenario; luego de la tabla 23 a

la 25 se presenta el número de veces que cada algoritmo obtuvo la mejor solución, cabe destacar

que puede suceder que dos o más heurísticas obtengan el mismo valor, pero eso no dificulta el

análisis, pues en cada grupo se consideraron 10 instancias, de modo que cada fila debe sumar a lo

menos 10.

74

Para el primer conjunto de instancias Ya (Ya(C,2C)) mostradas en la tabla 23, se pueden

realizar algunos análisis interesantes, en primer lugar Hm se muestra como la peor heurística

obteniendo resultados competitivos sólo para instancias con 30 o menos nodos. Hu se perfila

como la mejor alternativa; sin embargo para todos los conjuntos de instancias las nuevas

heurísticas aportan con a lo menos 1 mejor solución, más aún existen situaciones donde son estas

heurísticas las que proveen de la mayor cantidad de mejores soluciones (*). En relación a la mejora

entregada por el dinamismo a la heurística constructiva simple se puede observar que aporta para

un gran número de conjuntos de instancias (20/30).

TABLA 23. ANÁLISIS DE HEURÍSTICAS INSTANCIAS YA(C,C)

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Ya(10,10)-10 0.00 3.00 1.00 8.00 Ya(15,15)-10 4.00 3.00 2.00 8.00 Ya(20,20)-10 1.00 2.00 0.00 9.00

Ya(10,10)-20* 4.00 4.00 3.00 1.00 Ya(15,15)-20 2.00 3.00 3.00 5.00 Ya(20,20)-20 2.00 5.00 6.00 3.00

Ya(10,10)-30 3.00 5.00 7.00 1.00 Ya(15,15)-30 3.00 2.00 5.00 2.00 Ya(20,20)-30* 5.00 6.00 4.00 1.00

Ya(10,10)-40* 5.00 3.00 4.00 0.00 Ya(15,15)-40 1.00 3.00 8.00 0.00 Ya(20,20)-40* 2.00 5.00 5.00 0.00

Ya(10,10)-50 1.00 5.00 7.00 0.00 Ya(15,15)-50 1.00 4.00 6.00 0.00 Ya(20,20)-50 2.00 5.00 7.00 0.00

Ya(10,10)-60 2.00 4.00 6.00 0.00 Ya(15,15)-60 4.00 4.00 6.00 0.00 Ya(20,20)-60 2.00 1.00 9.00 0.00

Ya(10,10)-70 2.00 4.00 6.00 0.00 Ya(15,15)-70 1.00 4.00 6.00 0.00 Ya(20,20)-70 3.00 4.00 7.00 0.00

Ya(10,10)-80* 2.00 3.00 5.00 0.00 Ya(15,15)-80* 2.00 3.00 5.00 0.00 Ya(20,20)-80 3.00 2.00 6.00 0.00

Ya(10,10)-90 3.00 4.00 6.00 0.00 Ya(15,15)-90 2.00 2.00 7.00 0.00 Ya(20,20)-90 5.00 2.00 6.00 0.00

Ya(10,10)-100 2.00 3.00 7.00 0.00 Ya(15,15)-100* 2.00 5.00 3.00 0.00 Ya(20,20)-100 3.00 1.00 7.00 0.00

Para el segundo conjunto de instancias Ya (Ya(C,2C)) (tabla 24) ocurre algo similar al caso

anterior con la salvedad de que la heurística Hm sólo es competitiva para instancias de 10 nodos.

Las nuevas heurísticas aportan para todos los conjuntos de instancias.

Para las instancias Mo (tabla 25) Hm tiende a perder efectividad a medida que aumenta la

longitud del intervalo, a diferencia de las heurísticas constructivas que tienden a mejorar su

desempeño. Específicamente para un valor del parámetro de distorsión de 0.15 la heurística que

presenta un mejor desempeño es Hm, relegando a aportes menores a las heurísticas constructivas

y sólo para instancias con 40 o menos nodos. Para el subconjunto de instancias con parámetro de

distorsión 0.5, Hm sigue dominando pero en menor medida y tanto la heurística Hu como las

heurísticas constructivas comienzan a generar aportes para instancias de todo tamaño. Finalmente

para el conjunto de instancias con parámetro 0.85 no existe una heurística dominante, pero se

puede apreciar que Hm tiene un desempeño por debajo de las tres restantes, luego las heurísticas

constructivas aportan con a lo menos con 2 instancias en cada conjunto, incluso para el conjunto

Mo(0.85)-70 aporta con 7 y para Mo(0.85)-30, Mo(0.85)-40 y Mo(0.85)-60 aporta con 6 instancias.

En las instancias He (tabla 26) la mejor heurística es Hm para todos los tamaños de

instancias. Las nuevas heurísticas sólo aportan en las instancias He0-20 y He1-20.

75

TABLA 24. ANÁLISIS DE HEURÍSTICAS INSTANCIAS YA(C,2C)

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Ya(10,20)-10 3.00 6.00 5.00 6.00 Ya(15,30)-10 4.00 4.00 6.00 2.00 Ya(20,40)-10 4.00 5.00 5.00 7.00

Ya(10,20)-20 6.00 4.00 8.00 0.00 Ya(15,30)-20 4.00 6.00 7.00 0.00 Ya(20,40)-20 4.00 5.00 8.00 0.00

Ya(10,20)-30 3.00 3.00 9.00 0.00 Ya(15,30)-30 7.00 5.00 9.00 0.00 Ya(20,40)-30 4.00 6.00 7.00 0.00

Ya(10,20)-40 3.00 5.00 6.00 0.00 Ya(15,30)-40 5.00 6.00 6.00 0.00 Ya(20,40)-40 4.00 6.00 7.00 0.00

Ya(10,20)-50 2.00 4.00 7.00 0.00 Ya(15,30)-50 4.00 7.00 8.00 0.00 Ya(20,40)-50 4.00 4.00 9.00 0.00

Ya(10,20)-60 3.00 5.00 7.00 0.00 Ya(15,30)-60 4.00 2.00 6.00 0.00 Ya(20,40)-60 6.00 3.00 8.00 0.00

Ya(10,20)-70 1.00 5.00 7.00 0.00 Ya(15,30)-70 2.00 6.00 10.00 0.00 Ya(20,40)-70 4.00 5.00 9.00 0.00

Ya(10,20)-80 1.00 3.00 7.00 0.00 Ya(15,30)-80 2.00 3.00 7.00 0.00 Ya(20,40)-80 1.00 4.00 7.00 0.00

Ya(10,20)-90 4.00 5.00 7.00 0.00 Ya(15,30)-90 5.00 0.00 6.00 0.00 Ya(20,40)-90 2.00 6.00 8.00 0.00

Ya(10,20)-100 0.00 0.00 10.00 0.00 Ya(15,30)-100 1.00 3.00 8.00 0.00 Ya(20,40)-100 2.00 4.00 6.00 0.00

TABLA 25. ANÁLISIS DE HEURÍSTICAS INSTANCIAS MO

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Hc Hcd Hu Hm

Mo(0.15)-10 3.00 4.00 8.00 10.00 Mo(0.50)-10 6.00 6.00 7.00 4.00 Mo(0.85)-10 7.00 8.00 7.00 8.00

Mo(0.15)-20 4.00 6.00 3.00 9.00 Mo(0.50)-20 2.00 3.00 1.00 8.00 Mo(0.85)-20* 9.00 4.00 3.00 1.00

Mo(0.15)-30 2.00 2.00 4.00 8.00 Mo(0.50)-30 2.00 0.00 3.00 6.00 Mo(0.85)-30* 6.00 3.00 3.00 1.00

Mo(0.15)-40 1.00 2.00 2.00 9.00 Mo(0.50)-40 0.00 1.00 2.00 7.00 Mo(0.85)-40* 2.00 4.00 2.00 3.00

Mo(0.15)-50 0.00 0.00 3.00 10.00 Mo(0.50)-50 0.00 0.00 2.00 8.00 Mo(0.85)-50* 4.00 2.00 4.00 0.00

Mo(0.15)-60 0.00 0.00 0.00 10.00 Mo(0.50)-60 0.00 1.00 1.00 8.00 Mo(0.85)-60 0.00 3.00 3.00 4.00

Mo(0.15)-70 0.00 0.00 0.00 10.00 Mo(0.50)-70 1.00 1.00 2.00 6.00 Mo(0.85)-70* 3.00 4.00 1.00 2.00

Mo(0.15)-80 0.00 0.00 1.00 9.00 Mo(0.50)-80 0.00 0.00 2.00 8.00 Mo(0.85)-80 3.00 1.00 5.00 1.00

Mo(0.15)-90 0.00 0.00 0.00 10.00 Mo(0.50)-90 1.00 0.00 2.00 7.00 Mo(0.85)-90* 3.00 2.00 4.00 1.00

Mo(0.15)-100 0.00 0.00 0.00 10.00 Mo(0.50)-100 0.00 0.00 0.00 10.00 Mo(0.85)-100 1.00 1.00 6.00 2.00

TABLA 26. ANÁLISIS DE HEURÍSTICAS INSTANCIAS HE

Hc Hcd Hu Hm

Hc Hcd Hu Hm

He0-10 2.00 6.00 3.00 8.00 He1-10 2.00 6.00 3.00 8.00

He0-20 1.00 1.00 0.00 8.00 He1-20 0.00 1.00 0.00 9.00

He0-30 0.00 0.00 0.00 10.00 He1-30 0.00 0.00 0.00 10.00

He0-40 0.00 0.00 0.00 10.00 He1-40 0.00 0.00 0.00 10.00

He0-50 0.00 0.00 0.00 10.00 He1-50 0.00 0.00 0.00 10.00

He0-60 0.00 0.00 0.00 10.00 He1-60 0.00 0.00 0.00 10.00

He0-70 0.00 0.00 0.00 10.00 He1-70 0.00 0.00 0.00 10.00

He0-80 0.00 0.00 0.00 10.00 He1-80 0.00 0.00 0.00 10.00

He0-90 0.00 0.00 0.00 10.00 He1-90 0.00 0.00 0.00 10.00

He0-100 0.00 0.00 0.00 10.00 He1-100 0.00 0.00 0.00 10.00

En relación al segundo análisis de las nuevas heurísticas, correspondiente a los gaps

obtenidos de la tabla 27 a la 29, se presentan algunas estadísticas de interés con respecto a esta

desviación porcentual, es importante comentar que ésta es solo una muestra de los resultados,

76

para mayor detalle ver anexo 1. Es relevante mencionar que este gap se calcula en relación a la

mejor solución conocida, ya sea entregada por el B&C o por las soluciones obtenidas por

(Kasperski et al., 2012) con su conjunto de algoritmos.

En las tablas 27 y 28, se observa el desempeño de las heurísticas para las instancias Ya,

subconjunto Ya(C,C) y Ya(C,2C) respectivamente. De las tablas se puede apreciar que Hc en

ambos subconjuntos obtiene gaps que no superan el 4%. Para Hcd ocurre algo similar, salvo en

Ya(10,10)-20 donde se obtiene un gap máximo de 14%. Adicionalmente se puede observar que su

desviación relativa tanto de Hc como de Hcd tiende a mejorar a medida que crece el tamaño del

problema, pues para 80 y 100 nodos se alcanzan gaps menores al 0.75% para Ya(C,C) y 0.45%

para Ya(C,2C) en el caso de Hc, y 0.72% para Ya(C,C) y 0.43% para Ya(C,2C), esto demuestra

que para este conjunto de instancias estas heurísticas son competitivas con metaheurísticas

sofisticadas como las implementadas por (Kasperski et al., 2012). Cabe destacar que Hc, Hcd y Hu

tienen un mejor desempeño en el subconjunto Ya(C,2C). Al comparar los gaps de Hc y Hcd, se

observa que en general tienen un desempeño similar, además si se considera el análisis anterior

(aporte de mejores soluciones), donde se observó que ambas aportan en forma independiente, es

posible concluir que para este conjunto de instancias ambas son alternativas válidas. En relación

a las heurísticas de un escenario (Hu y Hm), se puede decir que Hu es significativamente mejor

que Hm, y que Hu tiene un desempeño comparable con el de las nuevas heurísticas.

TABLA 27. MUESTRA DE ESTADÍSTICAS DE HEURÍSTICAS PARA YA(C,C)

Hc Hcd Hu Hm

Min Av. Max desv Min Av. Max desv Min Av. Max Desv Min Av. Max Desv

Ya(10,10)-20 0.00 2.02 4.00 1.35 0.26 3.22 14.44 4.27 0.24 2.79 5.67 1.51 0.00 4.43 9.06 2.48

Ya(10,10)-40 0.00 0.86 2.12 0.80 0.13 0.98 2.31 0.77 0.00 0.93 1.98 0.77 2.65 5.68 8.44 1.81

Ya(10,10)-60 0.02 0.73 1.81 0.58 0.00 0.65 1.35 0.49 0.00 0.57 1.29 0.50 4.17 5.53 8.45 1.40

Ya(10,10)-80 0.09 0.39 0.71 0.20 0.03 0.44 0.72 0.23 0.00 0.30 0.78 0.27 3.05 5.74 9.26 1.77

Ya(10,10)-100 0.00 0.23 0.75 0.21 0.14 0.24 0.51 0.13 0.00 0.10 0.26 0.09 3.33 6.01 7.48 1.32

TABLA 28. MUESTRA DE ESTADÍSTICAS DE HEURÍSTICAS PARA YA(C,2C)

Hc Hcd Hu Hm

Min Av. Max desv Min Av. Max Desv Min Av. Max desv Min Av. Max Desv

Ya(20,40)-20 0.00 0.70 3.19 1.04 0.00 0.70 3.01 0.96 0.00 0.25 1.70 0.54 1.50 6.91 11.84 3.78

Ya(20,40)-40 0.00 0.21 0.71 0.29 0.00 0.18 0.89 0.29 0.00 0.11 0.55 0.19 4.56 6.53 8.97 1.71

Ya(20,40)-60 0.00 0.09 0.35 0.11 0.01 0.18 0.55 0.17 0.00 0.08 0.32 0.11 2.35 4.90 7.01 1.49

Ya(20,40)-80 0.02 0.18 0.45 0.13 0.00 0.16 0.43 0.16 0.00 0.06 0.16 0.06 3.86 6.54 9.66 1.82

Ya(20,40)-100 0.00 0.10 0.23 0.09 0.00 0.08 0.24 0.09 0.00 0.04 0.20 0.06 4.52 6.26 9.04 1.59

77

En la tabla 29 se observa una muestra de los indicadores estadísticos de las instancias

He1, en este conjunto es donde todas las heurísticas básicas presentan el peor desempeño. La

que muestra mejores resultados es Hm obteniendo en promedio gaps en torno al 3%. Hc, Hcd y Hu

obtienen gaps en promedio superiores a un 17%. La heurística Hcd es levemente mejor a Hc y Hu

tanto en los promedios, mínimos y máximos.

De la tabla 30 se puede apreciar que tanto Hc como Hcd obtienen menores gaps con

intervalos de incertidumbre más grandes, con Hu sucede lo mismo pero en menor grado. Hm tiene

un comportamiento inverso obteniendo mejores resultados para intervalos de incertidumbre

pequeños. En forma particular para las instancias Mo(0.15) es Hm la que presenta los mejores

resultados; en tanto, para las instancias Mo(0.85) Hc es la que presenta un mejor desempeño, ya

que si bien Hu la supera para 80 y 100 nodos, en las instancias de menor tamaño Hu presenta

gaps superiores al 10%.

Para el conjunto de instancias He, se puede concluir que las heurísticas constructivas

dejan de ser competitivas, debido a que no aportan en forma significativa con mejores soluciones

(análisis anterior) ni tiene gaps de calidad. En relación a las instancias Mo se puede concluir que

para el parámetro de distorsión sobre 0.5, las heurísticas constructivas comienzan a aportar de

forma significativa, incluso para un factor de 0.85 entregan mejor o igual desempeño que las

heurísticas de un escenario.

TABLA 29. MUESTRA DE ESTADÍSTICAS DE HEURÍSTICAS PARA HE

Hc Hcd Hu Hm

Min Av. Max Desv Min Av. Max desv Min Av. Max Desv Min Av. Max Desv

He1-20 8.7 23.9 46.3 10.00 2.8 19.9 36.27 12.34 7.3 32.1 54.64 16.43 0.00 3.9 10.39 3.82

He1-40 13.52 22.49 34.84 6.73 4.87 18.03 28.74 7.54 13.97 24.56 36.51 6.63 1.08 2.8 4.89 1.46

He1-60 12.13 25.01 33.40 6.82 10.74 23.20 39.31 9.80 6.88 28.81 46.34 13.16 0.96 2.9 5.49 1.45

He1-80 11.39 22.25 34.04 7.10 9.75 18.87 26.99 4.98 13.19 25.27 37.83 6.88 0.79 2.9 6.10 1.50

He1-100 14.45 19.53 25.66 3.62 9.59 17.14 27.12 4.97 14.50 21.14 25.94 3.86 1.40 3.4 4.77 1.08

Finalmente se puede concluir que las nuevas heurísticas son una alternativa válida para la

obtención de soluciones de calidad en algunos conjuntos de instancias, como las Ya y Mo (con

parámetro de distorsión superior a 0.5). Adicionalmente estas heurísticas tienen la propiedad de

utilizar la información intervalar, propiedad que no se ha utilizado (en forma no trivial) en las

heurísticas propuestas a la fecha. Por otra parte, como se demostró anteriormente, estas nuevas

heurísticas son capaces de entregar mejores soluciones que Hu y Hm, luego se pueden utilizar de

forma complementaria, pues los tiempos de ejecución son muy pequeños.

78

TABLA 30. MUESTRA DE ESTADÍSTICAS PARA HEURÍSTICAS DE MO

Hc Hcd Hu Hm

Min Av. Max des Min Av. Max Desv Min Av. Max desv Min Av. Max Des

Mo(0.15)-20 0.00 37.82 274.51 84.40 0.00 22.52 152.15 47.95 0.00 23.67 113.35 34.14 0.00 2.13 19.91 6.26

Mo(0.15)-40 0.00 32.91 79.93 25.83 0.00 52.44 130.76 45.42 0.00 16.98 40.36 14.52 0.00 0.56 3.90 1.29

Mo(0.15)-60 10.02 32.16 73.97 22.89 5.60 56.00 132.00 39.15 2.01 13.26 27.20 9.97 0.00 0.25 2.25 0.71

Mo(0.15)-80 5.82 39.88 62.41 19.42 13.77 51.67 114.68 31.43 0.00 10.43 22.07 6.96 0.00 1.65 5.82 1.99

Mo(0.15)-100 7.87 36.08 55.26 15.24 28.87 63.66 102.38 24.32 1.88 14.86 24.23 7.98 0.00 0.57 4.43 1.42

Mo(0.85)-20 0.00 1.19 3.18 1.27 0.00 4.13 14.44 4.41 0.00 4.34 11.28 3.51 0.61 5.89 12.02 4.10

Mo(0.85)-40 0.00 3.33 6.72 2.35 0.00 3.12 6.59 2.22 0.31 4.53 10.41 2.90 1.19 3.26 6.98 1.62

Mo(0.85)-60 1.20 2.74 5.43 1.23 0.35 2.52 4.54 1.69 50 2.94 7.52 2.07 1.22 4.05 8.77 2.44

Mo(0.85)-80 1.26 2.45 5.26 1.28 0.95 2.31 4.76 1.16 0.34 1.93 5.04 1.30 1.41 3.58 7.10 1.60

Mo(0.85)-100 1.40 2.60 4.22 1.20 1.13 2.83 5.12 1.33 0.68 2.10 5.71 1.47 1.63 3.52 5.73 1.36

5.4.2 ANÁLISIS DE METAHEURÍSTICAS

Como se pudo evidenciar desde el análisis de los algoritmos exactos, para la mayor parte de los

conjuntos de instancias estudiados, no es viable obtener la solución óptima en un tiempo razonable

a partir de instancias con 50 nodos. Por otra parte, el análisis realizado a las heurísticas básicas,

muestra que si bien para algunos conjuntos de instancias se obtienen gaps de calidad, en otros

conjuntos no tiene la certeza de obtener una buena solución a través del uso de éstas. Dado los

requerimientos computacionales de los algoritmos exactos y la inestabilidad de las heurísticas

básicas, nace la necesidad de utilizar metaheurísticas, las que pueden entregar soluciones de

mejor calidad que las heurísticas básicas y en un tiempo significativamente menor que los

algoritmos exactos.

Para el análisis de las metaheurísticas se seleccionan 25 instancias de 80 nodos, 25

instancias de 60 y 20 de 100, dentro de las familias de instancias Ya(10,10), Ya(10,20), He1, La y

Mon(0.85), considerando 5 de cada familia.

Dos factores importantes de las metaheurísticas estudiadas son: la solución inicial y el

vecindario. Con respecto a la solución inicial, SA y mejora iterativa (MI) utilizan la mejor solución

entre las cuatro heurísticas básicas analizadas en la sección anterior; GRASP utiliza sólo la

heurística constructiva dinámica (Hcd), luego GRASP parte de una peor o igual solución que SA y

MI. En relación a la vecindad las tres heurísticas utilizan aquella explicada en capítulo IV.

Después de un proceso de experimentación se determinaron los siguientes conjuntos de

parámetros: SA para 100 nodos utilizó una temperatura inicial de 100, temperatura final de 0.1, un

factor de decaimiento de 0.95 y 500 ciclos internos. SA para 80 y 60 nodos, utilizó una temperatura

inicial de 50, temperatura final de 0.01, un factor de decaimiento de 0.94 y 500 ciclos internos.

79

Mejora iterativa utilizó 8.000 ciclos. GRASP utilizó distintas combinaciones de parámetros para los

diferentes conjuntos de instancias, estos se pueden encontrar en Anexo 2. Es importante

mencionar que cada metaheurística fue corrida en 10 ocasiones para cada instancia, con el fin de

obtener indicadores estadísticos fiables.

En la tabla 31 se presentan los resultados para 100 nodos; se puede observar que la

metaheurística que presenta el mejor desempeño, en relación a las desviaciones porcentuales es

SA (desviaciones porcentuales menores al 0.22%), sin embargo este algoritmo también presenta

los mayores tiempos de ejecución. Por otra parte, mejora iterativa entrega soluciones con una

desviación porcentual menor al 2% y en un tiempo menor a 30 segundos, lo que la convierte en

una metaheurística rápida y con soluciones de calidad. Con un desempeño intermedio se

encuentra GRASP el cual provee gaps menores al 1% y los tiempos son un poco más que la mitad

del tiempo de SA (sólo en la instancia He0-3 logra mejorar el desempeño de SA). En cuanto al

desempeño individual, SA sólo en una ocasión no logra obtener la mejor solución conocida, en

tanto GRASP y mejora iterativa no lo logran en 3 y 8 instancias respectivamente. Las heurísticas

básicas proveen peores gap iniciales en las instancias He0 y Mo(0.85), esto provoca que mejora

iterativa obtenga un peor desempeño y esta situación no se visualiza en SA. Finalmente se puede

concluir que para 100 nodos no se logra mejorar los resultados de (Kasperski et al., 2012), sin

embargo las tres metaheurísticas obtienen desviaciones relativas menores al 2%.

En la tabla 32 se puede apreciar que nuevamente SA es el algoritmo que presenta el mejor

desempeño, siendo el único capaz de bajar los gaps de las instancias La. SA alcanza la mejor

solución conocida, en todas las corridas, para 18 de las 25 instancias evaluadas y obviando las

instancias La, sus mayores desviaciones porcentuales son en torno al 2%. Un caso particular

ocurre en las instancias He-0, donde la metaheurística que muestra los mejores resultados es

GRASP, llegando a la mejor solución conocida en cada una de las corridas, para las 5 instancias

del grupo. Para 60 nodos como se muestra en la tabla 33, ocurre lo mismo que lo descrito para las

tablas 31 y 32.

A continuación se dará una breve descripción de las principales características de SA y

GRASP. Una particularidad importante del SA implementado es que alcanza un buen desempeño

sin tener gran cantidad de rechazos, pues de la experimentación se observó que al tener una

temperatura inicial de 100, no se tienen más de 10 rechazos y al ser ésta de 50 no se tienen más

de 3, lo relevante es que esto basta para mejorar el desempeño de la mejora iterativa y de GRASP.

Debido a que GRASP es la única metaheurística que tiene una solución inicial de menor o

igual calidad (privilegiando la diversidad), es importante analizar su comportamiento diferenciando

su fase constructiva de la mejora iterativa. Para eso se presentan los gráficos 4 y 5, donde se

grafica el gap promedio entregado desde la fase constructiva y el gap final. Cabe destacar que se

80

analizan las mismas 25 instancias que se muestran en las tablas 32 y 33; de la 1 a la 5 se

presentan las instancias Ya(C,C), de la instancia 6 a la 10 se presenta Ya(C,2C), de la 11 a la 15

corresponde al conjunto He0, de la instancia 16 a la 20 se muestran los resultados de las

instancias Mo(0.85) y finalmente de la 21 a la 25 se presentan las instancias La. Es importante

observar que si bien ambas gráficas tienen forma similar, para 80 nodos se tiene peor calidad de

soluciones iniciales, esto se debe principalmente a la elección de parámetros, pues para 80 nodos

se dió mayor énfasis al proceso de búsqueda local y se generaron soluciones iniciales con mayor

aleatoriedad. Este ejercicio permitió corroborar que la fase constructiva juega un rol fundamental,

para la mayor parte de las instancias, en el algoritmo diseñado.

TABLA 31. MÍNIMA (MIN), PROMEDIO (AV.) Y MÁXIMA DESVIACIÓN PORCENTUAL DESDE SOLUCIÓN DE REFERENCIA PARA INSTANCIAS CON 100 NODOS.

H. B.

Mejora Iterativa SA GRASP

Instancia min av. Max t Min av. max T Min av. max T

Ya(10-10)-0 0.1 0.00 0.07 0.14 20.86 0.00 0.00 0.00 424.49 0.00 0.01 0.09 247.59

Ya(10-10)-1 0.1 0.00 0.05 0.06 22.81 0.00 0.01 0.06 420.39 0.00 0.01 0.05 258.91

Ya(10-10)-4 0.2 0.00 0.09 0.17 24.94 0.00 0.00 0.00 344.10 0.00 0.09 0.18 251.17

Ya(10-10)-5 0.1 0.00 0.05 0.13 20.37 0.00 0.00 0.05 332.21 0.03 0.08 0.14 247.14

Ya(10-10)-6 0.1 0.00 0.11 0.14 19.48 0.00 0.02 0.14 299.21 0.00 0.04 0.14 223.84

Ya(10-20)-0 0.1 0.00 0.04 0.07 36.99 0.00 0.02 0.07 669.04 0.00 0.06 0.14 289.90

Ya(10-20)-3 0.0 0.00 0.00 0.00 26.88 0.00 0.00 0.00 494.42 0.00 0.03 0.10 259.33

Ya(10-20)-4 0.0 0.00 0.00 0.00 30.87 0.00 0.00 0.00 488.54 0.00 0.03 0.08 285.69

Ya(10-20)-5 0.1 0.00 0.06 0.08 30.26 0.00 0.00 0.01 453.91 0.00 0.02 0.08 274.56

Ya(10-20)-6 0.0 0.00 0.00 0.00 28.73 0.00 0.00 0.00 415.97 0.00 0.01 0.02 256.34

He0-0 2.7 0.00 0.26 0.87 10.64 0.00 0.00 0.00 180.34 0.00 0.05 0.14 108.48

He0-1 1.7 0.07 0.36 0.49 11.87 0.00 0.11 0.22 167.28 0.00 0.26 0.45 120.60

He0-3 5.2 0.27 0.53 1.44 11.53 0.04 0.21 0.22 162.28 0.00 0.10 0.22 117.07

He0-5 1.7 0.19 0.32 0.45 11.52 0.00 0.01 0.06 243.01 0.00 0.02 0.06 117.32

He0-7 2.9 0.02 0.35 1.45 12.65 0.00 0.00 0.01 247.18 0.00 0.07 0.18 127.87

Mo(0.85)-2 1.1 0.02 0.06 0.30 12.08 0.00 0.00 0.02 214.31 0.00 0.00 0.02 166.14

Mo(0.85)-3 1.6 0.00 0.37 0.80 15.34 0.00 0.00 0.05 217.62 0.03 0.24 0.65 177.83

Mo(0.85)-6 2.1 0.00 0.64 1.50 14.58 0.00 0.00 0.00 256.89 0.00 0.47 0.84 165.83

Mo(0.85)-8 1.9 0.00 0.20 0.67 14.47 0.00 0.00 0.00 277.66 0.00 0.02 0.11 151.17

Mo(0.85)-9 0.7 0.14 0.33 0.48 16.11 0.00 0.04 0.14 243.86 0.14 0.49 0.81 153.49

Particularmente se puede observar de la gráfica 5, que para 3 de los 5 conjuntos de

instancias (Ya(C,C), Ya(C,2C) y La), la solución generada desde la fase constructiva es muy

similar a la final, lo cual indica que el mayor aporte en la metaheurística en estos conjuntos es

realizado por esta fase. Lo comentado anteriormente da pié para pensar en la generación de una

heurística que provea de cientos de soluciones iniciales generadas bajo el criterio utilizado en la

81

fase constructiva de GRASP. También es importante mencionar que en los dos conjuntos de

instancias restantes (Mo(0.85) y He0) el mayor aporte es realizado por la fase de búsqueda local.

Las instancias La presentan un gran problema, tanto para algoritmos exactos como

heurísticos, una de las alternativas desde el punto de vista heurístico es el uso de su topología, ya

sea para la generación de heurísticas ad-hoc como para el uso de la topología en la generación de

un vecindario.


H.B. Mejora iterativa SA GRASP

Min Av. Max t Min Av. Max T Min Av. Max T

Ya(10-10)-0 0.19 0.00 0.00 0.01 11.32 0.00 0.00 0.00 222.24 0.79 1.25 1.58 202.95

Ya(10-10)-1 0.12 0.00 0.10 0.37 13.64 0.00 0.00 0.00 264.42 0.51 2.03 2.72 226.00

Ya(10-10)-2 0.50 0.00 0.32 0.66 12.72 0.00 0.00 0.00 257.06 0.85 1.21 2.02 180.72

Ya(10-10)-3 0.60 0.00 0.17 0.27 11.28 0.00 0.00 0.00 197.45 0.78 1.83 2.58 179.98

Ya(10-10)-4 0.03 0.00 0.01 0.03 11.82 0.00 0.00 0.00 201.36 0.88 1.75 3.52 186.69

Ya(10-20)-0 0.05 0.02 0.04 0.05 17.71 0.00 0.00 0.02 329.83 2.18 3.65 5.22 229.42

Ya(10-20)-1 0.00 0.00 0.00 0.00 17.54 0.00 0.00 0.00 369.22 2.08 3.64 5.10 228.06

Ya(10-20)-2 0.10 0.00 0.06 0.10 15.91 0.00 0.00 0.00 280.77 2.06 3.41 4.19 187.76

Ya(10-20)-3 0.03 0.00 0.02 0.03 15.14 0.00 0.00 0.00 258.65 1.76 3.45 5.25 182.15

Ya(10-20)-4 0.00 0.00 0.00 0.00 16.22 0.00 0.00 0.00 254.53 1.80 3.27 5.17 192.86

He0-0 4.55 0.00 1.69 2.56 6.42 0.00 0.44 2.20 131.61 0.00 0.00 0.00 69.96

He0-1 1.78 0.00 0.08 0.34 7.38 0.00 0.00 0.00 155.41 0.00 0.00 0.00 86.70

He0-2 0.80 0.00 0.09 0.27 8.69 0.00 0.00 0.00 180.66 0.00 0.00 0.00 95.98

He0-3 1.27 0.00 0.19 0.47 8.78 0.00 0.00 0.00 171.79 0.00 0.00 0.00 91.76

He0-4 1.09 0.03 0.21 0.57 9.35 0.00 0.00 0.00 181.51 0.00 0.00 0.00 85.79

Mo(0.85)-0 0.94 0.00 0.04 0.20 7.33 0.00 0.00 0.00 146.25 0.17 0.61 1.05 63.47

Mo(0.85)-1 0.34 0.00 0.05 0.15 8.02 0.00 0.00 0.00 163.32 0.23 0.75 1.40 72.04

Mo(0.85)-2 1.69 0.00 0.25 0.54 9.62 0.00 0.00 0.00 188.45 0.00 0.61 1.57 84.20

Mo(0.85)-3 1.24 0.00 0.00 0.00 8.17 0.00 0.00 0.00 159.19 0.00 0.48 1.02 68.46

Mo(0.85)-4 1.63 0.00 0.26 0.54 8.58 0.00 0.00 0.00 171.87 0.00 1.10 2.16 79.68

La-0 16.67 16.67 16.67 16.67 16.56 8.45 15.27 16.67 364.10 16.67 16.67 16.67 136.55

La-1 19.23 19.23 19.23 19.23 17.15 8.70 16.46 19.23 382.49 19.23 19.23 19.23 183.45

La-2 17.95 17.95 17.95 17.95 17.67 7.25 15.13 17.95 284.71 17.95 17.95 17.95 177.98

La-3 16.67 16.67 16.67 16.67 17.76 4.41 12.97 16.67 282.91 16.67 16.67 16.67 178.84

La-4 19.23 19.23 19.23 19.23 16.91 10.00 16.72 19.23 260.56 19.23 19.23 19.23 181.04

Como conclusión final del estudio metaheurístico, se puede decir se presentan tres

algoritmos competitivos, que presentan desviaciones porcentuales muy pequeñas en relación a las

mejores soluciones conocidas. Cada uno de estos algoritmos posee diferentes cualidades que

pueden ser explotadas en mayor medida. Especificamente en relación al GRASP, se puede decir

82

que cuenta con una fase constructiva que para algunos conjuntos de instancias generan soluciones

muy buenas.


HB Mejora iterativa SA GRASP

Min Av. Max t Min Av. Max T Min Av. Max t

Ya(10-10)-0 0.20 0.00 0.01 0.01 6.77 0.00 0.00 0.00 153.92 0.00 0.00 0.00 104.17

Ya(10-10)-1 0.00 0.00 0.00 0.00 7.19 0.00 0.00 0.00 123.71 0.00 0.00 0.00 114.48

Ya(10-10)-2 0.77 0.00 0.02 0.09 6.72 0.00 0.00 0.00 102.01 0.00 0.00 0.00 113.31

Ya(10-10)-3 0.00 0.00 0.00 0.00 6.75 0.00 0.00 0.00 495.22 0.00 0.00 0.00 151.67

Ya(10-10)-4 0.24 0.00 0.02 0.03 6.35 0.00 0.00 0.00 135.79 0.00 0.00 0.03 114.21

Ya(10-20)-0 0.07 0.00 0.03 0.07 11.23 0.00 0.00 0.00 219.72 0.00 0.00 0.03 170.90

Ya(10-20)-1 0.00 0.00 0.00 0.00 10.38 0.00 0.00 0.00 148.87 0.00 0.00 0.00 174.37

Ya(10-20)-2 0.08 0.00 0.05 0.08 9.29 0.00 0.00 0.00 576.10 0.00 0.01 0.07 200.14

Ya(10-20)-3 0.16 0.00 0.08 0.16 9.06 0.00 0.00 0.00 177.87 0.00 0.00 0.00 147.00

Ya(10-20)-4 0.00 0.00 0.00 0.00 8.84 0.00 0.00 0.00 184.83 0.00 0.00 0.00 153.20

He0-0 5.15 0.00 0.05 0.13 3.55 0.00 0.00 0.00 98.99 0.00 0.00 0.00 36.91

He0-1 1.58 0.00 0.01 0.07 5.14 0.00 0.00 0.00 102.95 0.00 0.00 0.00 47.15

He0-2 2.86 0.00 0.09 0.47 5.76 0.00 0.00 0.00 89.37 0.00 0.00 0.05 57.93

He0-3 1.52 0.00 0.09 0.26 5.53 0.00 0.00 0.00 77.90 0.00 0.00 0.00 54.02

He0-4 2.30 0.00 0.05 0.17 4.99 0.00 0.00 0.00 70.51 0.00 0.00 0.00 52.48

Mo(0.85)-0 2.00 0.12 0.52 1.24 5.55 0.12 0.12 0.12 131.86 0.00 0.09 0.12 68.39

Mo(0.85)-1 1.21 0.00 0.04 0.37 6.59 0.00 0.00 0.00 113.65 0.00 0.00 0.00 86.60

Mo(0.85)-2 0.86 0.00 0.00 0.00 5.39 0.00 0.00 0.00 79.33 0.00 0.00 0.00 72.08

Mo(0.85)-3 1.55 0.00 0.00 0.00 4.95 0.00 0.00 0.00 71.75 0.00 0.00 0.00 62.11

Mo(0.85)-4 2.24 0.00 0.26 0.62 5.16 0.00 0.00 0.00 491.85 0.00 0.00 0.00 99.67

La-0 17.24 17.24 17.24 17.24 9.21 5.88 13.41 17.24 214.66 17.24 17.24 17.24 89.34

La-1 18.97 18.97 18.97 18.97 9.61 9.62 18.03 18.97 144.74 18.97 18.97 18.97 94.88

La-2 15.52 15.52 15.52 15.52 9.28 3.92 10.18 15.52 140.10 15.52 15.52 15.52 92.05

La-3 15.52 15.52 15.52 15.52 8.45 2.00 7.47 15.52 151.35 15.52 15.52 15.52 119.87

La-4 17.24 17.24 17.24 17.24 8.38 4.00 12.01 17.24 546.14 17.24 17.24 17.24 101.38

83

GRÁFICO 5. COMPORTAMIENTO DE GRASP PARA 60 NODOS

GRÁFICO 6. COMPORTAMIENTO DE GRASP PARA 100 NODOS

84

CAPÍTULO VI: CONCLUSIONES Y TRABAJOS FUTUROS

En este capítulo se presentan las principales conclusiones del trabajo realizado, adicionalmente se dan pautas para el desarrollo de trabajos futuros relacionados.

85

En esta tesis se ha trabajado el Problema del Árbol de Expansión Robusto con incertidumbre

intervalar en los costos (MMR-SA) desde un punto de vista algorítmico, tanto exacto como

heurístico. Este es un problema de gran complejidad (NP-Hard) y que en la literatura ha sido

abordado a través de diferentes algoritmos; particularmente desde el punto de vista exacto sólo se

ha trabajado con grafos de hasta 40 nodos. En este trabajo se propuso una variedad de algoritmos,

que según la experimentación antes mostrada son competitivos.

Con respecto a los métodos exactos, se desarrollan tres variantes del algoritmo de

descomposición de Benders y un algoritmo Branch and Cut, este último con una variante que

incluye ingreso más agresivo de cortes, además se implementa una formulación compacta del

problema, la que es resuelta a través de Cplex (versión 12.3). El algoritmo exacto que presenta el

mejor desempeño es B&C, siendo capaz de resolver nuevas instancias. Además, se mejoran las

cotas inferiores para todo el conjunto de instancias estudiadas.

La variante de B&C con ingreso más agresivo de cortes, incluye una metodología de

apareamiento de cortes. Si bien esta metodología no tuvo gran impacto en el MMR-ST, es posible

que en otros problemas MMR en redes pueda aportar en mayor medida. Particularmente, en

problema donde la topología permita generar restricciones apareadas ya sea del tipo disjuntas o

anidadas.

En relación a las variantes del algoritmo de Benders, para futuros trabajos es

recomendable considerar lo siguiente. Para la versión de Benders que incluye cortes heurísticos es

importante experimentar en mayor grado en el número de cortes ingresados y la estructura

utilizada en el vecindario que genera los cortes. En relación a la variante de Benders con cortes

incumbentes, en futuros trabajos se debe considerar la posibilidad de incorporar un conjunto de las

soluciones incumbentes encontradas en la resolución del problema maestro.

Desde el punto de vista heurístico, se entregan dos heurísticas constructivas que utilizan la

información intervalar a diferencia de las heurísticas de un escenario. Las nuevas heurísticas son

capaces de entregar mejores soluciones que Hu y Hm en algunos conjuntos de instancias. En

relación a la heurística constructiva dinámica, se pudo observar que en gran cantidad de ocasiones

entrega soluciones de mejor calidad que la versión básica. Además la estructura de este algoritmo

genera un gran espacio para la construcción de variantes. Es importante destacar que a través de

las heurísticas constructivas, se ha abordado el problema desde una perspectiva no estudiada a la

fecha.

Por otra parte se implementaron 3 metaheurísticas basadas en búsqueda local; mejora

iterativa, Simulated Annealing y GRASP, todas utilizando la misma vecindad. Las metaheurísticas

propuestas obtienen soluciones de similar calidad a lo propuesto en la literatura, existiendo un claro

trade off entre tiempo y calidad del gap, pues dicha mejora iterativa obtiene buenos resultados en

86

muy poco tiempo. Sin embargo, estos resultados son mejorados por GRASP y SA siendo que

estos últimos requieren de un mayor tiempo de ejecución. SA es el único algoritmo capaz de salir

de los óptimos locales de las instancias La y en general el que obtiene las mejores desviaciones.

GRASP cuenta con una fase constructiva que para algunos conjuntos de instancias funciona bien

por sí sola. Por otra parte, parece ser lógico pensar en la generación de diferentes estructuras de

vecindario, para conjuntos de instancias donde la topología sea particular como el caso de las

instancias LA o He. También es importante mencionar que las tres metaheurísticas pueden ser

exigidas en mayor medida, a través de un proceso de experimentación más profundo, con énfasis

en el ajuste de parámetros.

En el presente trabajo se estudiaron distintos conjuntos de instancias, comprobando que

tanto la topología del problema como la estructura de costos, generan de forma independiente un

impacto en la complejidad del problema. En forma particular se demostró, experimentalmente, que

para el algoritmo Branch and Cut propuesto, a menor valor del parámetro (en las instancias Mo)

este mejora su desempeño. Adicionalmente, en las instancias Ya se generaron dos categorías

(Ya(C,C) y Ya(C,2)), donde se observó que el crecimiento en el tiempo de ejecución al aumentar el

tamaño del problema es bastante más brusco en las primeras (Ya(C,C)). De forma complementaria

se tiene que en los distintos conjuntos de instancias, el efecto del pre procesamiento tiene distinto

impacto.

Las instancias La presentan un gran problema, tanto para algoritmos exactos como

heurísticos. De forma exacta sólo se resolvió una instancia de 30 nodos, que po lo demás es la

instancia de mayor tamaño que se tiene solución exacta para este conjutno. Por el lado heurístico,

es en este conjunto de instancias donde se presentan los peores resultado. Una de las alternativas

desde el punto de vista heurístico, es el uso de su topología, ya sea para la generación de

heurísticas ad-hoc, como para el uso de la topología en la generación de un vecindario.

Si bien se generó un aporte significativo en relación a los LB del conjunto de instancias

estudiadas a partir de las mejores soluciones conocidas es posible postular que, el mayor cuello de

botella se tiene en esta cota (LB) de modo que es imprescindible continuar con trabajos en este

aspecto para generar nuevas cotas.

Finalmente es preciso comentar que se ha realizado una propuesta extensa de

algoritmos para el MMR-ST, desde la perspectiva exacta y aproximada. A partir de esto, queda

abierta la posibilidad para futuras mejoras a los algoritmos propuestos.

87

REFERENCIAS BIBLIOGRAFÍA

Ahuja, R., Magnanti, T., & Reddy, M. (1995). Network Flows. En T. Ball, T. Magnanti, & G.

Neumhauser, Handbook of operation Research and management science (págs. 211-369).

Amsterdam: North-Holland.

Aissi, H., Bazgan, C., & Vanderpooten, D. (2005). Approximation complexity of min-max (regret)

versions of shortest path, spanning tree, and knapsack. Lect. Notes Comput. Sci , 3669, 862–873.

Álvarez-Miranda, E., Chen, X., Hu, X., & Candia-Véjar, A. (2011). Deterministic risk control cost-

efective network connections. Theoritical Computer science , 412, 257-264.

Álvarez-Miranda, E., Chen, X., Hu, X., & Candia-Véjar, A. (2010). Effiicient algorithm for the prize

collecting steiner tree problem with interval data. Lectures notes in computer science , 6124, 13-24.

Álvarez-Miranda, E., Ljubic, I., Raghavan, S., & Toth, P. (2012). The Recoverable Robust Two-

Level Network Design Problem. submit to .

Amberg, A., Domschke, W., & Vob, S. (1996). Capacitated minimum spanning trees: algorithms

using intelligent search. Combinatorial Optimization: Theory and parctice , 1, 9-40.

Aron, I., & Van Hentenryck, P. (2002). A contraint satisfaction approach to the robust spanning tree

with interval data. Proccedings of the international Conference on Uncertainty in Artificial

Intelligence , UAI, 18-25.

Aron, I., & Van Hentenryck, P. (2004). On Complexity of the robust spanning tree problem with

interval data. Operations Research Letters , 32, 36-40.

Averbakh, I. (2000). On the complexity of a class of combinatorial optimization problems with

uncertainty. Math. Program. Ser. , 127, 505–522.

Averbakh, I., & Berman, O. (2005). Minmax regret median location on a network under uncertainty.

Discrete Optimization , 5, 3-34.

Averbakh, I., & Lebedev, V. (2004). Interval data regret network optimization problems. Discr. App.

Math. , 138, 289–301.

Bellman, R., & Zadeh, L. (1970). Decision-making in a fuzzy environment. Management science ,

141-164.

Ben Tal, A., El Ghaoui, L., & Nemirovsky, A. (2009). Robust Optimization. New Jersey: Princeton

Series in Applied Mathemtics.

88

Benders, J. (1962). Partitioning procedures for solving mixed integer variables programming

problems. Numerische Mathematik , 4, 238–252.

Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and networks flows. Mathemmatical

Programming , 16, 259-271.

Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research , 52, 35-53.

Bondy, J., & Murty, U. (1976). Graph Theory With Applications. North Holland.

Boruvka, O. (1926). O jistém problému minimálním. Práce Mor. Prirodoved , 3, 37–58.

Boruvka, O. (1926b). Príspevek k resení otázky ekonomické stavby elektrovodních sítí.

Elektrotechnický , 15, 1953-1954.

Candia-Véjar, A., Álvarez-Miranda, E., & Maculan, N. (2011). Minmax regret combinatorial

optimization problems:an alalgorithmic perspective. Rairo Operation Research , 101-129.

Chang, N., & Davila, E. (2007). Minimax regret optimization analysis for a regional solid waste

management system. Waste Management , 820-832.

Chang, N., & Davila, E. (2006). Siting and routing assesment for solid waste management under

uncertainty using the grey min-max regret criterion. Environment Management , 654-672.

Chen, X., Hu, J., & Hu, X. (2009). A new model for path planning with interval data. Computers and

operations research , 36, 1893-1899.

Chen, X., Hu, J., & Hu, X. (2009b). A polinomial solvable minimum risk spanning tree problem with

interval data. European Journal Operation Research , 36, 43-46.

Chen, X., Hu, J., & Hu, X. (2007). On the minimum risk-sum path problem. ESCAPE’07

Proceedings Lectures Notes Computer Sciense , 175-185.

Conde, E., & Candia, A. (2007). Minimax regret spanning arborescences under uncertain costs.

European Journal Operation Research , 182, 326-327.

Cordeau, J., Laporte, G., & Mercier, A. (2000). A Benders decomposition approach for the

locomotive and car assignment problem. Transportation Science , 34, 133–149.

Dantzig, G. (1955). Linear Programming Under Uncertainty. Management Science , 3, 197-206.

Du, D., Smith, J., & Rubinstein, J. (200). Advances in Steiner Tree. Netherlands: Kluwer Academic

Publisher.

89

Dullerud, G., & Paganini, F. (2010). A Course in Robust Control Theory: A Convex Approach. New

York: Springer.

Feo, T., & Resende, M. (1989). A probabilistic heuristic for a computationally dificult set covering

problem. Operations Research Letters , 67-71.

Feo, T., & Resende, M. (1995). Greedy randomized adaptive search procedures. J. of Global

Optimization , 109-133.

Festa, P., & Resende, M. (2008). An annotated bibliography of GRASP part I: Algorithms. AT&T

Labs Research Technical Report , 1-24.

Festa, P., & Resende, M. (2008). An annotated bibliography of GRASP part II: Applications. AT&T

Labs Research Technical Report. , 1-42.

Festa, P., & Resende, M. (2001). GRASP: An annotated bibliography. AT&T Labs Research

Technical Report , 1-39.

Geoffrion, A. (1972). Generalized Benders decomposition. Journal of Optimization Theory and

Applications , 5, 822–844.

Glover, F. (1986). Future path for integer programming and links to artificial intellingence. Computer

and Operation Research , 533-549.

Godsil, C., & Royle, G. (2001). Algebraic Graph Theory. Springer.

Graham, R., & Hell, P. (1985). On the History of the Minimum Spanning Tree problem. Annals of

the History of Computing , 43-57.

Guan, Y., Ahmed, S., & Nemhauser, L. (2005). Sequential pairing of Mixed Integer Inequalities.

IPCO 2005 (págs. 23-34). Berlin: Springer-verlag.

HUANG, G., & LI, X. (2007). Data mining via minimal spanning tree clustering for prolonging lifetime

of wireless sensor networks. International Journal of Information Technology & Decision Making , 6,

235-251.

Huber, P., & Ronchetti, E. (2009). Robust Statistics (2 ed ed.). Cambridge: Wiley.

Hwang, F., Richards, D., & Winter, P. (1992). The Steiner Tree Problem. New York: North-Holland.

Jarník, B. (1930). O jistém problému minimálním. Práce Mor. Prírodoved. Spol , 6, 57-63.

Karasan, O., Pinar, M., & Yaman, H. (2001). The Robust shortest path problem with interval data.

Bilkent University.

90

Kasakci, A., Rozakis, S., & Vanderpooten, D. (2007). Energy crop supply in France: a min-max

regret aproach. J. Oper. Res. Lett. , 1470-1479.

Kasperski, A. (2008). Discrete Optimization with Interval Data. Berlin: Springer.

Kasperski, A., & Zielinski, P. (2006). An approximation algorithm for interval data minmax regret

combinatorial optimization problems. Information Processing Letters , 97, 177-180.

Kasperski, A., Makuchowski, M., & Zielinski, P. (2012). A tabu search algorithm for the minmax

regret minimum spanning tree problem with interval data. J Heuristics , 593-625.

Kaspeski, A., & Zielinski, P. (2004). Minimizing maximal regret in linear assigment problems with

intervalar data. (Raport serii PREPINTY nr. 007) . Wroclaw: Instytut Matematyki PWr.,.

Kiranyaz, S., & Gabbouj, M. (2007). Hierarchical Cellular Tree: An Efficient Indexing Scheme for

Content-Based Retrieval on Multimedia Databases. TRANSACTIONS ON MULTIMEDIA , 9, 102-

119.

Kirkpatrick, A. (1984). Optimization by simulated Annealing - quantitative studies. J. Stat. Phys. ,

975-986.

Kirkpatrick, S., Gellat, C., & Vecchi, M. (1983). Optimization by simulated annealing. Science 220 ,

671-680.

Korte, V., & Nesetril, J. (2001). Vojtech Jarnık’s work in combinatorial optimization. Discrete

Mathematics .

Kouvelis, P., & Yu, G. (1997). Robust Discrete Optimization and its applications. Dordrecht, The

Netherlands: Kluwer Academic Pablishers.

Kruskal, J. (1956). On the shortest spanning subtree of a graph and the travelling. Proc. Amer.

Math. Soc. , 7, 48-50.

Li, X., Yan, S., Xu, C., Nayak, A., & Stojmenovic, I. (2011). Localized delay-bounded and energy-

efficient data aggregation in wireless sensor and actor networks. WIRELESS COMMUNICATIONS

AND MOBILE COMPUTING , 11, 1603–1617.

Luolou, R., & Kanudia, A. (1999). Minimax regret strategies for greenhouse gas abatement:

methodology and aplications. Oper. Res. Lett. , 219-230.

Magnanti, T., & Wolsey, L. (1995). Optimal Trees. En T. Magnanti, & G. Neumhauser, Handbook of

operation Research and management science (págs. 503-615). Amsterdam: North-Holland.

91

Magnanti, T., & Wong, R. (1981). Accelerating Benders decomposition: Algorithmic enhancement

and model selection criteria. Operations Research , 23 (3), 464–483.

Magnanti, T., Mirchandani, R., & Wong, T. (1986). Tailoring Benders decomposition for

uncapacitated network design. Mathematical Programming Study , 26, 112-154.

Mardones, J. (2010). Heurísticas para el problema del vendedor viajero robusto con incertidumbre

intervalar. Curicó: Universidad de Talca.

Marti, K. (2008). Stochastic Optimization Methods. Munich: Springer.

McDaniel, D., & Devine, M. (1977). Management Science , 24, 312–379.

Mitchell, T. (1997). Machine Learning. McGraw Hill.

Montemanni, R. (2006). A Benders decomposition approach for the robust spanning tree proble

with intervalar data. Eur. J. Oper. Res. , 174, 1479–1490.

Montemanni, R., & Gambardella, L. (2005). A branch and bound algorithm for the ronust spanning

tree with interval data. European journal Operation Research , 161, 771-779.

Montemanni, R., Barta, J., & Gambardella, L. (2007). The robust travelling salesman problem with

intervalar data. Transportation science , 41 (3), 366-381.

Montemanni, R., Barta, J., Mastrolilli, M., & Gambardella, L. (2007). The robust traveling salesman

problem with interval data. Transportation Science , 41 (3), 366-381.

Narula, S., & Ho, C. (1980). Degree-constrained minimum spanning tree. Computer and Operation

Reserch , 7, 239–249.

Nesetril, J. (1997). A few remarks on the history of MST-Problem. Archivum Mathematicum Brno ,

15-22.

Nesetril, J., Milková, E., & Nesetrilová, H. (2001). Otakar Boruvka on minimum spanning tree

problem: Translation of both the 1926 papers, comments, history. Discrete Mathematics , 233, 3-36.

Nikulin, Y. (2008). Simulated annealing algorithm for the robust spanning tree. Journal Heuristic ,

14, 391-402.

Pereira, J., & Averbakh, I. (2011). The Robust Set Covering Problem with intervalar data. Ann Oper

Res .

Pérez, F., Candia, A., Astudillo, C., & Bardeen, M. (2012). A Simulated Annealing approach for the

minmax regret path problem. CLAIO. Rio de Janeiro.

92

Prim, R. (1957). Shortest connection networks and some generalizations. Bell System Technical

Journal , 36, 567-574.

Prömel, H., & Steger, A. (2002). The Steiner Tree Problem. A Tour Through Graphs, Algorithms

and Complexity . Wiesbaden: Vieweg Verlag.

Richardson, R. (1976). An optimization approach to routing aircraft. Transportation Science , 52-71.

Rocha, A., & Dias, Z. (2012). Image Phylogeny by Minimal Spanning Trees. TRANSACTIONS ON

INFORMATION FORENSICS AND SECURITY, , 744-788.

Salazar-Neumann, M. (2007). The robust minimum spanning tree problem: Compact and convex

uncertainty. Operation Research letters , 38, 1153-1163.

Santos, D., De Sousa, D., & Alvelos, F. (2008). Traffic engineering of telecommunication networks

based on multiple spanning tree routing. FITraMEn , 114-129.

Schneider, J., & Kirkpatrick, S. (2006). Stochastic Optimization. Berlin: Springer.

Tamir, A. (2000). Facility location problems on tree graphs with different speeds for customer and

servers: A study on covering problems defined by families of subtrees. Working Paper, Department

of Statisticsand Operations Research, School of Mathematical Science, Tel-Aviv University .

Uryasev, S., & Pardalos, P. (2001). Stochastic Optimization: Algorithms and Applications.

Dordrecht: Kluwer academic publisher.

Yaman, H., Karasan, O., & Pinar, M. (2001). The robust spanning tree problem with interval data.

Operations Research Letters , 29, 31-40.

Zhang, L., Li, D., & Lim, A. (2010). Energy-efficient traffic-aware detour trees for geographical

routing. International Journal of Computer Networks & Communications , 2 (1), 154-168.

Zhang, Y., Ting, G., Cheng, J., Liang, J., Prusty, M., & Ann, S. (2011). Will the US Economy

Recover in 2010? A Minimal Spanning Tree Study. Physica A , 390, 2020-2050.

Zimmermann, H. (2005). Fuzzy Set Theory and its Applications (4 ed ed.). Springer.

93

ANEXO 1: ESTADÍSTICAS DE HEURÍSTICAS

TABLA 34. ESTADÍSTICAS DE HEURÍTICAS YA(C,C)

Hc Hcd Hu Hm

Min Av. Max desv Min Av. Max desv Min Av. Max desv Min Av. Max desv

Ya(10,10)-10 4.46 17.03 37.32 10.93 0.00 9.43 25.77 8.92 0.00 12.45 29.72 10.32 0.00 4.11 12.09 4.23

Ya(10,10)-20 0.00 2.02 4.00 1.35 0.26 3.22 14.44 4.27 0.24 2.79 5.67 1.51 0.00 4.43 9.06 2.48

Ya(10,10)-30 0.00 1.60 4.32 1.30 0.00 1.07 2.69 1.01 0.00 1.16 5.69 1.77 1.86 4.86 8.72 2.31

Ya(10,10)-40 0.00 0.86 2.12 0.80 0.13 0.98 2.31 0.77 0.00 0.93 1.98 0.77 2.65 5.68 8.44 1.81

Ya(10,10)-50 0.31 0.91 2.35 0.71 0.00 0.78 2.97 0.92 0.22 0.51 0.94 0.26 1.68 4.95 7.51 1.76

Ya(10,10)-60 0.02 0.73 1.81 0.58 0.00 0.65 1.35 0.49 0.00 0.57 1.29 0.50 4.17 5.53 8.45 1.40

Ya(10,10)-70 0.07 0.48 1.42 0.40 0.00 0.44 1.28 0.42 0.00 0.23 0.53 0.17 3.04 5.10 7.41 1.42

Ya(10,10)-80 0.09 0.39 0.71 0.20 0.03 0.44 0.72 0.23 0.00 0.30 0.78 0.27 3.05 5.74 9.26 1.77

Ya(10,10)-90 0.00 0.23 0.79 0.26 0.00 0.21 0.48 0.17 0.00 0.16 0.73 0.23 4.00 6.28 8.15 1.44

Ya(10,10)-100 0.00 0.23 0.75 0.21 0.14 0.24 0.51 0.13 0.00 0.10 0.26 0.09 3.33 6.01 7.48 1.32

Ya(15,15)-10 0.00 11.14 28.57 9.85 0.00 13.01 30.23 11.13 0.00 9.28 26.87 8.22 0.00 0.94 5.33 2.01

Ya(15,15)-20 2.38 3.92 7.74 1.75 0.00 3.58 7.59 2.62 0.93 2.95 6.32 1.53 0.00 3.05 7.90 2.81

Ya(15,15)-30 0.00 1.66 3.82 1.23 0.00 1.91 4.55 1.49 0.00 1.44 4.43 1.53 0.60 5.09 11.37 3.06

Ya(15,15)-40 0.28 1.05 2.22 0.59 0.00 0.78 1.88 0.54 0.02 0.56 2.61 0.76 3.90 6.42 9.25 1.61

Ya(15,15)-50 0.06 0.68 1.38 0.38 0.00 0.59 1.15 0.40 0.00 0.57 1.64 0.61 3.06 5.52 8.20 1.63

Ya(15,15)-60 0.00 0.31 0.79 0.23 0.00 0.33 1.22 0.39 0.00 0.25 1.08 0.35 5.20 6.23 8.02 1.02

Ya(15,15)-70 0.00 0.42 1.19 0.41 0.00 0.54 1.42 0.51 0.00 0.44 1.73 0.56 3.75 6.10 7.43 1.01

Ya(15,15)-80 0.11 0.43 0.82 0.24 0.00 0.51 1.22 0.45 0.00 0.29 0.63 0.19 4.61 6.31 8.66 1.29

Ya(15,15)-90 0.05 0.27 0.63 0.23 0.00 0.33 0.96 0.31 0.00 0.18 0.43 0.18 3.12 6.08 8.36 1.52

Ya(15,15)-100 0.02 0.21 0.43 0.15 0.03 0.17 0.38 0.11 0.00 0.16 0.58 0.18 4.01 5.71 6.63 0.83

Ya(20,20)-10 1.52 11.34 20.74 6.73 0.00 7.49 20.74 7.79 0.81 8.56 18.86 5.56 0.00 3.03 11.03 4.07

Ya(20,20)-20 0.00 2.11 6.69 2.21 0.00 1.81 7.65 2.64 0.00 1.98 10.34 3.27 0.03 3.30 7.37 2.49

Ya(20,20)-30 0.07 1.45 5.37 1.69 0.00 1.05 5.25 1.61 0.05 1.78 4.40 1.53 0.13 4.20 10.03 2.87

Ya(20,20)-40 0.05 0.60 1.40 0.44 0.00 0.69 1.93 0.61 0.27 0.77 1.16 0.36 1.40 5.60 14.56 4.10

Ya(20,20)-50 0.00 0.83 2.37 0.70 0.00 0.58 1.76 0.58 0.00 50 1.34 0.46 2.97 6.32 9.88 1.75

Ya(20,20)-60 0.04 0.51 1.26 0.38 0.04 0.56 1.28 0.40 0.00 0.33 0.79 0.28 2.44 4.76 5.95 1.27

Ya(20,20)-70 0.22 0.40 0.84 0.18 0.00 0.36 1.34 0.41 0.00 0.26 1.13 0.37 2.64 5.45 9.88 2.10

Ya(20,20)-80 0.01 0.29 0.59 0.21 0.00 0.43 1.05 0.36 0.01 0.25 0.60 0.19 4.31 6.16 7.92 1.20

Ya(20,20)-90 0.00 0.32 0.94 0.30 0.00 0.32 0.77 0.28 0.00 0.22 0.75 0.27 4.06 6.40 8.24 1.28

Ya(20,20)-100 0.05 0.20 0.54 0.14 0.09 0.28 0.45 0.14 0.00 0.16 0.57 0.18 2.62 7.01 10.00 2.21

94

TABLA 35. ESTADÍSTICAS DE HEURÍSTICAS YA(C,2C)

Hc Hcd Hu Hm

Min Av. Max Desv Min Av. Max desv Min Av. Max desv Min Av. Max desv

Ya(10,20)-10 0.00 3.36 15.94 5.17 0.00 1.29 8.69 2.66 0.00 1.67 8.51 2.78 0.00 3.24 9.25 3.71

Ya(10,20)-20 0.00 0.45 1.40 0.44 0.00 0.66 1.83 0.59 0.00 0.43 1.40 0.46 1.45 6.11 10.12 2.85

Ya(10,20)-30 0.00 0.51 2.32 0.68 0.00 0.59 1.50 0.52 0.00 0.33 1.50 0.46 1.23 3.76 8.65 2.06

Ya(10,20)-40 0.00 0.40 1.20 0.36 0.00 0.53 1.50 0.56 0.00 0.39 1.42 0.46 1.82 5.63 9.24 2.34

Ya(10,20)-50 0.00 0.29 0.77 0.28 0.00 0.27 0.92 0.33 0.00 0.21 0.80 0.27 2.93 5.51 8.77 2.07

Ya(10,20)-60 0.00 0.15 0.40 0.15 0.00 0.12 0.31 0.09 0.00 0.15 0.45 0.15 3.87 6.66 9.06 1.54

Ya(10,20)-70 0.00 0.20 0.51 0.16 0.00 0.15 0.55 0.20 0.00 0.09 0.38 0.12 4.04 6.51 10.05 2.01

Ya(10,20)-80 0.04 0.11 0.38 0.11 0.00 0.14 0.53 0.16 0.00 0.09 0.52 0.16 3.77 6.19 7.70 1.38

Ya(10,20)-90 0.00 0.08 0.20 0.08 0.00 0.09 0.33 0.11 0.00 0.06 0.31 0.10 4.79 6.72 10.27 1.59

Ya(10,20)-100 0.01 0.16 0.65 0.19 0.01 0.11 0.29 0.09 0.00 0.04 0.13 0.05 2.41 5.16 7.01 1.26

Ya(15,30)-10 0.00 2.17 10.73 3.32 0.00 4.96 11.21 4.30 0.00 4.20 20.42 6.55 0.00 4.56 11.58 3.37

Ya(15,30)-20 0.00 0.75 3.14 0.92 0.00 0.88 2.15 0.77 0.00 0.77 2.86 1.04 0.83 6.29 17.09 4.59

Ya(15,30)-30 0.00 0.25 1.03 0.33 0.00 0.36 1.89 0.58 0.00 0.21 1.03 0.35 5.45 7.03 10.38 1.73

Ya(15,30)-40 0.00 0.52 1.79 0.63 0.00 0.60 3.28 0.98 0.00 0.42 1.17 0.38 2.99 6.16 9.78 2.37

Ya(15,30)-50 0.00 0.25 0.93 0.28 0.00 0.15 0.41 0.15 0.00 0.12 0.48 0.19 2.86 5.79 9.07 1.86

Ya(15,30)-60 0.00 0.18 0.45 0.14 0.00 0.21 0.67 0.22 0.00 0.19 0.77 0.25 1.56 4.91 7.46 1.97

Ya(15,30)-70 0.00 0.19 0.51 0.17 0.00 0.13 0.29 0.13 0.00 0.07 0.26 0.09 3.83 6.34 8.75 1.63

Ya(15,30)-80 0.01 0.10 0.34 0.10 0.00 0.08 0.14 0.06 0.00 0.05 0.17 0.06 2.92 5.68 8.46 1.83

Ya(15,30)-90 0.00 0.08 0.22 0.07 0.00 0.18 0.38 0.12 0.00 0.07 0.28 0.11 3.50 6.51 9.86 1.72

Ya(15,30)-100 0.00 0.14 0.35 0.11 0.00 0.10 0.23 0.08 0.00 0.04 0.25 0.08 3.09 5.29 7.09 1.52

Ya(20,40)-10 0.00 2.72 6.22 2.03 0.00 2.40 6.22 2.18 0.00 2.56 9.03 3.09 0.00 1.71 5.67 1.93

Ya(20,40)-20 0.00 0.70 3.19 1.04 0.00 0.70 3.01 0.96 0.00 0.25 1.70 0.54 1.50 6.91 11.84 3.78

Ya(20,40)-30 0.00 0.55 2.52 0.81 0.00 0.46 1.73 0.58 0.00 0.36 1.97 0.62 3.60 6.03 8.66 1.52

Ya(20,40)-40 0.00 0.21 0.71 0.29 0.00 0.18 0.89 0.29 0.00 0.11 0.55 0.19 4.56 6.53 8.97 1.71

Ya(20,40)-50 0.00 0.18 0.56 0.19 0.00 0.20 0.70 0.22 0.00 0.08 0.47 0.15 3.46 5.66 7.86 1.46

Ya(20,40)-60 0.00 0.09 0.35 0.11 0.01 0.18 0.55 0.17 0.00 0.08 0.32 0.11 2.35 4.90 7.01 1.49

Ya(20,40)-70 0.00 0.12 0.24 0.09 0.00 0.14 0.32 0.12 0.00 0.08 0.33 0.11 2.63 5.87 8.86 1.89

Ya(20,40)-80 0.02 0.18 0.45 0.13 0.00 0.16 0.43 0.16 0.00 0.06 0.16 0.06 3.86 6.54 9.66 1.82

Ya(20,40)-90 0.00 0.10 0.28 0.10 0.00 0.12 0.81 0.25 0.00 0.07 0.27 0.10 4.35 6.70 8.71 1.39

Ya(20,40)-100 0.00 0.10 0.23 0.09 0.00 0.08 0.24 0.09 0.00 0.04 0.20 0.06 4.52 6.26 9.04 1.59

95

TABLA 36. ESTADÍSTICAS HEURÍSTICAS HE

Hc Hcd Hu Hm

Min Av. Max desv Min Av. Max desv Min Av. Max desv Min Av. Max desv

He0-10 5.8 19.6 48.6 15.1 0.0 11.7 34.7 12.7 0.0 23.9 63.9 23.4 0.0 5.2 10.19 4.11

He0-20 2.5 26.3 52.4 18.4 3.7 25.2 49.7 15.9 3.7 31.1 80.9 22.1 0.0 4.6 10.56 3.26

He0-30 18.4 33.4 61.6 15.9 15.0 23.4 45.7 9.1 17.5 31.0 60.6 13.0 1.1 2.7 6.76 1.75

He0-40 16.6 28.8 41.4 9.3 9.7 24.2 33.1 6.8 10.9 30.1 49.4 11.1 0.1 3.0 5.74 2.01

He0-50 14.2 27.1 64.3 14.0 8.2 21.2 32.5 8.0 11.8 20.2 35.3 7.0 0.5 3.2 7.38 2.46

He0-60 16.1 31.7 44.6 8.5 9.5 26.4 38.6 9.3 11.3 23.7 32.6 8.1 0.8 3.7 7.75 2.31

He0-70 16.3 32.9 50.7 13.6 13.8 33.4 50.0 10.7 23.5 37.4 56.8 11.2 1.3 2.8 4.49 1.18

He0-80 23.9 35.1 46.4 7.0 21.8 32.7 45.6 8.4 15.7 33.2 42.7 8.3 0.8 1.9 4.76 1.17

He0-90 13.8 29.6 39.7 8.7 21.8 32.6 49.4 8.4 16.2 31.8 50.6 9.9 0.8 2.8 8.20 2.15

He0-100 23.2 31.0 44.4 6.1 17.0 24.4 34.3 5.5 19.0 26.2 40.1 6.9 1.0 2.7 5.22 1.32

He1-10 5.8 19.6 48.6 15.1 0.0 11.7 34.7 12.7 0.0 23.9 63.9 23.4 0.0 5.2 10.19 4.11

He1-20 8.7 23.9 46.3 10.00 2.8 19.9 36.27 12.34 7.3 32.1 54.64 16.43 0.00 3.9 10.39 3.82

He1-30 12.83 23.33 35.00 8.45 6.73 20.79 39.18 9.99 8.41 28.87 43.10 9.79 0.00 2.1 7.02 2.35

He1-40 13.52 22.49 34.84 6.73 4.87 18.03 28.74 7.54 13.97 24.56 36.51 6.63 1.08 2.8 4.89 1.46

He1-50 11.82 20.00 27.51 6.29 9.46 19.17 26.47 5.09 11.28 26.20 46.61 9.18 1.02 2.9 5.87 1.57

He1-60 12.13 25.01 33.40 6.82 10.74 23.20 39.31 9.80 6.88 28.81 46.34 13.16 0.96 2.9 5.49 1.45

He1-70 10.78 21.50 34.10 7.55 11.77 19.06 31.06 5.63 12.16 22.99 33.39 6.33 1.41 3.6 6.64 1.73

He1-80 11.39 22.25 34.04 7.10 9.75 18.87 26.99 4.98 13.19 25.27 37.83 6.88 0.79 2.9 6.10 1.50

He1-90 10.94 19.78 28.51 7.41 10.54 19.79 30.96 7.33 20.04 25.34 36.87 5.48 1.74 3.3 5.67 1.31

He1-100 14.45 19.53 25.66 3.62 9.59 17.14 27.12 4.97 14.50 21.14 25.94 3.86 1.40 3.4 4.77 1.08

96

TABLA 37. ESTADÍSTICAS HEURÍSTICAS MO

Hc Hcd Hu Hm

Min Av. Max desv Min Av. Max desv Min Av. Max desv Min Av. Max Desv

Mo(0.15)-10 0.00 44.83 98.92 41.23 0.00 41.17 169.76 57.79 0.00 3.20 31.46 9.93 0.00 0.00 0.00 0.00

Mo(0.15)-20 0.00 37.82 274.51 84.40 0.00 22.52 152.15 47.95 0.00 23.67 113.35 34.14 0.00 2.13 19.91 6.26

Mo(0.15)-30 0.00 28.05 84.67 28.38 0.00 24.15 83.52 24.75 0.00 7.60 20.13 8.01 0.00 1.57 7.22 2.70

Mo(0.15)-40 0.00 32.91 79.93 25.83 0.00 52.44 130.76 45.42 0.00 16.98 40.36 14.52 0.00 0.56 3.90 1.29

Mo(0.15)-50 28.90 69.53 123.84 32.79 31.73 78.02 172.05 49.43 0.00 8.58 25.06 8.14 0.00 0.71 4.61 1.49

Mo(0.15)-60 10.02 32.16 73.97 22.89 5.60 56.00 132.00 39.15 2.01 13.26 27.20 9.97 0.00 0.25 2.25 0.71

Mo(0.15)-70 1.11 37.65 96.11 26.51 50 38.72 96.90 29.73 0.88 12.51 34.53 9.79 0.00 0.38 1.67 0.55

Mo(0.15)-80 5.82 39.88 62.41 19.42 13.77 51.67 114.68 31.43 0.00 10.43 22.07 6.96 0.00 1.65 5.82 1.99

Mo(0.15)-90 22.06 61.47 132.96 31.88 17.66 55.84 111.57 28.96 3.40 12.19 32.55 8.89 0.00 1.17 4.33 1.52

Mo(0.15)-100 7.87 36.08 55.26 15.24 28.87 63.66 102.38 24.32 1.88 14.86 24.23 7.98 0.00 0.57 4.43 1.42

Mo(0.50)-10 0.00 5.97 39.79 12.26 0.00 6.08 39.79 12.72 0.00 4.79 34.53 10.77 0.00 2.68 8.00 3.27

Mo(0.50)-20 0.00 9.09 31.06 9.05 0.00 14.53 46.05 15.55 1.63 12.24 36.31 11.64 0.00 2.06 6.23 1.97

Mo(0.50)-30 0.00 6.57 19.84 6.69 1.03 9.25 29.16 8.03 0.00 3.74 9.60 3.65 0.00 1.84 5.92 2.21

Mo(0.50)-40 4.22 8.25 12.65 2.60 2.08 9.35 24.44 6.64 1.46 6.00 10.74 2.70 0.00 3.07 7.30 2.11

Mo(0.50)-50 3.07 10.42 20.40 5.74 2.54 14.34 28.48 7.57 3.07 10.32 22.83 5.96 0.60 3.11 6.23 2.13

Mo(0.50)-60 2.79 9.50 18.61 5.37 3.74 12.75 23.22 6.95 0.27 8.45 13.57 4.50 0.16 2.60 4.11 1.22

Mo(0.50)-70 4.25 8.30 16.78 4.43 15 13.64 23.55 5.91 2.52 8.82 17.25 4.95 0.00 3.30 6.51 2.37

Mo(0.50)-80 5.59 9.46 14.06 2.75 8.09 12.22 19.02 4.08 2.91 6.31 8.84 1.97 0.30 3.68 9.09 2.57

Mo(0.50)-90 4.10 9.29 23.10 5.50 4.14 12.12 23.70 6.62 0.57 8.65 14.98 4.59 0.87 3.89 8.34 2.11

Mo(0.50)-100 4.86 9.36 15.99 3.95 4.60 11.95 20.88 5.10 3.73 9.24 15.97 3.25 0.77 2.10 3.81 0.93

Mo(0.85)-10 0.00 0.39 1.65 0.66 0.00 0.44 2.22 0.79 0.00 1.13 7.65 2.37 0.00 0.69 3.52 1.22

Mo(0.85)-20 0.00 1.19 3.18 1.27 0.00 4.13 14.44 4.41 0.00 4.34 11.28 3.51 0.61 5.89 12.02 4.10

Mo(0.85)-30 0.00 1.82 4.75 1.73 0.00 2.49 5.97 2.16 0.01 1.85 4.39 1.41 0.97 3.50 5.66 1.41

Mo(0.85)-40 0.00 3.33 6.72 2.35 0.00 3.12 6.59 2.22 0.31 4.53 10.41 2.90 1.19 3.26 6.98 1.62

Mo(0.85)-50 0.31 1.85 4.56 1.39 1.23 2.26 4.18 1.03 0.21 1.55 5.13 1.54 3.19 4.70 8.61 1.69

Mo(0.85)-60 1.20 2.74 5.43 1.23 0.35 2.52 4.54 1.69 50 2.94 7.52 2.07 1.22 4.05 8.77 2.44

Mo(0.85)-70 50 2.83 6.17 1.78 0.52 2.19 5.20 1.41 0.89 2.87 6.36 1.83 1.03 4.24 7.55 1.94

Mo(0.85)-80 1.26 2.45 5.26 1.28 0.95 2.31 4.76 1.16 0.34 1.93 5.04 1.30 1.41 3.58 7.10 1.60

Mo(0.85)-90 0.91 2.13 3.80 1.08 0.75 2.42 3.94 1.10 0.90 2.04 3.20 0.79 2.35 3.97 5.83 0.96

Mo(0.85)-100 1.40 2.60 4.22 1.20 1.13 2.83 5.12 1.33 0.68 2.10 5.71 1.47 1.63 3.52 5.73 1.36

ANEXO 2: PARÁMETROS GRASP

TABLA 38. RESULTADOS DE GRASP PARA 100 NODOS CON DISTINTOS CONJUNTOS DE PARÁMETROS POR

FAMILIA DE INSTANCIAS.

Instance FO time FOKZ UB-B&C LB-B&C ciclos alpha sol Mej. min Mej av. Mej. max H. Básica

Ya(10-10)-0 119847 246.771 119847 120154 107996 5000 0.03 20 0 1701 500 120013

Ya(10-10)-0 119847 250.287 119847 120154 107996 5000 0.03 20 0 2017 568 120013

Ya(10-10)-0 119847 247.385 119847 120154 107996 5000 0.03 20 0 1814 536 120013

Ya(10-10)-0 119847 249.304 119847 120154 107996 5000 0.03 20 0 2274 557 120013

Ya(10-10)-0 119847 250.38 119847 120154 107996 5000 0.03 20 0 1648 577 120013

Ya(10-10)-0 119847 246.481 119847 120154 107996 5000 0.03 20 0 1683 455 120013

Ya(10-10)-0 119960 246.013 119847 120154 107996 5000 0.03 20 0 2026 629 120013

Ya(10-10)-0 119847 247.759 119847 120154 107996 5000 0.03 20 0 2378 430 120013

Ya(10-10)-0 119847 246.527 119847 120154 107996 5000 0.03 20 0 1399 510 120013

Ya(10-10)-0 119847 244.999 119847 120154 107996 5000 0.03 20 0 2378 691 120013

Ya(10-10)-1 125712 258.789 125683 125759 114128 5000 0.03 20 0 1862 333 125759

Ya(10-10)-1 125683 258.399 125683 125759 114128 5000 0.03 20 2 489 201 125759

Ya(10-10)-1 125710 258.337 125683 125759 114128 5000 0.03 20 0 1280 275 125759

Ya(10-10)-1 125710 259.366 125683 125759 114128 5000 0.03 20 0 1862 368 125759

Ya(10-10)-1 125683 259.569 125683 125759 114128 5000 0.03 20 4 1500 360 125759

Ya(10-10)-1 125685 259.647 125683 125759 114128 5000 0.03 20 0 1211 385 125759

Ya(10-10)-1 125683 259.351 125683 125759 114128 5000 0.03 20 0 1817 704 125759

Ya(10-10)-1 125683 258.758 125683 125759 114128 5000 0.03 20 0 1689 494 125759

Ya(10-10)-1 125751 258.539 125683 125759 114128 5000 0.03 20 0 1512 248 125759

Ya(10-10)-1 125685 258.352 125683 125759 114128 5000 0.03 20 0 713 286 125759

Ya(10-10)-4 120689 253.407 120614 120817 108482 5000 0.03 20 0 2347 557 120817

Ya(10-10)-4 120722 251.768 120614 120817 108482 5000 0.03 20 143 1288 605 120817

Ya(10-10)-4 120647 250.443 120614 120817 108482 5000 0.03 20 33 1419 629 120817

Ya(10-10)-4 120713 250.817 120614 120817 108482 5000 0.03 20 0 2111 809 120817

Ya(10-10)-4 120817 250.224 120614 120817 108482 5000 0.03 20 0 1992 606 120817

Ya(10-10)-4 120689 251.129 120614 120817 108482 5000 0.03 20 0 1690 550 120817

Ya(10-10)-4 120831 251.223 120614 120817 108482 5000 0.03 20 0 1034 391 120817

Ya(10-10)-4 120758 251.285 120614 120817 108482 5000 0.03 20 23 1803 646 120817

Ya(10-10)-4 120689 250.349 120614 120817 108482 5000 0.03 20 237 1468 708 120817

Ya(10-10)-4 120614 251.082 120614 120817 108482 5000 0.03 20 0 1728 614 120817

Ya(10-10)-5 121259 255.882 121178 121337 108795 5000 0.03 20 0 966 179 121337

Ya(10-10)-5 121259 246.808 121178 121337 108795 5000 0.03 20 0 791 210 121337

Ya(10-10)-5 121348 245.435 121178 121337 108795 5000 0.03 20 42 758 253 121337

Ya(10-10)-5 121219 246.324 121178 121337 108795 5000 0.03 20 40 368 177 121337

Ya(10-10)-5 121301 247.651 121178 121337 108795 5000 0.03 20 0 286 124 121337

Ya(10-10)-5 121221 246.356 121178 121337 108795 5000 0.03 20 0 1312 249 121337

98

Ya(10-10)-5 121301 245.95 121178 121337 108795 5000 0.03 20 0 612 143 121337

Ya(10-10)-5 121348 247.042 121178 121337 108795 5000 0.03 20 0 877 134 121337

Ya(10-10)-5 121221 242.003 121178 121337 108795 5000 0.03 20 0 718 198 121337

Ya(10-10)-5 121308 247.9 121178 121337 108795 5000 0.03 20 0 844 145 121337

Ya(10-10)-6 128063 230.49 128012 128287 115439 5000 0.03 20 0 510 126 128186

Ya(10-10)-6 128085 227.885 128012 128287 115439 5000 0.03 20 0 338 121 128186

Ya(10-10)-6 128113 222.035 128012 128287 115439 5000 0.03 20 0 606 166 128186

Ya(10-10)-6 128012 219.071 128012 128287 115439 5000 0.03 20 0 275 70 128186

Ya(10-10)-6 128012 219.04 128012 128287 115439 5000 0.03 20 0 716 134 128186

Ya(10-10)-6 128012 218.822 128012 128287 115439 5000 0.03 20 0 753 175 128186

Ya(10-10)-6 128186 224.204 128012 128287 115439 5000 0.03 20 0 530 136 128186

Ya(10-10)-6 128161 219.149 128012 128287 115439 5000 0.03 20 0 582 122 128186

Ya(10-10)-6 128012 228.871 128012 128287 115439 5000 0.03 20 0 367 90 128186

Ya(10-10)-6 128012 228.871 128012 128287 115439 5000 0.03 20 0 367 90 128186

Ya(10-20)-0 176738 293.805 176639 176757 164436 5000 0.03 15 0 1380 323 176757

Ya(10-20)-0 176893 288.164 176639 176757 164436 5000 0.03 15 0 2972 390 176757

Ya(10-20)-0 176820 289.115 176639 176757 164436 5000 0.03 15 0 931 244 176757

Ya(10-20)-0 176639 291.377 176639 176757 164436 5000 0.03 15 0 1539 318 176757

Ya(10-20)-0 176639 287.743 176639 176757 164436 5000 0.03 15 0 403 97 176757

Ya(10-20)-0 176656 287.68 176639 176757 164436 5000 0.03 15 0 2967 516 176757

Ya(10-20)-0 176820 291.221 176639 176757 164436 5000 0.03 15 0 1467 276 176757

Ya(10-20)-0 176755 291.704 176639 176757 164436 5000 0.03 15 0 1898 270 176757

Ya(10-20)-0 176738 287.275 176639 176757 164436 5000 0.03 15 0 2061 451 176757

Ya(10-20)-0 176729 290.94 176639 176757 164436 5000 0.03 15 0 4565 587 176757

Ya(10-20)-3 161195 260.645 161103 161106 151902 5000 0.03 15 0 1909 443 161106

Ya(10-20)-3 161103 261.144 161103 161106 151902 5000 0.03 15 0 1938 561 161106

Ya(10-20)-3 161147 261.284 161103 161106 151902 5000 0.03 15 0 1688 646 161106

Ya(10-20)-3 161103 261.098 161103 161106 151902 5000 0.03 15 0 1204 342 161106

Ya(10-20)-3 161165 260.224 161103 161106 151902 5000 0.03 15 0 1053 365 161106

Ya(10-20)-3 161261 259.99 161103 161106 151902 5000 0.03 15 0 1423 417 161106

Ya(10-20)-3 161103 259.569 161103 161106 151902 5000 0.03 15 0 1949 670 161106

Ya(10-20)-3 161103 261.129 161103 161106 151902 5000 0.03 15 3 1988 505 161106

Ya(10-20)-3 161204 255.575 161103 161106 151902 5000 0.03 15 0 2334 443 161106

Ya(10-20)-3 161103 252.674 161103 161106 151902 5000 0.03 15 0 1777 475 161106

Ya(10-20)-4 181783 289.957 181698 181698 169776 5000 0.03 15 0 1788 535 181698

Ya(10-20)-4 181698 286.01 181698 181698 169776 5000 0.03 15 0 1035 308 181698

Ya(10-20)-4 181751 290.395 181698 181698 169776 5000 0.03 15 0 1870 468 181698

Ya(10-20)-4 181751 286.947 181698 181698 169776 5000 0.03 15 0 1415 447 181698

Ya(10-20)-4 181698 289.676 181698 181698 169776 5000 0.03 15 0 1662 331 181698

Ya(10-20)-4 181751 285.793 181698 181698 169776 5000 0.03 15 0 1282 368 181698

Ya(10-20)-4 181835 289.505 181698 181698 169776 5000 0.03 15 0 1641 591 181698

99

Ya(10-20)-4 181751 289.406 181698 181698 169776 5000 0.03 15 0 2847 790 181698

Ya(10-20)-4 181836 275.419 181698 181698 169776 5000 0.03 15 0 2016 458 181698

Ya(10-20)-4 181751 273.827 181698 181698 169776 5000 0.03 15 0 1130 243 181698

Ya(10-20)-5 179615 273.609 179589 179740 168533 5000 0.03 15 0 833 140 179740

Ya(10-20)-5 179624 276.214 179589 179740 168533 5000 0.03 15 0 740 84 179740

Ya(10-20)-5 179611 275.747 179589 179740 168533 5000 0.03 15 0 611 84 179740

Ya(10-20)-5 179589 273.266 179589 179740 168533 5000 0.03 15 0 1121 238 179740

Ya(10-20)-5 179740 272.158 179589 179740 168533 5000 0.03 15 0 1828 233 179740

Ya(10-20)-5 179593 276.526 179589 179740 168533 5000 0.03 15 0 1953 352 179740

Ya(10-20)-5 179615 276.962 179589 179740 168533 5000 0.03 15 0 712 140 179740

Ya(10-20)-5 179602 273.656 179589 179740 168533 5000 0.03 15 0 1840 310 179740

Ya(10-20)-5 179589 273.736 179589 179740 168533 5000 0.03 15 0 423 107 179740

Ya(10-20)-5 179589 273.736 179589 179740 168533 5000 0.03 15 0 423 107 179740

Ya(10-20)-6 190300 251.301 190300 190300 179275 5000 0.03 15 0 562 90 190300

Ya(10-20)-6 190300 254.359 190300 190300 179275 5000 0.03 15 0 256 44 190300

Ya(10-20)-6 190300 254.09 190300 190300 179275 5000 0.03 15 0 169 21 190300

Ya(10-20)-6 190323 263.335 190300 190300 179275 5000 0.03 15 0 355 71 190300

Ya(10-20)-6 190312 258.984 190300 190300 179275 5000 0.03 15 0 774 210 190300

Ya(10-20)-6 190300 255.507 190300 190300 179275 5000 0.03 15 0 397 65 190300

Ya(10-20)-6 190323 258.797 190300 190300 179275 5000 0.03 15 0 98 23 190300

Ya(10-20)-6 190334 255.672 190300 190300 179275 5000 0.03 15 0 1683 253 190300

Ya(10-20)-6 190300 255.415 190300 190300 179275 5000 0.03 15 0 524 75 190300

Ya(10-20)-6 190312 255.899 190300 190300 179275 5000 0.03 15 0 355 94 190300

He0-0 133829 108.171 133829 136318 95699 15000 0.03 5 61278 92522 75512 137486

He0-0 134012 108.41 133829 136318 95699 15000 0.03 5 80632 95617 87526 137486

He0-0 133829 108.217 133829 136318 95699 15000 0.03 5 65113 92430 81780 137486

He0-0 133829 108.763 133829 136318 95699 15000 0.03 5 79728 97313 87358 137486

He0-0 133949 109.324 133829 136318 95699 15000 0.03 5 68277 108748 88633 137486

He0-0 134012 107.656 133829 136318 95699 15000 0.03 5 66606 93168 82808 137486

He0-0 133829 109.434 133829 136318 95699 15000 0.03 5 65907 92385 81802 137486

He0-0 133829 106.128 133829 136318 95699 15000 0.03 5 59556 92385 73894 137486

He0-0 133940 109.678 133829 136318 95699 15000 0.03 5 76898 91969 85625 137486

He0-0 133920 109.028 133829 136318 95699 15000 0.03 5 72025 95860 86522 137486

He0-1 126958 120.807 126587 127536 91725.1 15000 0.03 5 58304 87246 72656 128790

He0-1 126587 120.885 126587 127536 91725.1 15000 0.03 5 67038 129876 95175 128790

He0-1 126868 121.212 126587 127536 91725.1 15000 0.03 5 70974 122359 92468 128790

He0-1 126717 120.9 126587 127536 91725.1 15000 0.03 5 53165 95180 76027 128790

He0-1 127007 120.759 126587 127536 91725.1 15000 0.03 5 51607 86750 67201 128790

He0-1 127007 120.604 126587 127536 91725.1 15000 0.03 5 65232 87464 72764 128790

He0-1 126868 120.136 126587 127536 91725.1 15000 0.03 5 70900 121451 90242 128790

He0-1 126868 119.667 126587 127536 91725.1 15000 0.03 5 64811 87356 73299 128790

100

He0-1 127157 120.401 126587 127536 91725.1 15000 0.03 5 79391 119739 89753 128790

He0-1 127115 120.666 126587 127536 91725.1 15000 0.03 5 70568 121510 87712 128790

He0-3 117676 117.796 117676 120177 83967.2 15000 0.03 5 59442 89331 75485 123814

He0-3 117676 116.781 117676 120177 83967.2 15000 0.03 5 54818 81368 73905 123814

He0-3 117728 117.11 117676 120177 83967.2 15000 0.03 5 65136 83147 72813 123814

He0-3 117941 117.452 117676 120177 83967.2 15000 0.03 5 40663 82567 68323 123814

He0-3 117941 116.876 117676 120177 83967.2 15000 0.03 5 53815 77538 68419 123814

He0-3 117728 117.281 117676 120177 83967.2 15000 0.03 5 37340 78121 62418 123814

He0-3 117676 116.423 117676 120177 83967.2 15000 0.03 5 51693 83232 70327 123814

He0-3 117728 116.797 117676 120177 83967.2 15000 0.03 5 57859 77675 67063 123814

He0-3 117941 117.359 117676 120177 83967.2 15000 0.03 5 54561 84390 71183 123814

He0-3 117941 116.781 117676 120177 83967.2 15000 0.03 5 51352 80215 64813 123814

He0-5 122985 117.359 122985 124475 88660.9 15000 0.03 5 49404 57177 53507 125015

He0-5 123028 117.109 122985 124475 88660.9 15000 0.03 5 45590 59962 53428 125015

He0-5 122985 117.624 122985 124475 88660.9 15000 0.03 5 39984 58206 49780 125015

He0-5 123028 117.312 122985 124475 88660.9 15000 0.03 5 48472 61817 55273 125015

He0-5 122985 117.375 122985 124475 88660.9 15000 0.03 5 51984 57266 54893 125015

He0-5 123050 116.72 122985 124475 88660.9 15000 0.03 5 50685 78107 60960 125015

He0-5 123059 117.39 122985 124475 88660.9 15000 0.03 5 47333 71020 58477 125015

He0-5 122985 117.749 122985 124475 88660.9 15000 0.03 5 26615 70040 52239 125015

He0-5 122985 117.234 122985 124475 88660.9 15000 0.03 5 40020 55315 47735 125015

He0-5 123059 117.374 122985 124475 88660.9 15000 0.03 5 45555 62849 55538 125015

He0-7 143769 127.702 143753 146374 102881 15000 0.03 5 51752 74029 64272 147881

He0-7 143895 127.608 143753 146374 102881 15000 0.03 5 49719 77423 66628 147881

He0-7 143852 127.811 143753 146374 102881 15000 0.03 5 55427 70230 61192 147881

He0-7 143937 127.827 143753 146374 102881 15000 0.03 5 59806 71241 65120 147881

He0-7 143769 128.435 143753 146374 102881 15000 0.03 5 61040 85944 71230 147881

He0-7 143868 128.95 143753 146374 102881 15000 0.03 5 52234 85170 65983 147881

He0-7 143769 127.733 143753 146374 102881 15000 0.03 5 50179 74988 64205 147881

He0-7 143864 127.296 143753 146374 102881 15000 0.03 5 57827 85739 71563 147881

He0-7 144010 127.561 143753 146374 102881 15000 0.03 5 57906 86328 71844 147881

He0-7 143753 127.733 143753 146374 102881 15000 0.03 5 57711 70860 63305 147881

Mo(0.85)-2 132712 300.004 132712 134462 106073 10000 0.03 20 2119 9328 5877 134213

Mo(0.85)-2 132712 151.617 132712 134462 106073 5000 0.03 20 2564 11730 5748 134213

Mo(0.85)-2 132719 149.418 132712 134462 106073 5000 0.03 20 1096 10127 4858 134213

Mo(0.85)-2 132712 152.142 132712 134462 106073 5000 0.03 20 1400 10103 5485 134213

Mo(0.85)-2 132739 151.742 132712 134462 106073 5000 0.03 20 2612 11907 6294 134213

Mo(0.85)-2 132712 152.1 132712 134462 106073 5000 0.03 20 1481 9328 5420 134213

Mo(0.85)-2 132712 151.648 132712 134462 106073 5000 0.03 20 2102 10509 5851 134213

Mo(0.85)-2 132728 151.071 132712 134462 106073 5000 0.03 20 2415 9667 5947 134213

Mo(0.85)-2 132712 151.304 132712 134462 106073 5000 0.03 20 1848 9679 4967 134213

101

Mo(0.85)-2 132712 150.306 132712 134462 106073 5000 0.03 20 2388 10999 5825 134213

Mo(0.85)-3 151588 178.262 151476 153298 117714 5000 0.03 20 4007 12733 9013 153949

Mo(0.85)-3 151823 177.622 151476 153298 117714 5000 0.03 20 5026 23655 11265 153949

Mo(0.85)-3 151559 176.779 151476 153298 117714 5000 0.03 20 5478 13655 8463 153949

Mo(0.85)-3 151527 177.793 151476 153298 117714 5000 0.03 20 6252 16676 9232 153949

Mo(0.85)-3 152144 177.699 151476 153298 117714 5000 0.03 20 4062 12297 8091 153949

Mo(0.85)-3 151808 177.887 151476 153298 117714 5000 0.03 20 3527 17414 8706 153949

Mo(0.85)-3 151982 178.121 151476 153298 117714 5000 0.03 20 4209 17681 9046 153949

Mo(0.85)-3 151864 178.277 151476 153298 117714 5000 0.03 20 3891 12866 7620 153949

Mo(0.85)-3 152462 178.246 151476 153298 117714 5000 0.03 20 3218 17301 10014 153949

Mo(0.85)-3 151613 177.621 151476 153298 117714 5000 0.03 20 4934 13563 8286 153949

Mo(0.85)-6 131030 166.281 131030 132756 105948 5000 0.03 20 6259 20580 12684 133789

Mo(0.85)-6 131455 165.938 131030 132756 105948 5000 0.03 20 5190 18608 11824 133789

Mo(0.85)-6 131495 166.718 131030 132756 105948 5000 0.03 20 6782 18621 12356 133789

Mo(0.85)-6 132135 166.077 131030 132756 105948 5000 0.03 20 2665 17825 11774 133789

Mo(0.85)-6 131341 166.405 131030 132756 105948 5000 0.03 20 7104 15652 10983 133789

Mo(0.85)-6 132142 165.298 131030 132756 105948 5000 0.03 20 4706 18332 11672 133789

Mo(0.85)-6 131030 165.531 131030 132756 105948 5000 0.03 20 7488 18943 13105 133789

Mo(0.85)-6 131793 164.908 131030 132756 105948 5000 0.03 20 8338 21053 12689 133789

Mo(0.85)-6 132127 165.657 131030 132756 105948 5000 0.03 20 7230 16627 12811 133789

Mo(0.85)-6 132009 165.485 131030 132756 105948 5000 0.03 20 7400 18083 12494 133789

Mo(0.85)-8 126741 154.409 126741 129786 101729 5000 0.03 20 3000 15168 7835 129208

Mo(0.85)-8 126741 155.033 126741 129786 101729 5000 0.03 20 5380 12411 7938 129208

Mo(0.85)-8 126741 152.786 126741 129786 101729 5000 0.03 20 3730 12665 7601 129208

Mo(0.85)-8 126855 149.853 126741 129786 101729 5000 0.03 20 3920 11627 6950 129208

Mo(0.85)-8 126741 150.649 126741 129786 101729 5000 0.03 20 2091 10367 7028 129208

Mo(0.85)-8 126741 149.386 126741 129786 101729 5000 0.03 20 2702 15170 7560 129208

Mo(0.85)-8 126741 149.76 126741 129786 101729 5000 0.03 20 4416 16750 7741 129208

Mo(0.85)-8 126741 149.901 126741 129786 101729 5000 0.03 20 2500 14951 7502 129208

Mo(0.85)-8 126741 149.916 126741 129786 101729 5000 0.03 20 2493 13772 7720 129208

Mo(0.85)-8 126884 150.01 126741 129786 101729 5000 0.03 20 3240 14929 7381 129208

Mo(0.85)-9 134316 153.613 134133 135121 106658 5000 0.03 20 469 8104 4439 135121

Mo(0.85)-9 134652 152.817 134133 135121 106658 5000 0.03 20 1447 8555 4867 135121

Mo(0.85)-9 134793 153.754 134133 135121 106658 5000 0.03 20 41 8904 3666 135121

Mo(0.85)-9 135024 153.302 134133 135121 106658 5000 0.03 20 1585 8024 4788 135121

Mo(0.85)-9 135023 152.724 134133 135121 106658 5000 0.03 20 902 11866 4905 135121

Mo(0.85)-9 134652 153.489 134133 135121 106658 5000 0.03 20 978 9415 4712 135121

Mo(0.85)-9 135234 152.599 134133 135121 106658 5000 0.03 20 2087 11260 5276 135121

Mo(0.85)-9 134611 152.849 134133 135121 106658 5000 0.03 20 1344 9779 5949 135121

Mo(0.85)-9 134652 154.762 134133 135121 106658 5000 0.03 20 594 9668 5017 135121

Mo(0.85)-9 135024 154.986 134133 135121 106658 5000 0.03 20 1144 8321 4609 135121

Business

Algoritmos para el problema de árbol de expansión mínima robusto con datos intervalares