APLICACIÓN DE LA FORMULACIÓN DE R.k. Martin AL PROBLEMA DE STEINER EN GRAFOS

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial APLICACIÓN DE LA FORMULACIÓN de R.k. Martin AL PROBLEMA DE STEINER EN GRAFOS Autor: Sergio Flores Medina Tutor: Jose Manuel García Sánchez Dpto. Organización Industrial y Gestión de Empresas I Universidad de Sevilla Sevilla, 2019 iii Proyecto Fin de Carrera Grado en Ingenieria de Organización Industrial APLICACIÓN DE LA FORMULACIÓN de R.k. Martin AL PROBLEMA DE STEINER EN GRAFOS Autor: Sergio Flores Medina Tutor: Jose Manuel García Sánchez Profesor titular Dpto. de Organización Industrial y Gestion de Empresas I Universidad de Sevilla Sevilla, 2019 v Proyecto Fin de Carrera: APLICACIÓN DE LA FORMULACIÓN de R.k. Martin AL PROBLEMA DE STEINER EN GRAFOS Autor: Sergio Flores Medina Tutor: Jose Manuel García Sánchez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2019 El Secretario del Tribunal vii A mi familia A mis amigos A mis maestros ix Resumen En este proyecto de fin de grado evaluaremos una formulación matemática para problemas de selección de árboles en grafos. Concretamente, se van a estudiar dos problemas, el problema de MST (Minimum Spanning Tree) y el problema de Steiner. La formulación que se va a evaluar es la de R.k. Martin. Esta formulación conecta a los nodos del problema sin permitir ciclos. Existen otras formulaciones que no permiten ciclos, pero no se ha encontrado ningún análisis experimental de la eficiencia de dicha formulación. La eficiencia se va a medir con una batería de problemas existente en la web y se van a evaluar los tiempos de resolución de dicha estrategia de formulación aplicada sobre esta batería de problemas. Figura 29 Estructura de los problemas en .txt 34 Figura 30 Diagrama de flujo del código en C 35 Figura 31 Archivo .txt para problemas Steiner 37 Figura 32 Comparativa entre resultados continuos y enteros MST 44 Figura 33 Gráfica comparativa entre resultados continuos y enteros en Steiner 49 xvii 1 INTRODUCCIÓN Y OBJETIVO DEL TRABAJO En los últimos años, la demanda en comunicaciones de datos ha crecido exponencialmente por lo que se han necesitado nuevas y mejores alternativas o metodologías para dar solución a este tipo de problema. Debido a esto, el uso y la importancia de los grafos ha crecido exponencialmente también. Actualmente, el uso de grafos para la resolución de problemas es algo muy común debido a su versatilidad y efectividad. Como explicaremos más adelante, una red de grafos es un conjunto de nodos o vértices unidos por aristas o arcos. El objetivo a la hora de resolver cualquier problema de grafos es obtener una red (conjunto de aristas/arcos y nodos/vértices) que satisfaga mejor la función objetivo que se proponga en cada caso. En esta red, no suele ser necesario coger todas las aristas y todos los nodos, por lo que el problema será decidir qué nodos y qué aristas formarán parte de esta red. La estrategia que usaremos para resolver este problema de grafos es la estrategia propuesta por R.k. Martin de la cual no hemos encontrado ninguna experimentación. Esta estrategia se presentó aplicada al problema MST y nosotros la extenderemos para presentarla también al problema de Steiner. El problema MST lo resolveremos como caso particular de tipo p donde todos los nodos son terminales. En este trabajo, las funciones objetivo serán las proporcionadas por esos dos problemas, el MST (Minimun Spanning Tree), que consistirá en unir todos los nodos a mínimo costo, y por el problema de Steiner en la que uniremos a mínimo costo los nodos denominados como terminales. Esta estrategia propuesta por R.k. Martin consigue, además, que no se forme ningún ciclo en su interior, algo que suele crear ineficiencias y es mejor evitar. Por último, se hará un análisis experimental de los resultados comparándolos con otras formulaciones para ver así su eficiencia. Para realizar este trabajo, trabajaremos con esta formulación resolviendo una batería de problemas ya predefinida. Esto lo haremos creando un código en C++ para automatizar el proceso de construcción del problema y posteriormente resolveremos el problema en LINGO. En resumen, el objetivo del trabajo será resolver distintos problemas de grafos del tipo MST y steiner de forma óptima utilizando la formulación de R.k. Martin la cual evita ciclos y analizar los resultados y el tiempo de operación. Introducción a los grafos 2 2 2 INTRODUCCIÓN A LOS GRAFOS Definición de grafo Dentro de la rama de las ciencias, podemos definir un grafo como un conjunto de vertices o nodos que están unidos mediante aristas o arcos. La palabra grafo, viene de la palabra griega “grafos”, que significa dibujo. El objetivo de usar esta notación, es expresar las relaciones que tienen ciertas unidades de una manera gráfica y sencilla. Tan polivalente es el grafo, que prácticamente cualquier problema puede ser representado usando esta notación. Figura 1 Grafo Fuente: Elaboración propia En este ejemplo podemos observar de forma mas clara los componentes de un grafo. Todo grafo, podrá ser expresado como un par ordenado G = (V,E) donde ‘V’ representa el número de nodos que normalmente suele ser finito y ‘E’ el número de aristas Como podemos apreciar, este grafo tiene 6 nodos los cuales están unidos entre sí. Estas uniones pueden ser de dos tipos (aristas o arcos), lo que cambiaría el grafo completamente. Esto diferencia a los grafos en dirigidos y no dirigidos, de los cuales veremos sus particularidades a continuación. Tipos de grafos En este apartado vamos a estudiar las distintas tipologías de grafos que existen o al menos las más importantes. -Grafo simple: Este tipo de grafo tiene lugar cuando como mucho solo hay una arista de unión entre dos nodos. 3 Figura 2 Grafo simple Fuente: Elaboración propia -Multigrafo: También es conocido como grafo general. El grafo simple es una subclase de este grafo y este grafo ocurre cuando se permiten 2 aristas entre dos nodos. Estas aristas pueden llamarse en este caso lazo o múltiple. Figura 3 Multigrafo Fuente: Elaboración propia -Hipergrafo: Grafo en el cual las aristas tienen más de dos extremos, es decir, inciden sobre 2 o más vértices. -Grafo infinito: Grafo de cardinalidad 1 infinita -Grafo aleatorio: Grafo en el cual las aristas tienen unas probabilidades determinadas -Grafo plano: Grafo en el cual los nodos y aristas pueden representarse en dos dimensiones sin que haya ninguna intersección entre ellos. 1 Cardinalidad: Número de elementos de un conjunto Introducción a los grafos 4 4 Caracterización de grafos Podemos dividir a los grafos en dos grandes grupos. El primer grupo estará formado por los grafos no dirigidos. Para estos grafos, todos los pares posibles son no ordenados. Esto quiere decir por ejemplo, que si el grafo anterior fuera no dirigido cmpliría la siguiente propiedad {3,2}={2,3}. Ver en: Figura 1 Grafo A este tipo de uniones entre grafos no dirigidos se le llamará aristas. Por otro lado, tenemos los grafos no dirigidos los cuales son un poco más complejos. Figura 4 Grafo dirigido Fuente: Apuntes de Jose Manuel García En la “Figura 4 Grafo dirigido” podemos observar el cambio respecto al grafo dirigido. Este tipo de grafos tiene sus uniones direccionadas y por eso mismo se llamará dirigido. En este caso, remitiéndonos al ejemplo anterior, podremos afirmar que no tiene por qué cumplirse que {3,2}={2,3} aunque podría suceder perfectamente. A partir de ahora, cuando hablemos de las uniones de estos grafos no dirigidos, hablaremos sobre arcos. Figura 5 Grafo dirigido conexo Fuente: Apuntes de Jose Manuel García No en todos los grafos es necesario que todos los nodos estén conectados mediante arcos o aristas. Por lo tanto, diferenciaremos el grafo en el cual todos los nodos están unidos llamándolo “conexo”. 5 Figura 6 Grafo dirigido conexo acíclico Fuente: Apuntes de Jose Manuel García Por otro lado diferenciaremos tipos de grafos dependiendo de si sus cíclicos son acíclicos o no. En este caso, en la Figura 6 Grafo dirigido conexo acíclico podemos apreciar como es acíclico debido a que en ningún momento podríamos entrar en un bucle infinito. En el caso en el que se pudiera no sería acíclico. Este concepto lo explicaremos mejor en el apartado “Propiedades de un grafo”. Por ultimo, explicaremos la estructura de árbol que puede existir dentro de los grafos. Figura 7 Árbol GDA sin caminos cerrados Fuente: Apuntes de Jose Manuel García La estructura de árbol será una estructura muy importante para analizar en este TFG. Esta estructura evita que se pueda cualquier ningún ciclo dentro de su propia estructura. Por lo tanto la unión puede que adopte forma de árbol, algo que observaremos mejor en la siguiente imagen. Esta estructura puede evitar ineficiencias a la hora de resolver problemas por lo que suele ser preferible. Introducción a los grafos 6 6 Figura 8 Intree y Outtree Fuente: Apuntes de Jose Manuel García Como podemos observar en la Figura 8 Intree y Outtree podemos apreciar mejor esa forma de árbol de la que se ha hablado anteriormente. Dentro de la estructura de árbol que puede tomar un grafo podemos diferenciar dos tipos. Los “Intree” en los cuales cada nodo tiene a lo sumo un sucesor pudiendo así tener varios predecesores o la estructura “Outtree” en la cual cada trabajo tiene a lo sumo un precedesor y análogamente puede tener más de un sucesor. Si mezclamos ambas estructuras podemos llegar a tener un camino cerrado y tener ese riesgo de tener ineficiencias que es mejor evitar. Por lo tanto, habrá que tener cuidado si mezclamos ambas estructuras. Propiedades de un grafo En este apartado se verán las distintas propiedades que se cumplen cuando usamos la estructura de grafos. Adyacencia: Se dirá que dos aristas o arcos son adyacentes si hay un mismo vértice o nodo que une a ambas. 7 Figura 9 Adyacencia entre dos aristas Fuente: Elaboración propia Por ejemplo, como podemos ver en la “FIGURA 9”, la arista A y B son adyacentes debido a que hay un nodo que las une a ambas. -Ponderación: Para resolver los problemas de grafos es necesario definir los valores o pesos de los distintos actores que participan en dicho problema. Para ello se usarán las aristas, adjudicándoles su valor correspondiente para posteriormente resolver el problema. Por ejemplo en una de las muchas aplicaciones de los grafos, la red de carreteras, cada arista tiene el coste que supone ir por ese determinado camino. Las aplicaciones las estudiaremos más a fondo más adelante. -Incidencia: Esta propiedad se cumple cuando dos nodos están unidos mediante una arista. Básicamente, una arista solo puede incidir a dos vértices o nodos. -Etiquetado: Es una función que hace que podamos distinguir al nodo o a la arista que nosotros elijamos haciéndolos distintos al resto. -Ciclos: Se dirá que existe un ciclo cuando avanzando por una arista a través de un nodo inicial, se puede volver al mismo nodo inicial sin haber cruzado por una misma arista dos veces. La mayoría de los grafos contienen ciclos y suelen ser un verdadero problema cuando intentamos resolver un problema de este tipo ya que crean ineficiencias. Dentro de los tipos de ciclos podemos distinguir dos tipos. El primer tipo son los acíclicos que ocurre cuando existe una union entre tres nodos pero la dirección de los arcos evita que partiendo de una nodo inicial se vuelva a pasar por ese mismo nodo. Este tipo de grafo lo podemos observar más claramente en la Figura 6 Grafo dirigido conexo acíclico. El segundo tipo de ciclos se observa cuando sí podemos volver al nodo inicial partiendo de una arista y sin repetir ninguna de ellas por el camino como hemos comentado antes. Este ciclo es aún peor que el anterior debido a que además de ineficiencias puede crear bucles infinitos. Existe también el llamado ciclo Hamiltoniano que ocurre cuando podemos recorrer el grafo pasando por los vértices solo una vez excepto el vértice de inicio y fin que es el mismo. Cuando en cierto grafo cogemos una ruta determinada siendo esta una sucesión de vértices y de aristas la llamaremos camino de longitud n siendo n el conjunto de vértices que estén en el camino. Si todas sus aristas son distintas diremos que es simple y diremos que es cerrado si el vértice final= vértice inicial. En este caso podremos hablar igualmente de ciclo. Una trayectoria es un camino simple en el que todos sus vértices (salvo el final y el inicial en el caso de que sea un circuito cerrado) son distintos. En el caso en que la trayectoria sea cerrada como bien hemos dicho, la llamaremos circuito. Formulaciones 14 14 Se puede apreciar como realmente hemos obtenido el óptimo del problema. También como comentamos antes, podemos ver como no es el único óptimo posible en este problema ya que podríamos haber cogido perfectamente la otra arista de coste 1. En resumen, esta será la forma en que solucionemos los problemas de tipo MST, uniendo todos los nodos y a coste mínimo. Problema de Steiner en grafos Jakob Steiner fue un matemático suizo del Siglo XIX y uno de los más importantes geómetras de la historia. Esta representación de problemas adoptó este nombre en honor a él. La idea de esta representación es encontrar la ruta mínima entre dos nodos. Esta ruta mínima puede ser análogamente la ruta de más bajo coste, la ruta más rápida etcétera. Para el problema es necesario tener un grafo no dirigido G=(V,E) para el cual definiremos un conjunto N de nodos terminales N∈V y otro conjunto de nodos Steiner S∈V los cuales sirven de conexión entre los nodos terminales. La idea de este tipo de problema es conectar todos los nodos terminales a mínimo costo, pudiendo adoptar en la solución final tantos nodos Steiner como sea necesario para alcazar el óptimo. Generalmente, ya que cada arista supone un coste, cuantos menos nodos Steiner haya en nuestra solución final, menor será el coste final, pero no tiene por qué ser siempre así. A continuación veremos la representación de un problema donde los nodos rojos son los nodos terminales que hay que unir y los azules los steiner que podremos unir o no dependiendo de si nos hacen falta. Figura 15 Grafo problema de Steiner Fuente: Elaboración propia 15 Como podemos observar, tenemos distintas formas de unir todos los nodos terminales. Hay que decir que tal como hemos explicado anteriormente, la solución óptima probablemente adoptará una estructura de árbol por lo que será algo a tener en cuenta. A continuación, mostraré una solución válida de las muchas que hay que se ha elegido para este ejemplo. Figura 16 Solución grafo problema de Steiner Fuente: Elaboración propia Como Podemos observar, tenemos una solución factible, que no quiere decir que sea la óptima, puesto que hemos unido todos los nodos terminales y además hemos adoptado una estructura de árbol. Esto será algo a tener en cuenta en este TFG. Explicación del modelo matemático de R.k. Martin Este modelo fue propuesto por R.K. Martin y tiene como finalidad resolver problemas de grafos evitando cualquier tipo de ciclo, ya que como hemos comentado antes los ciclos hacen que el modelo sea ineficiente. Por lo que la solución de este modelo será un árbol. Tal como está puesto el modelo, resolvería el problema uniendo todos los nodos con una estructura de árbol, es decir, como si todos los nodos fueran terminales. Añadiendo unas restricciones, podemos hacer fácilmente que el problema pase a ser Steiner y que ya solo tenga que unir un número limitado de nodos terminales. Por lo tanto, primero explicaremos el modelo abstracto y posteriormente comprobaremos si es válido o no, y en el caso de que lo sea veremos su eficiencia. Formulaciones 16 16 Figura 17 Modelo matemático de R.K. Martin Fuente: Models and methods for Traffic Engineering problems with single-path routing. Tesis de Martim Joyce-Moniz. 3.4.1 Explicación de las variables y atributos del problema Antes de explicar el modelo, me gustaría aclarar varios conceptos. Primeramente, explicaré que quiere expresar cada variable/atributo. - 𝐶𝑒: Es un valor predefinido de la cantidad de flujo que pasa por la arista e, es decir, su coste. - 𝑛: Es el número de nodos que habrá en nuestra solución final. - 𝑊𝑒: Es una variable binaria que nos indica que la arista ij ha sido cogida para el modelo (We=1) o no (We = 0) - 𝑍𝑖 𝑗 𝑢: Es una variable binaria también que en este caso indica cuando su valor es 1, que el vértice k está en el lado del vértice j. - 𝑍𝑎 𝑢 : Es una variable binaria análoga a la anterior que hace referencia igualmente a los arcos. - N es el conjunto nodos, E es el conjunto aristas y A es el conjunto arcos. 17 Figura 18 Explicación de la variable Z Fuente: Elaboración propia Por ejemplo, en este caso, podemos apreciar como las aristas 𝑊𝑒1=1 y 𝑊𝑒2=1 (e1 es la arista 1-2 y e2 es la arista 2-3) y existe un pequeño árbol por lo que podría ser una solución válida. En este caso veremos que valores toman las variables 𝑍1 2 3 y 𝑍2 1 3. 𝑍2 1 3:0 // El vértice 3 debe estar unido al subíndice que colocaremos más a la derecha. Como 3 no está unido por el vértice 1, su valor es 0. 𝑍1 2 3::1// El vértice 3 si está unido en este caso por el lado del vértice 2 por lo que este si coge el valor 1. 3.4.2 Explicación de las restricciones Ahora procederé a explicar las restricciones del modelo matemático: - La función objetivo tratará de minimizar el flujo, el cual se calcula como un sumatorio de todas las aristas We por el flujo de cada una (Ce) el cual está predefinido. Estas aristas que entraran en el sumatorio son obviamente las pertenecientes a la red E que es con la que estamos operando. Por lo tanto, en la solución final se intentarán coger aristas que tengan poco flujo. - La restricción 1.1c nos indica que los nodos o aristas que adoptemos en nuestra solución deberán ser un número inferior a las aristas que entren en la misma. Esto es debido a que, en un árbol, para unir todos los nodos, necesitamos solo y exclusivamente una arista menos que los nodos totales. Formulaciones 18 18 Figura 19 Explicación gráfica de la restricción 1.1c Fuente: Elaboración propia Como podemos apreciar, realmente en un grafo de 5 nodos solo necesitamos 4 aristas para poder unirlos a todos. - La restricción 1.8c expresa que para toda arista We cogida en nuestra solución, debe tener una de las dos siguientes variables ( 𝑍𝑖 𝑗 𝑢 o 𝑍𝑗 𝑖 𝑢 ) el valor 1 obligatoriamente para todos los nodos pertenecientes a la red N que son los que queremos incluir en nuestra solución. Esto es debido a que si tuviesen valor 0 las dos variables Z es porque hay un nodo u que no está conectado y debería estarlo y de la misma manera, si las dos toman el valor 1 es porque hay un error ya que no es necesario coger dos mismos arcos a la vez. Por lo tanto, para incluir todos los nodos pertenecientes a N, decimos que uno de esos dos valores debe ser 1. - La restricción 1.8a nos indica que a un solo nodo ‘u’ solo se puede llegar como mucho mediante un arco cuando fijamos otro nodo cualquiera. En un ejemplo generalizador, en el caso (𝑍𝑎 𝑢) fijaremos el nodo u y uno de los dos extremos de a ( en este caso el inicial) y diremos que ese sumatorio de arcos deberá ser menor que 1. También, los nodos que fijaremos no pueden ser iguales. - La restricción 1.8b nos expresa que cuando fijamos un nodo ‘u’ en un arco cualquiera 𝑍𝑎 𝑢 , si fijamos el nodo inicial del arco i como el mismo que ‘u’, este valor será <=0, ya que si fuese mayor existiría algún ciclo porque se podría llegar al nodo en cuestión por dos caminos distintos. Como la restricción 1.8a es un poco más difícil de comprender, la explicare también gráficamente a continuación. 19 Figura 20 Explicación de la restricción 1.8a. Fuente: Elaboración propia Mirando este caso en el cual he adoptado una posible solución valida para un problema de 5 nodos, intentaremos explicar el sentido de la restricción 1.8a. Por ejemplo, en este caso, fijaremos el nodo ‘u’ de 𝑍𝑎 𝑢 como el nodo 3. Por otro lado, fijaremos el nodo 5 como el nodo inicial. El sumatorio de los arcos 𝑍5 𝑥 3 donde x representa los números 1,2 y 4 deberá ser menor o igual que 1. En efecto, el valor del sumatorio sería 1 ya que el único que se activa es el arco 𝑍5 4 3. Por otro lado, vamos a comprobar que pasaría si cogemos como nodo inicial el nodo 2 fijando como nodo ‘u’ el nodo 3 de nuevo. En este caso, el sumatorio de los arcos 𝑍2 𝑥 3 donde x es 1,4 y 5 es 0. Por lo tanto, el modelo no necesariamente tiene que dar 1 en todo sumatorio de la restricción 1.8a, ya que como acabamos de ver, ha dado 0 en este caso y tenemos una estructura en forma de árbol conexo correcta. Por ello pondremos que deberá ser <=1. Formulaciones 20 20 Otras formulaciones En este apartado explicaremos distintas formulaciones que existen para resolver el mismo problema. Posteriormente, compararemos los resultados obtenidos de estos modelos con la formulación de R.k. Martin. 3.5.1 Formulación de Miller, Tucker y Zennit Para explicar este modelo, primero explicaremos primero las variables del mismo: - Llamaremos N al conjunto de nodos del grafo - Llamamos A al conjunto de aristas del grafo. - Cj: es el valor del coste asignado a la arista “j”. - Xi: es el valor del nivel del nodo “i”. - Ri: es una variable binaria tal que el primer nodo que vayamos a poner en nuestro árbol tenga valor 1 y los otros tengan valor 0. Esto es para diferenciar los nodos, ya el primer nodo que pongamos no va a tener nodo padre, por lo que va a tener que cumplir otro tipo de condiciones que los nodos que tienen padre. - Origenj: es el número del nodo origen de la arista “j”. - Destinoj: es el número del nodo destino de la arista “j”. Posteriormente, la variable de decisión: - αj: Es la única variable de decisión que tendremos en este modelo, tendrá un valor binario, valdrá uno cuando se seleccione ese arco como parte de la solución y cero cuando no. Por último, explicaremos las restricciones del mismo: - ∑αj ∀j/Destinoj=i =1 ∀i/Ri=0 Esta primera restricción sirve para asegurar que cada nodo que no sea raíz tiene nodo padre, asegurando que es el nodo destino de algún otro nodo - ∑αj ∀j/Origenj=i ≥1 ∀i/Ri=1 La segunda restricción obliga a todos los nodos raíz ser padre de al menos un nodo. 21 - −𝑥𝑂𝑟𝑖𝑔𝑒𝑛𝑗 +𝑥𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 +(𝑁 −1)∗αj ≤ N − 2 , ∀j/𝑅𝑂𝑟𝑖𝑔𝑒𝑛𝑗 = 0,𝑅𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 = 0 Con esta tercera restricción, imponemos que el nivel del nodo padre debe ser siempre mayor que el nodo hijo para así evitar bucles. - 𝑥𝑂𝑟𝑖𝑔𝑒𝑛𝑗 ≥ 1 , ∀j/𝑅𝑂𝑟𝑖𝑔𝑒𝑛𝑗 = 0 La cuarta restricción en cambio nos dice que un nodo que no sea raíz tiene que tener un nivel mayor o igual a uno. Ya que el único nodo que tendrá nivel cero será el nodo raíz. - 𝑥𝑂𝑟𝑖𝑔𝑒𝑛𝑗 ≤ 𝑁 −1 , ∀j/𝑅𝑂𝑟𝑖𝑔𝑒𝑛𝑗 = 0 La quinta restricción nos dice que el nivel de un nodo que no sea padre tiene que ser menor que el número de nodos menos uno. Esto es debido a que, si ponemos todos los nodos en fila, no podríamos superar nunca ese nivel. - αj∈[0,1] , ∀j ∈ A La sexta restricción sirve para imponer que nuestra variable de decisión tiene que tomar un valor binario. Función objetivo: La función objetivo lo que busca es minimizar el coste de las aristas que pertenecen a la solución, siendo αj nuestra variable de decisión. - Min Ʃ Cj * αj , ∀j ∈ A 3.5.2 Formulación de Derroche Laporte Esta formulación solo tiene un pequeño cambio respecto a la formulación anterior y es la tercera restricción, que es la referida a los niveles y a los ciclos. Esta se sustituye por estas otras dos restricciones: - −𝑥𝑂𝑟𝑖𝑔𝑒𝑛𝑗 +𝑥𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 +(𝑁 −1)∗αj+(N−3)∗ α𝑗+(𝐴 2) ≤ N − 2 ∀j/𝑗 ≤ (𝐴 2),𝑅𝑂𝑟𝑖𝑔𝑒𝑛𝑗 = 0,𝑅𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 = 0 Formulaciones 22 22 - −𝑥𝑂𝑟𝑖𝑔𝑒𝑛𝑗 +𝑥𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 +(𝑁 −1)∗αj+(N−3)∗ α𝑗−(𝐴 2) ≤ N − 2 ∀j/𝑗 > (𝐴 2)+1,𝑅𝑂𝑟𝑖𝑔𝑒𝑛𝑗 = 0,𝑅𝐷𝑒𝑠𝑡𝑖𝑛𝑜𝑗 = 0 Básicamente imponen lo mismo, que el nivel del nodo padre debe ser mayor al nivel del nodo hijo. Estas dos formulaciones anteriores las compararemos con la formulación de R.k Martin para ver así la eficiencia de ambas. 3.5.3 Estrategia de flujo multiple Aquí vamos a describir la estrategia de flujo multiple, que es otra forma distinta de resolver este tipo de problemas. Primeramente vamos a ver las variables de este problema, que son las siguientes: - N representa el conjunto de nodos. - A es el conjunto de arcos. - Ti es una variable binaria que vale 1 si el nodo es terminal. - R es una variable que diferencia al nodo raíz. - Cij es el coste de cada arco. A continuación, veremos las variables de decision. - αij sería 1 si el arco en cuestión se selecciona y vale 0 si no. Por ultimo explicaremos las restricciones: 1) ∑ 𝑋𝑖𝑘 = ∑ 𝑋𝑗𝑖 − 1 𝑗𝑘 ,∀𝑖/𝑖 ≠ 𝑟,𝑇𝑖 = 1 2) ∑ 𝑋𝑘𝑖 = ∑ 𝑋𝑖𝑗 𝑗𝑘 ,∀𝑖/ 𝑇𝑖 = 0 3) 𝑋𝑖𝑗 ≤ 𝐶𝑆 ∗ 𝛼𝑖𝑗 ,∀(𝑖,𝑗) ∈ 𝐴 4) 𝑋𝑗𝑖 ≤ 𝐶𝑆 ∗ 𝛼𝑖𝑗 ,∀(𝑗,𝑖) ∈ 𝐴 5) ∑ 𝑋𝑟𝑗 𝑗 = 𝐶𝑆 6) (∑ 𝑇𝑖) − 1 = 𝐶𝑆 𝑁 𝑖=0 ,∀𝑖/𝑖 ∈ 𝑁 7) 𝛼𝑖𝑗 ∈ [0,1] ,∀(𝑖,𝑗) ∈ 𝐴 La primera restricción explica que para cualquier nodo terminal, el flujo que sale debe ser el que entra menos una unidad, es decir, cada nodo terminal se quedará con una unidad de flujo. La segunda indica que en los nodos steiner el flujo que entra es el mismo que el que sale. La tercera y la cuarta restringen el flujo que puede pasar por un determinado arco a una cota superior. 23 Esto es para que no pase más flujo por cualquier arco del que ha enviado el nodo raíz. La quinta fija la cota superior como el flujo que manda el nodo raíz. La sexta define la cota superior como el número de nodos menos uno. La séptima define a la variable alfa como binaria. Por ultimo la función objetivo es la siguiente: ∑ 𝑪𝒊𝒋 ∗𝜶𝒊𝒋 (𝒊,𝒋)∈𝑨 Lo que hace es minimizar el coste total de transporter una unidad de flujo por el camino obtenido como solución. 3.5.4 Estrategia de flujo simple La variables del problema y variables de flujo serían las mismas que en la estrategia que el flujo multiple. Las diferencias se pueden apreciar en las restricciones que serían las siguientes: 1) ∑ (𝑥𝑖𝑗 𝑘 − 𝑥𝑗𝑖 𝑘 𝑗:(𝑖,𝑗)∈𝐴 ) = 0 ,∀𝑗 ≠ {𝑘,𝑟},∀𝑘 ≠ 𝑟/𝑇𝑘 = 1 2) ∑ 𝑥𝑟𝑗 𝑘 𝑗:(𝑟,𝑗)∈𝐴 = 1 ,∀𝑗 = 𝑟/𝑗 ≠ 𝑘,∀𝑘 ≠ 𝑟/𝑇𝑘 = 1 3) 𝑥𝑖𝑗 𝑘 ≤ 𝛼𝑖𝑗 ,∀(𝑖,𝑗),∀𝑘 ≠ 𝑟/𝑇𝑘 = 1 4) 𝑥𝑗𝑖 𝑘 ≤ 𝛼𝑖𝑗 ,∀(𝑖,𝑗),∀𝑘 ≠ 𝑟/𝑇𝑘 = 1 5) 𝑥𝑖𝑗 𝑘 ∈ {0,1} ,∀(𝑖,𝑘)/𝑇𝑘 = 1,∀𝑗 ∈ 𝑁 6) 𝛼𝑖𝑗 ∈ [0,1] ,∀(𝑖,𝑗) ∈ 𝐴 La primera restricción vuelve a indicar lo mismo que en el caso múltiple, el flujo total que llega desde todos los nodos conectados con I pasando por k debe ser el mismo que sale desde I hacia el resto de los nodos conectados, pasando siempre por k. Lo que llega es igual a lo que sale. La segunda refleja que cada nodo raíz debe mandar una unidad de flujo a cada nodo terminal. La tercera y la cuarta expresan que el flujo que pasa por cada arco debe ser menor o igual a uno. La quinta nos indica que el flujo que pasa por cada arco debe estar entre cero y uno. La sexta fija el alfa como una variable binaria. Estas dos formulaciones de flujo solo las nombraremos pero no trabajaremos con ella en la parte de análisis de resultados, ya que sus resultados se comprobaron en el pasado y no fueron muy buenos. LINGO 30 30 Figura 24 Datos ejemplo LINGO Fuente: Elaboración propia (LINGO) Para entender mejor este pequeño ejemplo, he dibujado el grafo el cual quedaría de la siguiente forma: Figura 25 Grafo de los datos del ejemplo Fuente: Elaboración propia 31 Como podemos apreciar, tenemos 5 nodos y 10 posibles aristas de las cuales solo podremos coger 4 de ellas. Para este modelo, he escrito el número del nodo en color amarillo en el interior del mismo, y el coste de la arista en un tono violeta al lado de la misma arista. El coste óptimo sería el que saldría de coger las 4 con menos coste, pero no siempre es posible. En este ejemplo, veremos que solución nos sale cuando resolvemos el problema. Lo que haremos a continuación, será transcribir el modelo matemático a lenguaje LINGO y posteriormente veremos si verdaderamente este modelo funciona. Para ello, solucionaremos el modelo a mano ya que su tamaño es reducido y veremos si las soluciones son las mismas Una vez escrito el modelo en lenguaje LINGO, quedaría de la siguiente forma: Figura 26 Modelo de R.k. Martin en LINGO Fuente: Elaboración propia (LINGO) Este modelo de esa manera compila, así que solo habrá que comprobar si puede también encontrar el óptimo. Para que se pueda ver mejor, escribiré el modelo directamente en el Word también. El modelo que he plasmado en una captura antes es el siguiente: MIN=@SUM(Aristas(z):Coste(z)*X(z)); @SUM(Aristas(z):X(z))=NUM-1; @FOR(Aristas(z):@FOR(ARCOS(i)|NO(i)#EQ#N1(z) #AND# ND(i)#EQ#N2(z): @FOR(ARCOS(j)|NO(j)#EQ#N2(z)#AND#ND(j)#EQ#N1(z): @FOR(Nodos(k): X(z)=Y(i,k)+ Y(j,k) )))); @FOR(Nodos(k):@FOR(Nodos(i)|i#NE#k: @SUM(Arcos(j)|NO(j)#EQ#i: y(j,k)) <= 1)); @FOR(Nodos(k): @SUM(Arcos(i)|NO(i)#EQ#k : y(i,k)) <= 0); @FOR(Aristas(j):@BIn(x(j))); END Una vez compilamos el modelo y vemos los resultados vemos que sale lo siguiente: LINGO 32 32 Figura 27 Solución del modelo. Fuente: Elaboración propia (LINGO) Como se puede apreciar, este modelo ha encontrado una solución de valor 10 en la cual une el nodo 1 con el resto de nodos por lo que a priori es válida ya que forma un árbol conexo. Se realizan 13 iteraciones, lo que podría ser mejorable para un modelo tan pequeño. Aún así, ha encontrado la solución al instante. A continuación, veremos si gráficamente podemos encontrar la misma solución que se ha encontrado con estos dos modelos. Para ello cogeremos el árbol que menor función objetivo tenga quedando la siguiente solución: 33 Figura 28 Solución gráfica del modelo Fuente: Elaboración propia En efecto, gráficamente podemos observar como en el óptimo se encuentran las 4 aristas que unen al nodo 1 con el resto de nodos y que la suma de sus costes hace un total de 10. No se puede encontrar una solución mejor puesto que son los costes más bajos y además el grafo final está formando un árbol, por lo que podemos afirmar que nuestros modelos han encontrado la solución óptima correctamente. Por lo tanto, daremos válido el modelo de momento. Este mismo modelo se usará con grafos mucho más grandes y comprobaremos si sigue encontrando la mejor solución. Conversión con C a LINGO Los datos de los problemas que resolveremos proceden de archivos de texto(.txt) que tienen la siguiente estructura: LINGO 34 34 Figura 29 Estructura de los problemas en .txt Fuente: Elaboración propia Todos los problemas que resolvamos nos vendrán dados con esa estructura. El primer número que aparece son los nodos que hay. Por lo tanto en las dos primeras columnas veremos todos los números desde el 1 hasta el número de nodos que haya, ya que tiene que haber mínimo una unión disponible por cada uno. El Segundo número, son los arcos disponibles en el problema en cuestión. Tiene relación también con la cantidad de filas que habrá. La primera columna de los números por debajo del número de nodos y de aristas expresa el nodo de inicio del arco, y la segunda columna el nodo final del arco. Por último, la tercera columna expresa el coste de ese arco en cuestión. Con esa estructura, trataremos de resolver los problemas que se nos planteen. En principio, este trabajo constará de 38 problemas distintos con la misma estructura. Para ello, nuestro primer paso será resolverlo teniendo en cuenta que todos los nodos son terminales. Es decir, trataremos de unir todos los nodos al mínimo coste. Para ello, hemos creado un código en C con el que automatizaremos el proceso de leer datos del archivo de texto y convertirlo en formato LINGO. Este código está adjuntado como anexo 1 al final del mismo trabajo. Aquí adjuntaremos a continuación un diagrama de flujo en el que se puede visualizar qué hace el código exactamente. 35 Figura 30 Diagrama de flujo del código en C Fuente: Elaboración propia (BIZAGI) Posteriormente, ese código nos crearía un archivo LINGO con la siguiente estructura, listo para ser compilado: LINGO 36 36 MODEL: SETS: Nodos/1.. 45/; Aristas/1.. 87/:X,N1,N2,Coste; Arcos/1.. 174/:NO,ND; Triple(Arcos,Nodos) :Y; ENDSETS DATA: Coste= 8 8 8 8 10 3 10 4 5 6 9 7 9 4 1 6 6 3 7 3 4 2 5 8 7 6 2 6 4 7 1 10 1 6 7 10 6 9 6 3 4 10 5 5 7 6 10 1 5 10 4 4 3 2 1 3 9 5 8 7 6 3 2 10 1 7 1 7 2 5 1 6 8 2 6 7 4 9 9 5 10 5 1 6 1 1 6 ; N1= 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 6 7 7 7 8 8 9 10 11 11 12 13 14 15 16 18 20 20 20 20 20 22 22 23 23 24 24 25 26 26 26 26 26 26 27 28 29 29 30 30 30 30 30 31 31 32 34 34 35 35 36 36 36 37 37 37 38 39 39 39 39 40 40 40 43 44 44 44 45 45 ; N2= 10 25 29 4 9 28 32 22 27 43 6 8 25 32 12 21 25 12 4 6 12 5 16 37 17 3 35 33 24 31 13 14 22 2 11 24 36 42 32 37 3 4 5 44 40 1 10 20 30 33 45 42 19 34 39 5 9 14 19 36 21 39 15 9 33 12 31 9 13 17 28 30 41 27 7 18 23 36 7 17 33 15 11 15 38 4 41 ; NO= 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 6 7 7 7 8 8 9 10 11 11 12 13 14 15 16 18 20 20 20 20 20 22 22 23 23 24 24 25 26 26 26 26 26 26 27 28 29 29 30 30 30 30 30 31 31 32 34 34 35 35 36 36 36 37 37 37 38 39 39 39 39 40 40 40 43 44 44 44 45 45 10 25 29 4 9 28 32 22 27 43 6 8 25 32 12 21 25 12 4 6 12 5 16 37 17 3 35 33 24 31 13 14 22 2 11 24 36 42 32 37 3 4 5 44 40 1 10 20 30 33 45 42 19 34 39 5 9 14 19 36 21 39 15 9 33 12 31 9 13 17 28 30 41 27 7 18 23 36 7 17 33 15 11 15 38 4 41 ; ND= 10 25 29 4 9 28 32 22 27 43 6 8 25 32 12 21 25 12 4 6 12 5 16 37 17 3 35 33 24 31 13 14 22 2 11 24 36 42 32 37 3 4 5 44 40 1 10 20 30 33 45 42 19 34 39 5 9 14 19 36 21 39 15 9 33 12 31 9 13 17 28 30 41 27 7 18 23 36 7 17 33 15 11 15 38 4 41 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 6 7 7 7 8 8 9 10 11 11 12 13 14 15 16 18 20 20 20 20 20 22 22 23 23 24 24 25 26 26 26 26 26 26 27 28 29 29 30 30 30 30 30 31 31 32 34 34 35 35 36 36 36 37 37 37 38 39 39 39 39 40 40 40 43 44 44 44 45 45 ; NUM = 45 ; ENDDATA MIN=@SUM(Aristas(z):Coste(z)*X(z)); @SUM(Aristas(z):X(z))=NUM-1; @FOR(Aristas(z):@FOR(ARCOS(i)|NO(i)#EQ#N1(z) #AND# ND(i)#EQ#N2(z): @FOR(ARCOS(j)|NO(j)#EQ#N2(z)#AND#ND(j)#EQ#N1(z): @FOR(Nodos(k): X(z)=Y(i,k)+ Y(j,k) )))); @FOR(Nodos(k):@FOR(Nodos(i)|i#NE#k: @SUM(Arcos(j)|NO(j)#EQ#i: y(j,k)) <= 1)); @FOR(Nodos(k): @SUM(Arcos(i)|NO(i)#EQ#k : y(i,k)) <= 0); @FOR(Aristas(j):@BIn(x(j))); END Conversión con C a LINGO (Steiner) Para este apartado, el archivo .txt que se cogerá será el mismo que el de antes. Sin embargo, se leerá de forma distinta. En el archivo .txt anterior no se leía el final del archivo que es lo referido a Steiner. Para ponernos en contexto, pondré un ejemplo a continuación: 37 Figura 31 Archivo .txt para problemas Steiner Fuente: Elaboración propia Como podemos percibir, el archivo tiene exactamente la misma estructura inicial. Como se explicó antes, el primer número hace referencia al número de nodos, el segundo al número de aristas y luego de 3 en 3 se hace referencia al nodo inicial, nodo final y coste de la arista respectivamente. La diferencia que existe es que ahora trataremos con más datos que estarán al final del mismo .txt de los cuales antes no se dijo nada. Estos datos los hemos marcado con los números 1, 2 y 3 en la “Figura 31 Archivo .txt para problemas Steiner”, los cuales explicaremos a continuación. 1.- El primer dato hace referencia al número de nodos terminales que habrá. Estos serán los nodos que haya que coger obligatoriamente. 2.- Te dice qué nodos son los terminales. 3.- Es un número que hay que sumar a la solución final del modelo. Con estos nuevos datos, nos dispondremos a resolver el modelo. Para ello crearemos un programa en C que nos automatice el proceso el cual al igual que el anterior, adjuntare al final del trabajo. LINGO 38 38 Una vez hecho el programa nos saldrán modelos con la siguiente estructura: MODEL: SETS: Nodos/1.. 22/:TR,alfa; Aristas/1.. 33/:X,N1,N2,Coste; Arcos/1.. 66/:NO,ND; Triple(Arcos,Nodos) :Y; ENDSETS DATA: Coste= 4 1 7 5 7 8 9 10 2 9 7 2 1 9 13 3 9 8 17 15 15 5 7 16 5 10 10 6 4 3 6 6 7; N1= 1 2 3 5 7 8 9 10 10 11 12 13 13 14 14 15 15 15 3 10 16 17 17 13 18 18 18 19 19 20 20 14 6; N2= 21 4 22 1 16 12 22 18 19 2 5 8 22 17 10 6 7 14 12 12 9 11 2 4 3 20 9 13 15 4 11 21 1; NO= 1 2 3 5 7 8 9 10 10 11 12 13 13 14 14 15 15 15 3 10 16 17 17 13 18 18 18 19 19 20 20 14 6 21 4 22 1 16 12 22 18 19 2 5 8 22 17 10 6 7 14 12 12 9 11 2 4 3 20 9 13 15 4 11 21 1; ND= 21 4 22 1 16 12 22 18 19 2 5 8 22 17 10 6 7 14 12 12 9 11 2 4 3 20 9 13 15 4 11 21 1 1 2 3 5 7 8 9 10 10 11 12 13 13 14 14 15 15 15 3 10 16 17 17 13 18 18 18 19 19 20 20 14 6; TR= 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0; M= 37; ENDDATA MIN=@SUM(Aristas(z):Coste(z)*X(z))+M; @FOR(Nodos(k)|TR(k)#EQ#1: Alfa(k)=1); @SUM(Nodos(k):alfa(k))=@SUM(aristas(z):X(z))+1; @FOR(Aristas(z):@FOR(ARCOS(i)|NO(i)#EQ#N1(z) #AND# ND(i)#EQ#N2(z): @FOR(ARCOS(j)|NO(j)#EQ#N2(z)#AND#ND(j)#EQ#N1(z): @FOR(Nodos(k): X(z)=Y(i,k)+ Y(j,k) )))); @FOR(Nodos(k):@FOR(Nodos(i)|i#NE#k: @SUM(Arcos(j)|NO(j)#EQ#i: y(j,k)) <= 1)); @FOR(Nodos(k):@SUM(Arcos(i)|NO(i)#EQ#k : y(i,k)) <= 0); @FOR(Nodos(k)|TR(k)#EQ#0: @FOR(Aristas(z)|k#EQ#N1(z):X(z)<=alfa(k))); @FOR(Nodos(k)|TR(k)#EQ#0: @FOR(Aristas(z)|k#EQ#N2(z):X(z)<=alfa(k))); @FOR(Aristas(j):@BIn(x(j))); @FOR(Nodos(k):@BIN(alfa(k))); END Se puede apreciar que la estructura ha cambiado notablemente, y es que se han añadido más datos y restricciones los cuales explicaremos a continuación. Se crea el atributo del nodo terminal como TR, que es un nodo el cual tiene que pertenecer al modelo obligatoriamente. Por ello mismo valdrá 1 si es terminal y 0 si no. También se crea la variable alfa que es 1 si el nodo pertenece a la red de nodos de la solución y 0 si no. Por ultimo, antes de pasar a las restricciones, también se añade el valor M que es un valor que hay que sumar a la solución que nos de el problema para llegar a la verdadera solución. Ya dentro de las restricciones los cambios que hay son los siguientes: 39 1.- Se añade el valor M sumando en la función objetivo. 2.- Como ahora no participan en la solución todos los nodos, el sumatorio de los alfa será igual al número de aristas+1. Recordamos que para unir todos los nodos necesitamos una arista menos que el total de nodos. 3.- En las dos siguientes restricciones que volveré a copiar a continuación se consigue que si cogemos una arista, automáticamente tenemos que coger si o sí los dos nodos de los extremos de la misma. @FOR(Nodos(k)|TR(k)#EQ#0: @FOR(Aristas(z)|k#EQ#N1(z):X(z)<=alfa(k))); @FOR(Nodos(k)|TR(k)#EQ#0: @FOR(Aristas(z)|k#EQ#N2(z):X(z)<=alfa(k))); Esto se consigue diciendo que alfa tiene que ser mayor o igual, debido a que si la arista vale 1, entonces alfa obligatoriamente debe tomar el valor de 1 también. 4.- Por ultimo, se especifica que alfa tiene que ser una variable binaria también. El diagrama de flujo que explica el proceso es similar al diagrama de flujo expuesto anteriormente. Como bien hemos comentado anteriormente, solo varía en unas restricciones que hay que añadir al modelo. EXPERIMENTACIÓN 46 46 En efecto, la formulación consigue alcanzar el óptimo en cada problema. Para crear esta tabla, hemos agrupado los distintos problemas en filas y los datos en columnas. Hemos tenido en cuenta el tiempo de realización del ejercicio, que será mejor cuanto menor tiempo tarde, la función objetivo que trataremos de minimizar, el número de restricciones, el número de variables, las iteraciones que también es deseable que sea un número de tamaño reducido y la memoria usada. A la hora de ver los resultados, podemos ver como estos problemas están ordenados por complejidad, siendo el más fácil de resolver el primero y el más complejo el último. También se puede apreciar como en el problema 5 comienza ya a crecer exponencialmente a tiempos superiores a 2 horas, algo que veremos reflejado posteriormente. Seguidamente, se intentó resolver más problemas de los cuales su resultado fue el siguiente: Tabla 6 Problemas no resueltos modelo entero TIEMPO F.O. Nº restricciones Nº variables Iteraciones Memoria usada steinc6 16:14:54 1729 440300 613521 504848 110968 steinc7 1:00:52 1771 478369 664222 202846 120242 steinc8 1:03:10 1669 485300 671925 193292 121735 steinc9 1:28:22 1997 552180 755811 235940 137364 steinc10 1:08:38 1986 562788 761805 217763 138908 steinc11 0:05:27 0 1249498 2002995 0 RAN OUT steinc12 0:05:57 0 1279438 2062935 0 RAN OUT steinc13 0:05:49 0 1256954 2019922 0 RAN OUT steinc14 0:05:49 0 1231035 1966032 0 RAN OUT steinc15 0:04:54 0 1157502 1816815 0 RAN OUT steinc16 0:00:17 0 1136003 3545137 0 RAN OUT steinc17 0:00:17 0 1093003 3490705 0 RAN OUT steinc18 0:00:16 0 1150503 3523969 0 RAN OUT steinc19 0:02:33 0 1811031 3378817 0 RAN OUT steinc20 0:00:00 0 0 100000 0 RAN OUT Fuente: Elaboración propia 47 El problema steinc6 vuelve a aumentar la complejidad del mismo añadiendo más restricciones y variables y se puede ver como ni en 16 horas se consigue resolver. A partir de este hecho, se opta por dejar los problemas resolviéndose como mucho 1 hora. Por otro lado, a partir del steinc11, en el cual vuelve a aumentar la complejidad, ni siquiera LINGO es capaz de intentar resolverlo ya que el mismo programa falla debido a lo grande que es dicho problema. Esto era algo que suponíamos ya que en la forma continua nos dio fallos también. En el último caso (steinc20), directamente da error al segundo 0. Por esto, solo nos centraremos a la hora de analizar los resultados en los problemas que se han podido resolver o que no se han resuelto por falta de tiempo (sin haber dado error) y quitaremos de nuestro análisis los problemas a partir del steinc11, ya que ni hemos podido operar con ellos. Por último, cabe destacar que, aunque los tiempos sean muy altos, se consigue llegar al mismo óptimo en los dos modelos. Por lo tanto, se puede ver que la forma continua, que es la “lower bound” encuentra soluciones bastante buenas. Resultados de los problemas Steiner (continua) Aquí evaluaremos la forma continua de la formulación en el problema steiner. Recordamos que la forma continua lo que busca es la lower bound, que es la cota inferior y se suele usar como punto de partida. Para conseguir transformar el problema en un problema steiner, es necesario quitar las siguientes dos restricciones: @FOR(Aristas(j):@BIn(x(j))); @FOR(Nodos(k):@BIN(alfa(k))); Estas dos restricciones hacen que las variables alfa y x solo puedan adaptar valores binarios por lo que si las quitamos, ampliaremos el arco de soluciones además de que aumentará la velocidad de búsqueda. Una vez resuelto todos los problemas, agrupamos los datos en una tabla similar al modelo continuo anterior donde solo detallábamos el tiempo y el valor de la función objetivo. Tabla 7 Resultados modelo Steiner continuo F.O. TIEMPO Steinb1 79,5 0:00:00 Steinb2 83 0:00:00 Steinb3 138 0:00:00 Steinb4 53,7 0:00:00 Steinb5 50,5 0:00:00 Steinb6 119,024 0:00:01 Steinb7 111 0:00:00 Steinb8 98,375 0:00:00 EXPERIMENTACIÓN 48 48 Steinb9 220 0:00:00 Steinb10 80,25 0:00:01 Steinb11 81,7778 0:00:03 Steinb12 167,679 0:00:06 Steinb13 159,4 0:00:00 Steinb14 230 0:00:00 Steinb15 309,5 0:00:01 Steinb16 108,568 0:00:11 Steinb17 122,929 0:00:08 Steinb18 200 0:00:28 steinc1 76,4667 0:01:01 steinc2 115,833 0:01:05 steinc3 727,241 0:08:19 steinc4 - 1:04:14 steinc5 - 1:31:42 Fuente: Elaboración propia Los problemas en general se resuelven bastante rápido como era de esperar, aunque a partir del “steinc4” estos se complican y tardan más de 1 hora en resolverse. Haciendo una gráfica comparativa viendo los resultados obtenidos con la formulación continua con los óptimos que recordamos que disponemos de ellos desde el principio, obtendríamos lo siguiente: 49 Figura 33 Gráfica comparativa entre resultados continuos y enteros en Steiner Fuente: Elaboración propia Como podemos apreciar, la formulación continua a pesar de no alcanzar el óptimo en la mayoría de problemas, se acerca muchísimo. Aquí se puede ver mejor como la “lower bound” que alcanza esta formulación es realmente buena. Resultados de los problemas Steiner Igual que en la tabla que analizaba el MST, volvemos a tomar nota de las variables, restricciones, iteraciones y memoria usada además de la función objetivo y del tiempo que tarda. Tabla 8 Resultados modelo Steiner entero TIEMPO F.O. Nº restricciones Nº variables Iteraciones Memoria usada Steinb1 0:00:01 82 436 518 526 119 Steinb2 0:00:00 83 557 655 397 147 Steinb3 0:00:00 138 917 1030 888 225 Steinb4 0:00:45 59 4934 6511 89770 1251 EXPERIMENTACIÓN 50 50 Steinb5 0:00:26 61 4763 6347 28610 1218 Steinb6 0:00:12 122 6033 7937 13826 1513 Steinb7 0:00:00 111 1248 1496 565 310 Steinb8 0:00:00 104 1703 2025 1101 416 Steinb9 0:00:00 220 1690 1929 933 401 Steinb10 0:02:26 86 9868 13473 468689 2517 Steinb11 0:03:05 88 12287 16427 873907 3076 Steinb12 0:02:54 174 11958 15902 322291 2984 Steinb13 0:00:13 165 3392 4110 13476 817 Steinb14 0:00:44 235 4570 5546 61451 1092 Steinb15 0:00:23 318 5653 6703 48072 1323 Steinb16 1:04:02 172 18982 25790 7446644 4784 Steinb17 0:10:02 131 17026 22848 862188 4255 Steinb18 0:08:53 218 20499 27427 507083 5106 steinc1 0:11:28 85 58137 74758 3105105 13956 steinc2 1:00:54 153 46775 60256 11271224 11258 steinc3 3:26:33 813 84567 105418 2847760 19834 steinc4 1:01:10 1104 98196 121609 1722308 22922 steinc5 1:16:00 - 125924 152470 1004186 28919 steinc6 7:48:12 - 441947 613882 1606965 111206 steinc7 1:00:05 - 480057 664595 127241 120488 steinc8 3:48:46 - 486719 672233 837572 121956 steinc9 1:09:39 - 553501 756105 424823 137582 steinc10 1:05:55 - 563622 761990 371762 139080 Fuente: Elaboración propia 51 Podemos ver que el modelo es correcto ya que ecuentra el óptimo. Sin embargo sigue siendo lento. Era de esperar pues este tendría características parecidas al modelo entero. En rojo están los problemas de los cuales no hemos podido hayar el óptimo por falta de tiempo ya que hemos puesto 1 hora como límite. En los primeros problemas sin solucionar al menos encontro una solución del problema. En los últimos se puede ver que aunque hayan pasado casi 8 horas, no consigue encontrar nada. En este caso se intenta resolver hasta el steinc10 sin suerte, ya que el único que consigue resolver en menos de una hora es el primero. También se puede ver que aunque las cotas inferiores no sean todas las mismas que la solución como en el caso anterior de MST, son bastante parecidas y es algo bueno también. Comparación de resultados de la forma continua MST con la forma continua de Miller Tucker y Zemlin y con la forma de Desroche y Laporte Evaluando los problemas hasta el problema 10c, establaceremos una comparación entre las soluciones en continua de mi modelo con el modelo de Miller Tucker y Zemlin y también con el modelo de Derroche Laporte. Tal y como comentamos antes, en la formulación continua veremos cómo de bueno es el modelo fijándonos en la “lower bound” o cota inferior. Lo normal es que la cota inferior sea una solución mejor que la óptima en el modelo entero, por lo tanto cuanto más cerca se encuentre de ese óptimo, mejor será. Tabla 9 Comparación de la cota inferior de los modelos presentados MST ÓPTIMO R.K. MARTIN TIEMPO R.k. Martin M. T. Z. D.L. Steinb1 53 53 0:00:00 41,333 53 Steinb2 77 77 0:00:00 60,429 77 Steinb3 66 66 0:00:00 63,000 66 Steinb4 131 131 0:00:00 109,667 128 Steinb5 116 116 0:00:00 93,947 115 Steinb6 145 145 0:00:00 118,682 144 Steinb7 108 108 0:00:00 85,048 106 Steinb8 110 110 0:00:00 88,040 105 Steinb9 79 79 0:00:00 65,769 79 Steinb10 184 184 0:00:00 156,481 184 EXPERIMENTACIÓN 52 52 Steinb11 188 188 0:00:00 154,581 184 Steinb12 194 194 0:00:02 156,839 194 Steinb13 178 178 0:00:01 137,543 177 Steinb14 178 178 0:00:01 140,268 178 Steinb15 232 232 0:00:01 194,149 231 Steinb16 248 248 0:00:04 209,447 248 Steinb17 205 205 0:00:03 177,548 205 Steinb18 252 252 0:00:05 214,321 249 steinc1 666 666 0:00:10 541,127 682 steinc2 683 683 0:00:07 578,787 682 steinc3 827 827 0:00:15 625,492 821 steinc4 930 930 0:00:18 759,083 928 steinc5 1044 1044 0:00:29 859,865 1035 steinc6 1156 1156 0:06:19 973,597 1153 steinc7 1247 1247 0:08:20 1071,460 1247 steinc8 1182 1182 0:07:47 983,648 1180 steinc9 1293 1293 0:09:55 1057,670 1293 steinc10 1363 1363 0:10:34 1139,620 1363 Fuente: Elaboración propia En esta tabla podemos ver la comparación entre los resultados de los modelos nombrados anteriormente. Por un lado, podemos apreciar como los tiempos del modelo de R.k. Martin comienzan a crecer exponencialmente mientras los otros, aunque no estén en las tablas, son menores de cinco segundos todos. Por otro lado, los resultados del modelo de R.k. Martin en la forma continua MST son iguales que el óptimo, por lo que es algo muy bueno. El modelo de Derroche Laporte también tiene una muy buena cota inferior pero no siempre llega al óptimo. 53 Comparación de resultados de la forma continua steiner con la forma continua de Miller, Tucker y Zemlin y con la forma de Desrocher y Laporte En este apartado haremos una comparación similar al apartado anterior pero con las soluciones continuas en la forma Steiner. Por lo tanto la tabla de comparaciones quedaría de la siguiente forma: Tabla 10 Comparación de la cota inferior de los modelos presentados Steiner ÓPTIMO R.K. MARTIN TIEMPO R.k. Martin M. T. Z. D.L. Steinb1 82 79,5 0:00:00 70,083 77,75 Steinb2 83 83 0:00:00 76,714 82,5 Steinb3 138 138 0:00:00 133,105 138 Steinb4 59 53,7 0:00:00 41,410 50,5 Steinb5 61 50,5 0:00:00 43,395 52,167 Steinb6 122 119,024 0:00:01 93,409 107,333 Steinb7 111 111 0:00:00 99,286 105 Steinb8 104 98,375 0:00:00 81,640 92,75 Steinb9 220 220 0:00:00 203,692 217,5 Steinb10 86 80,25 0:00:01 64,148 70,333 Steinb11 88 81,7778 0:00:03 67,290 79 Steinb12 174 167,679 0:00:06 137,516 159,333 Steinb13 165 159,4 0:00:00 127,786 145,75 Steinb14 235 230 0:00:00 186,951 211,917 Steinb15 318 309,5 0:00:01 283,021 313,5 Steinb16 127 108,568 0:00:11 95,263 109,833 Steinb17 131 122,929 0:00:08 111,123 119,333 Steinb18 218 200 0:00:28 179,833 204,25 steinc1 85 76,4667 0:01:01 48,049 52 EXPERIMENTACIÓN 54 54 steinc2 144 115,833 0:01:05 69,189 81,5 steinc3 754 727,241 0:08:19 559,006 678,833 Fuente: Elaboración propia En esta tabla solo hemos llegado hasta el problema steinc3, ya que no pudimos resolver los siguientes problemas. Viendo de nuevo las soluciones, vuelve a ocurrir algo parecido. Con respecto al tiempo, este vuelve a crecer exponencialmente mientras en los otros modelos sigue siendo inferior a 5 segundos. Por otro lado, aunque en este caso las soluciones del modelo Steiner en continua no coincidan con las óptimas en Steiner entero, presenta cotas inferiores mejores que las de los otros dos modelos. 55 6 CONCLUSIONES Con respecto al modelo, podemos asegurar que el modelo es eficaz ya que alcanza el óptimo en los problemas que resuelve. Sin embargo, no es nada eficiente. Tarda demasiado, hasta más de dieciséis horas en resolver modelos en los que el número de aristas y de nodos es superior a 300 cada uno y hace que se creen demasiadas variables y restricciones. Eso ha hecho que, a la hora de ver los resultados, el trabajo se hiciera lento, ya que la mayoría de los problemas tardaban más de una hora en resolverse. Sin embargo, hemos comprobado que la formulación de R.k. Martin no se hizo para optimizar el tiempo sino para optimizar la cota inferior del problema MST. Como hemos podido comprobar, al resolver el problema MST que es de tipo P de forma continua, alcanzábamos el mismo óptimo que si lo resolvíamos de la forma entera en cualquier problema. Esto es lo que más destacamos de su formulación. Esto mismo no pasó cuando extrapolamos la formulación al problema de Steiner que es NP. En este problema la cota inferior no era el mismo óptimo que te daba cuando resolvías el problema de forma entera. Sin embargo, si es verdad que el acercamiento al óptimo fue mayor que los otros dos modelos. En general, este trabajo creo que se ha adecuado a mis conocimientos adquiridos en la carrera. Es cierto que para la programación en C y en LINGO tuve que aprender más, pero tuve la capacidad de hacerlo sin problema. También ha sido un trabajo desde mi punto de vista entretenido. Siempre me había gustado trabajar con modelos matemáticos y por eso mismo se me ha hecho más ameno. ANEXOS 62 62 63