El problema del flujo máximo: Teoría, algoritmos y aplicaciones

Traballo Fin de Grao El problema del ujo máximo: Teoría, algoritmos y aplicaciones. Ángela López Porta 2018/2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao El problema del ujo máximo: Teoría, algoritmos y aplicaciones. Ángela López Porta Julio, 2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estadística e Investigación Operativa Título: El problema de ujo máximo: Teoría, algoritmos y aplicaciones Breve descrición do contido En este trabajo el alumno se familiarizará con una clase importante de problemas de programación lineal. Más concretamente una clase especial de problemas de ujo en redes con coste mínimo: el problema de ujo máximo. Se trata de un problema clásico, ampliamente estudiado en la literatura y que aparece frecuentemente en aplicaciones prácticas, ya sea de forma directa o como subproblema de problemas más complejos. iii Índice general Resumen viii Introducción xi 1. El Problema de Flujo en Redes con Coste Mínimo 1 1.1. Programación lineal ............................... 1 1.1.1. Dualidad ................................. 3 1.1.2. Programación Lineal Entera ....................... 5 1.2. Grafos y Redes con Flujo ............................ 6 1.2.1. Redes con Flujo .............................. 7 1.3. PFCM ....................................... 8 1.4. PFCM con variables enteras: Unimodularidad ................. 10 2. El problema de ujo máximo 13 2.1. Introducción .................................... 13 2.2. Aplicaciones .................................... 14 2.2.1. Problema de ujo factible ........................ 15 2.2.2. Problema de los representantes ..................... 16 2.2.3. Problema de redondeo de matrices ................... 17 2.3. Conjunto de corte de capacidad mínima .................... 17 2.4. Teorema max-ow min-cut ............................ 19 3. Conceptos adicionales de optimización en redes 23 3.1. Tipos de algoritmos ............................... 23 3.2. Complejidad computacional ........................... 24 3.2.1. Diferentes medidas de complejidad ................... 24 3.2.2. Notación O ................................ 25 3.3. Algoritmos de búsqueda ............................. 26 v vi ÍNDICE GENERAL 3.4. Problema del camino más corto ......................... 27 3.5. Redes residuales ................................. 29 3.6. Etiquetas de distancia .............................. 30 4. Algoritmo de trayectorias aumentadas 33 4.1. Ejemplo de resolución .............................. 34 4.2. Relaciones entre la red original y la red residual ................ 37 4.3. Efectos del aumento en la descomposición de ujo ............... 39 4.4. Algoritmo de etiquetado ............................. 41 4.4.1. Exactitud del algoritmo y resultados relacionados ........... 47 4.4.2. Complejidad del algoritmo ........................ 48 4.4.3. Desventajas del algoritmo ........................ 49 5. Mejoras del algoritmo 51 5.1. Algoritmo de trayectorias aumentadas de máxima capacidad ......... 51 5.2. Algoritmo de escalado de capacidades ..................... 52 5.2.1. Complejidad del algoritmo ........................ 57 5.3. Algoritmo de trayectorias aumentadas más cortas ............... 57 5.3.1. Exactitud del algoritmo ......................... 63 5.3.2. Complejidad del algoritmo ........................ 65 5.3.3. Mejora práctica .............................. 68 5.4. Algoritmo de escalado de capacidades con caminos más cortos ........ 69 5.5. Algoritmo preow-push ............................. 70 Bibliografía 75 2 CAPÍTULO 1. EL PROBLEMA DE FLUJO EN REDES CON COSTE MÍNIMO • Restricciones de desigualdad, gi(x)≤0, i ∈ {1, . . . , m} ( gi:Rn−→ R ). • Restricciones de igualdad, hj(x) = 0, j ∈ {1, . . . , l} ( hj:Rn−→ R ). Así, un problema de programación matemática puede ser representado como: Minimizar f(x) sujeto a: gi(x)≤0i= 1, . . . , m hj(x)=0 j= 1, . . . , l. Si además imponemos que las tanto la función objetivo como las restricciones sean todas lineales, obtendremos la representación de un problema de programación lineal. Más comúnmente, podemos ver representado el problema de programación lineal de forma matricial. Para ello, denimos: Vector de costes, c∈Rn . Matriz de restricciones A∈Rm×n , con elementos de la forma aij . Vector de lados derechos, b∈Rm . Identicando estos elementos podemos escribir el problema de programación lineal como: Minimizar cTx sujeto a: Ax =b x≥0. Recordemos que siempre podemos transformar un problema de maximización en uno de minimización, y viceversa, multiplicando todos los coecientes de la función objetivo por −1 . La solución óptima para el problema original será la solución del nuevo problema pero multiplicada por −1 . Esto se debe a que se verica la siguiente igualdad: m´ax n X j=1 cjxj=−m´ın n X j=1 −cjxj. En cuanto a las restricciones,también podemos transformar una desigualdad del tipo  ≥  en otra del tipo  ≤ , y viceversa, multiplicando por −1 ambos lados de la desigualdad. Además, podemos transformar desigualdades en igualdades añadiendo unas nuevas variables, conocidas como variables de holgura . Dada una restricción Pn j=1 aijxj≥bi , se tendría Pn j=1 aijxj−xs i=bi con xs i≥0 . Análogamente, si tuviéramos Pn j=1 aijxj≤bi , se le sumaría esta nueva variable. 1.1. PROGRAMACIÓN LINEAL 3 Para la resolución de los problemas de programación lineal utilizamos el método símplex . Este consiste en ir saltando de punto extremo en punto extremo de la región factible hasta encontrar un punto extremo óptimo o hasta concluir que no existe tal óptimo. Como veremos más adelante en la Sección 3.2, para analizar el rendimiento de un algoritmo se puede recurrir a diferentes técnicas. Entre ellas destacan el análisis del peor caso y el análisis del caso promedio. El análisis del peor caso mira el rendimiento del algoritmo para aquellas clases de problemas que le resultan más difíciles de resolver. Por otra parte, el análisis del caso promedio mira el rendimiento promedio del algoritmo sobre todos los problemas de una determinada clase. El método símplex se comporta de forma diferente dependiendo de si usamos un análisis u otro. Mientras que en el caso promedio se obtiene un rendimiento polinomial, utilizando el análisis del peor caso el rendimiento pasa a ser exponencial 1 . 1.1.1. Dualidad Dado un problema de programación lineal, al que denominaremos primal, podemos asociarle un problema de programación lineal conocido como el problema dual . El estudio de este nuevo problema resulta de gran interés pues nos proporciona una solución para el problema primal. Además, es muy útil en el diseño de algoritmos ecientes para resolver tanto problemas de programación lineal como algunos problemas de optimización en redes, que introduciremos más adelante. La formulación de un problema dual a través de un primal es la siguiente: (P) Minimizar cTx sujeto a: Ax =b x≥0. (D) Maximizar bTπ(= πTb) sujeto a: ATπ≤c π no restringido . Figura 1.1: Problemas primal y dual en su forma estándar. (P) Minimizar cTx sujeto a: Ax ≥b x≥0. (D) Maximizar bTπ(= πTb) sujeto a: ATπ≤c π≥0. Figura 1.2: Problemas primal y dual en su forma canónica. 1 El tiempo que necesita para resolver el peor problema para un grafo con m aristas y n nodos, crece exponencialmente en función de estos dos parámetros. 4 CAPÍTULO 1. EL PROBLEMA DE FLUJO EN REDES CON COSTE MÍNIMO Diremos que π es el vector de variables duales del problema, y, a partir de dichas formulaciones, se deduce el siguiente conjunto de reglas para transformar un problema en el otro: Problema primal Problema dual F.objetivo Minimizar Maximizar F.objetivo Restricciones ≥bi ≤bi =bi ≥0 ≤0 no restring. Variables Variables ≥0 ≤0 no restring. ≤cj ≥cj =cj Restricciones Figura 1.3: Correspondencias entre el problema primal y el dual. Ejemplo 1.1. Consideremos el siguiente problema de programación lineal (P) Min 4x1+ 2x2+ 6x3+x4 sujeto a: x1+x2+x3≥6 x3+x4≤4 x1+x3= 2 x≥0. A partir de las reglas mencionadas en la tabla anterior, se tiene que la formulación para el problema dual asociado será: (D) Máx 6π1+ 4π2+ 2π3 sujeto a: π1+π3≤4 π1≤2 π1+π2+π3≤6 π2≤1 π1≥0 π2≤0 π3 no restrig. Puesto que el problema dual no deja de ser un problema de programación lineal podemos formular el dual del mismo, lo que nos lleva al siguiente resultado: Proposición 1.2. El dual del dual coincide con el primal. 1.1. PROGRAMACIÓN LINEAL 5 Consideremos ahora un problema de programación lineal y su dual expresados en su forma canónica. Si x y π son dos soluciones factibles para los respectivos problemas, entonces verican que Ax ≥b , πTA≤cT , x≥0 y π≥0 . De estas desigualdades se puede seguir: cTx≥(πTA)x=πT(Ax)≥πTb Es decir, la función objetivo asociada a cualquier solución factible para el problema de minimización siempre será mayor o igual que la función objetivo para el problema de maximización. Esta propiedad es conocida como la propiedad de dualidad débil . Presentamos, además, la siguiente relación entre las soluciones óptimas de ambos problemas. Proposición 1.3 (Dualidad fuerte) . Dados un problema de programación lineal y su dual, si uno de ellos tiene solución óptima entonces el otro también la tiene y ambos valores óptimos en la función objetivo coinciden. 1.1.2. Programación Lineal Entera En algunos problemas de programación lineal surge la necesidad de imponer que todas nuestras variables tomen valores únicamente enteros, puesto que en nuestro contexto no tendría sentido hablar de variables de decisión divisibles. Esta nueva restricción da lugar a un subproblema conocido como el problema de programación (lineal) entera . Minimizar f(x) sujeto a: gi(x)≤0i= 1, . . . , m hj(x)=0j= 1, . . . , l x∈Zn. Resulta casi inmediato pensar en resolver estos problemas mediante el método símplex, obviando que las variables deben ser enteras, es decir, relajando el problema, y después redondear el resultado obtenido. Sin embargo, con este procedimiento se pueden llegar a obtener resultados muy lejanos al óptimo real. Por ello, para resolver estos problemas ecazmente se utiliza el método de ramicación y acotación . Este método consiste en, a partir de observaciones anteriores, subdividir sucesivamente la región factible del problema de partida y resolver las versiones relajadas de los subproblemas resultantes, como ya hemos visto en la asignatura del grado. El método de ramicación y acotación es de tipo exponencial, por lo que se podría decir que es peor que el método símplex al necesitar más tiempo de ejecución. 6 CAPÍTULO 1. EL PROBLEMA DE FLUJO EN REDES CON COSTE MÍNIMO 1.2. Grafos y Redes con Flujo Para resolver los problemas de optimización en redes, y más particularmente el problema de ujo máximo que queremos estudiar, es muy habitual utilizar representaciones grácas que nos permitan visualizar tales problemas con facilidad. Es por ello que debemos recordar la denición de grafo y redes con ujo. Un grafo G es un par (N, A) en el cual N es el conjunto de elementos llamados nodos o vértices y A es el conjunto de elementos llamados aristas o arcos . Podemos distinguir dos tipos de grafos en función de A : Grafo dirigido: G se dice que es un grafo dirigido si A⊆N×N , es decir, la arista (i, j) comienza en el nodo i y termina en el nodo j . Grafo no dirigido: En este caso A se compone de subconjuntos de N de dos elementos. Los conjuntos {i, j} y {j, i} representan la misma arista. En lo relativo a este trabajo, solamente utilizaremos grafos dirigidos . 1 2 3 4 a1 a2 a3 a4 a5 (a) Grafo dirigido. En este caso N={1,2,3,4} y A={a1,...,a5} . 1 2 3 4 5 6 a1 a2 a3 a4 a5 a6 a7 a8 a9 (b) Grafo no dirigido. En este caso N={1,...,6} y A={a1,...,a9} . Figura 1.4: Ejemplo de un grafo dirigido y uno no dirigido. En ocasiones, es conveniente expresar la información dada en los grafos dirigidos de forma matricial. Para ello, dado un grafo G= (N, A) dirigido con conjunto de nodos N={1, . . . , n} y conjunto de aristas A={a1, a2, . . . , am} , se dene la matriz de adyacencia del grafo, An×n , como: aij =(1 si (i, j) es un arco de G 0 en otro caso. Otra posible forma de representar el grafo dirigido G es a través de la matriz de inci- 1.2. GRAFOS Y REDES CON FLUJO 7 dencia , Bn×m , que se dene como: bik =       1 si i es el nodo inicial de ak −1 si i es el nodo terminal de ak 0 en otro caso. A=      0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0       (a) Matriz de adyacencia B=      11000 −10110 0−1−1 0 1 000−1−1       (b) Matriz de incidencia Figura 1.5: Matrices de adyacencia e incidencia asociadas al grafo 1.4(a). 1.2.1. Redes con Flujo Una red es un grafo con uno o más números asociados a cada arista o nodo. Dichas cantidades pueden representar costes, distancias, . . . Denominamos ujo al envío de elementos de un lugar a otro dentro de la red, es decir, de un nodo a otro nodo. Un ujo podría representar el transporte de mercancías entre una fábrica y sus distintos puntos de distribución. Los modelos correspondientes a estas características los llamaremos modelos de redes con ujo . Los objetos que se envían a través de la red los denominamos unidades de ujo o simplemente unidades . Las unidades de ujo podrían ser personas, objetos,... En nuestro problema de optimización asociaremos a toda arista k un ujo fk obtenido tras resolver el problema, es decir, los ujos fk son las variables de decisión del problema. Dicho ujo depende de los siguientes tres parámetros: Cota inferior lk≥0 : cantidad mínima de ujo debe de enviarse por la arista k . Capacidad o cota superior uk≥0 : cantidad máxima de ujo que se puede enviar por la arista k . Coste o benecio ck : si es positivo denota el coste de enviar una unidad de ujo por la arista k . Si es negativo, en cambio, representa el benecio. En aquellos casos en los que nos interese hacer referencia a los nodos incidentes, i y j , de una arista k , pasaremos a referirnos a esta arista como la arista (i, j) y tendremos los valores asociados lij , uij y cij . 8 CAPÍTULO 1. EL PROBLEMA DE FLUJO EN REDES CON COSTE MÍNIMO [3] 1 2 3 4 5 [ −3 ] (1,5,2) (0,2,1) (2,6,1) (1,4,2) (0,2,3) (1,2,2) (0,3,4) Figura 1.6: Ejemplo de una red con ujo. En ocasiones podemos encontrar modelos de redes con ujo en los cuales, por algunos de los nodos, entre o salga ujo por la red. En ese caso diríamos que tenemos ujos externos . Podemos tener un ujo externo jo , es decir, una cantidad ja de ujo, que será positiva si entra a la red y negativa si sale de ella; o bien una cantidad variable, el ujo externo de holgura . En este último caso se asocia a cada nodo i los siguientes parámetros: Cota inferior, le i : Si es una cantidad positiva denota la cantidad mínima de ujo que entra a la red por el nodo i , y si es negativa denota la máxima cantidad de ujo que sale de la red por el nodo i . Cota superior o capacidad, ue i : Si es positivo hace referencia a la cantidad máxima de ujo que entra por el nodo i a la red, y si es negativa denota la cantidad mínima que debe salir por dicho nodo. Coste o benecio, ce i : Si es positivo denota el coste por unidad de ujo que circula por el nodo i , y si es negativa el benecio. Dada una red con ujo R podemos expresarla como R= ((N, A),(l, u, c),(le, ue, ce)) donde (N, A) es el grafo asociado a la red, (l, u, c) son las capacidades y costes de los arcos, y (le, ue, ce) son los ujos externos con sus costes. Debemos observar que siempre podemos transformar una red con ujos externos en otra sin ellos añadiendo un nuevo nodo auxiliar. Así, si un nodo i tiene ujo externo positivo, añadimos un arco desde el nodo auxiliar al nodo i . Si, por el contrario, el nodo tiene un ujo externo negativo, el arco irá del nodo i al nodo auxiliar. Los parámetros de los nuevos arcos se determinan a través de los parámetros que teníamos para el nodo i . Ilustramos este procedimiento en la Figura 1.7. 1.3. PFCM Para denir el problema general de ujo en redes con coste mínimo vamos a considerar la ausencia de ujos externos en la red, lo cual no es restrictivo por lo visto anteriormente. 1.3. PFCM 9 1 [3,2,1] 2 [0,0,0] 3 [ −1 ,0,2] 4 [2,4, −3 ] 5 [ −3 ,0,1] (1,5,2) (0,2,1) (2,6,1) (1,4,2) (0,2,3) (1,2,2) (0,3,4) 1 2 3 4 56 (1,5,2) (0,2,1) (2,6,1) (1,4,2) (0,2,3) (1,2,2) (0,3,4) (3,2,1) (2,4,−3) (0,1,2) (0,3,1) Figura 1.7: Paso a una red sin ujos externos. 10 CAPÍTULO 1. EL PROBLEMA DE FLUJO EN REDES CON COSTE MÍNIMO Por ello, es claro imponer la restricción de conservación de ujo , que establece que la cantidad de ujo que entra en un nodo tiene que coincidir con la cantidad de ujo que sale de él. En otras palabras, ningún nodo puede generar o eliminar ujo. Dada una red con ujo, el problema de ujo en redes con coste mínimo consiste en establecer el ujo que debe pasar por cada arco de modo que el coste sea mínimo y, a su vez, se respeten las restricciones de capacidad de los arcos y la conservación de ujo de cada nodo. Para mayor comodidad en la lectura, nos referiremos a este problema como el PFCM. Veamos que un PFCM se puede escribir como un problema de programación lineal. Si denotamos por AOi el conjunto de arcos que salen del nodo i y por ATi el conjunto de arcos que terminan en el nodo i , obtenemos la formulación: Minimizar X k∈A ckfk sujeto a: X k∈AOi fk−X k∈ATi fk= 0 i∈N fk≤ukk∈A fk≥lkk∈A. Las restricciones del problema no son más que las ya mencionadas anteriormente, la conservación de ujo y las restricciones de capacidad de los arcos. La función objetivo en este caso es el coste que supone enviar el ujo por la red. Visto de este modo, está claro que este problema lo podremos resolver mediante el método símplex. Además, podemos obtener una representación matricial del problema. Sea A la matriz de restricciones, B la matriz de incidencia asociada al grafo y b el vector con las constantes del lado derecho. Dado un vector v , que es un vector columna, denotamos su traspuesto como vT . Si denotamos por c , f , u y l los vectores coste, ujos, cotas superiores y cotas inferiores, respectivamente, tendríamos: Minimizar cTf sujeto a: Bn×mf=0 Im×mf≤u Im×mf≥l. 1.4. PFCM con variables enteras: Unimodularidad En ocasiones, necesitaremos imponer en nuestro PFCM que las variables tomen valores enteros con lo que obtendríamos un problema de programación lineal entera, que, por lo 1.4. PFCM CON VARIABLES ENTERAS: UNIMODULARIDAD 11 general, es más costoso de resolver. Sin embargo, gracias a la estructura del PFCM, veremos que podemos resolverlo mediante el método símplex. Para ello, trabajaremos con un nuevo concepto, la unimodularidad. Denición 1.4. Una matriz cuadrada A∈Zp×p se dice que es unimodular si tiene por determinante 1 o −1 . Además, A∈Zp×q se dice totalmente unimodular si cualquier submatriz cuadrada es singular o unimodular. Teniendo en cuenta que todos los elementos de una matriz pueden ser considerados como submatrices 1 × 1, se deduce que una matriz totalmente unimodular está compuesta únicamente de los números 0 , 1 y −1 . Proposición 1.5. Dada una matriz totalmente unimodular A∈Zp×q y un vector b∈Zp , tenemos que cualquier solución básica factible denida por las restricciones Ax =b , x≥0 , tiene todas sus componentes enteras. Por tanto, si tenemos un vector de lados derechos con componentes enteras y una matriz de restricciones totalmente unimodular, la proposición anterior nos asegura que todas las soluciones básicas factibles que encontremos para el problema Ax =b,x≥0 , tendrán todos sus elementos enteros. Particularmente, si existen óptimos nitos, alguno de ellos debe tomar valores enteros. Esto nos permite obviar la condición de integralidad de las variables y resolver el problema de programación lineal con el método símplex. Proposición 1.6. La matriz de incidencia B de un grafo dirigido es totalmente unimodular. Recordando la formulación matricial que teníamos para el problema de ujo en redes a coste mínimo Minimizar cTf sujeto a: Bn×mf=0 Im×mf≤u Im×mf≥l, veamos que podemos transformar este problema en otro problema equivalente de la forma Af =b,f≥0 , con b entero y A totalmente unimodular. Por una parte, como l≥0 , la condición f≥0 es trivial. Para obtener Af =b tomamos como vector de lados derechos el vector b= (0,...,0, u1, . . . , um, l1, . . . , lm) y como matriz de restricciones la matriz A=    Bn×m0n×m0n×m Im×mIm×m0m×m Im×m0m×m−Im×m     . 18 CAPÍTULO 2. EL PROBLEMA DE FLUJO MÁXIMO s 1 2 3 10 20 30 t (6,7) (14,15) (18,19) (1,2) (2,3) (3,4) (5,6) (7,8) (1,2) (8,9) (6,7) (3,4) (14,15) (15,16) (8,9) Figura 2.4: Ejemplo del problema de redondeo de matrices. conjuntos S y S son tales que, para dos puntos distinguidos, por ejemplo 1 y n , 1∈S y n∈S se dice que el corte es un corte 1−n . Si tenemos un corte (S, S) sobre el grafo G asociado a una red R , se dene la capacidad del conjunto de corte como U(S, S) = P(i,j)∈(S,S)uij . 1 2 3 4 5 6 7 3 1 9 2 5 7 1 Tenemos muchas alternativas para formar conjuntos de corte 1−6 para este grafo, entre ellas están los siguientes ejemplos, con sus respectivas capacidades: S={1} , S={2,3,4,5,6} , (S, S) = {(1,2),(1,3)} , U(S, S) = 10 . S={1,2,3} , S={4,5,6} , (S, S) = {(2,4),(3,5)} , U(S, S) = 11 . S={1,2,3,4,5} , S={6} , (S, S) = {(4,6),(5,6)} , U(S, S)=6 . S={1,4,5} , S={2,3,6} , (S, S) = {(1,2),(1,3),(4,6),(5,6)} , U(S, S) = 16 . Consideremos ahora un ujo factible f para el problema de ujo máximo y un conjunto de corte (S, S) de modo que s∈S y t∈S . Por ser f un ujo factible debe vericar las 2.4. TEOREMA MAX-FLOW MIN-CUT 19 restricciones del problema, con lo que podemos escribir F=X i∈S X {j:(i,j)∈A} fij −X {j:(j,i)∈A} fji . Además, dados dos nodos p y q en S tales que (p, q)∈A , la variable xpq que surge en el primer sumando cuando hacemos i=p se cancela con la variable −xpq que surge en el segundo tras hacer i=q . Si p y q pertenecieran a S y (p, q)∈A , notar que la variable xpq no aparecería en la expresión. Teniendo en cuenta estos argumentos, podemos simplicar y reescribir lo anterior de la siguiente forma: F=X (i,j)∈(S,S) fij −X (i,j)∈(S,S) fij. Teniendo en cuenta que todo ujo factible verica 0≤fij ≤uij , se deduce el siguiente resultado: Lema 2.1. Cualquier ujo factible del nodo 1 al nodo n es menor o igual que la capacidad de cualquier conjunto de corte 1−n . Este resultado implica que si tenemos un ujo factible cuyo valor es igual a la capacidad de un conjunto de corte, entonces es un ujo máximo y el conjunto de corte tiene capacidad mínima. Denición 2.2. Dada una red R con capacidades limitadas en los arcos, el problema del conjunto de corte de capacidad mínima consiste en encontrar un conjunto de corte (S, S) cuya capacidad sea la mínima entre todos los conjuntos de corte que se pueden denir en la red. 2.4. Teorema max-ow min-cut Para nalizar este capítulo estudiaremos la formulación dual del problema de ujo máximo, la relacionaremos con los conjuntos de corte y, a partir de esta relación, deduciremos el teorema max-ow min-cut . Recordemos la formulación del problema de ujo máximo: Maximizar F sujeto a: X {j:(i,j)∈A} fij −X {j:(j,i)∈A} fji =       F si i=s 0 si i∈N−{s, t} −F si i=t 0≤fij ≤uij ∀(i, j)∈A. 20 CAPÍTULO 2. EL PROBLEMA DE FLUJO MÁXIMO Equivalentemente, teniendo en cuenta que denotamos por ~ ei∈Rn el vector i -ésimo de la base canónica de Rn y que, dada la matriz de incidencia B , se tiene que bik = 1 si i es el nodo inicial de la arista ak , bik =−1 si i es el nodo nal del arco ak y bik = 0 en otro caso. Maximizar F sujeto a: (~ en−~ e1)F+Bf =0n restricciones f≤um restricciones f≥0m restricciones . Nótese que para cada la i de B , Bf me da Pfij para los arcos que empiezan en i y P−fji para los arcos que terminan en i . Por tanto, la matriz de restricciones del problema viene dada por: A=                −1 0 . . . Bn×m 1 0 . . . Im×m 0               (n+m)×(m+1). La primera columna de A hace referencia al arco de vuelta, que va desde el nodo n al nodo 1 , mientras que el resto de columnas son las equivalentes a los arcos de la red original. Cada columna de la matriz implicará una restricción en el problema dual, luego tendremos π1, . . . , πn variables duales asociadas a las restricciones de conservación de ujo y variables δij asociadas a las restricciones de capacidad de los arcos. Así, teniendo en cuenta las equivalencias dadas en la Figura 1.3 y que nuestro problema primal es el problema de maximización, el dual resulta: Minimizar n X i=1 πi0 + n X i=1 n X j=1 uijδij sujeto a: πn−π1= 1 πi−πj+δij ≥0∀(i, j)∈A π∈Rn (no restringido) δij ≥0. Interpretación informal del dual: Nuestro objetivo es separar los nodos 1 y n rompiendo la red lo mínimo posible. 2.4. TEOREMA MAX-FLOW MIN-CUT 21 δij : ¾Qué porcentaje elimino del arco (i, j) ? Por el teorema de dualidad débil, sabemos que el valor de la función objetivo sobre cualquier solución factible para el problema de minimización será mayor o igual que el valor de la función objetivo del problema de maximización. Consideramos ahora un corte (S, S) separando el nodo 1 y el nodo n . Si denimos πi=(0i∈S 1i∈S y δij =(1 (i, j)∈(S, S) 0 en otro caso, se puede ver que esta solución siempre es factible para el dual y la función objetivo del mismo coincide con la capacidad del conjunto de corte (S, S) . Por tanto, dado que todo conjunto de corte separando la fuente y el sumidero se corresponde con una solución factible para el problema dual, el siguiente resultado es una consecuencia inmediata del teorema de dualidad débil: Proposición 2.3. El valor de cualquier ujo factible entre el nodo fuente y el sumidero es menor o igual a la capacidad de cualquier conjunto de corte separando esos dos nodos. Además, el algoritmo de trayectorias aumentadas que veremos en el Capítulo 4construye un ujo factible y un conjunto de corte tales que el valor del primero coincide con la capacidad del conjunto de corte, lo que implica, por la proposición anterior, que ambas soluciones son óptimas. Este resultado se conoce como el Teorema max-ow min-cut que presentamos a continuación. Teorema 2.4 (Teorema max-ow min-cut) . La capacidad del conjunto de corte de capacidad mínima coincide con el ujo máximo en la red. Como consecuencia del resultado anterior tenemos que, esencialmente, resolver el problema del conjunto de corte de capacidad mínima es equivalente a resolver el dual del problema de ujo máximo. Capítulo 3 Conceptos adicionales de optimización en redes Este capítulo nos servirá de transición antes de comenzar a tratar algunos algoritmos de resolución para el problema de ujo máximo. En él, hablaremos de conceptos ya vistos en la asignatura de Programación Lineal y Entera, por lo que seguiremos los apuntes de Julio González Díaz (2018-2019). Entre estos conceptos podemos encontrar una clasicación para los algoritmos (Sección 3.1), el conocido problema del camino más corto (Sección 3.4), o una pequeña introducción a la teoría de complejidad computacional (Sección 3.2) la cual nos permitirá comparar los algoritmos que desarrollaremos para el PFM según su eciencia. El resto del capítulo lo utilizaremos para desarrollar conceptos nuevos y los algoritmos de búsqueda, ambos obtenidos de Ahuja et al. (1993), que serán utilizados continuamente para facilitar el diseño de nuestros algoritmos. 3.1. Tipos de algoritmos Un algoritmo es un procedimiento, paso a paso, diseñado para resolver un problema dado. De entre todos los algoritmos posibles para un mismo tipo de problema, debemos identicar aquel que será el más eciente. Dadas las diferentes clasicaciones que existen para los algoritmos, pasamos a mencionar solamente un par de ellas. Un algoritmo se dice determinístico si es predecible, es decir, si dado un problema todas las ejecuciones del algoritmo producen el mismo resultado nal y los mismos resultados intermedios. En los algoritmos no determinísticos , sin embargo, se introduce algún tipo de aleatoriedad en el proceso de búsqueda de la solución. Por ejemplo, un algoritmo de tipo no determinístico sería, dentro de un problema de optimización, generar un conjunto 23 24 CAPÍTULO 3. CONCEPTOS ADICIONALES DE OPTIMIZACIÓN EN REDES de puntos aleatoriamente y escoger, de entre los factibles, el mejor. Aunque es posible que coincida la solución nal, el conjunto de puntos generados no tiene por qué ser el mismo, lo que haría no coincidir los resultados intermedios. Haciendo referencia a la precisión del algoritmo, podemos clasicarlo en estos tres grandes grupos: Algoritmos exactos: En este grupo se incluyen todos aquellos algoritmos que siempre devuelven la solución exacta del problema. Algoritmos aproximados: En este otro grupo se encuentran aquellos algoritmos cuyas soluciones estarán dentro de un determinado porcentaje del óptimo. Un algoritmo λ -aproximado devolverá una solución x tal que 1 :        OPT ≤c(x)≤λ· OPT si λ > 1, y λ· OPT ≤c(x)≤ OPT si λ < 1. Algoritmos heurísticos: Este tipo de algoritmos devuelven soluciones sin ninguna garantía de optimalidad. Pese a esto, los tiempos de ejecución para este grupo de algoritmos es mucho menor. El interés general, claramente, estará en utilizar algoritmos exactos para la resolución de los problemas. Sin embargo, estos algoritmos pueden llegar a ser muy lentos, lo que nos lleva a echar mano de algoritmos aproximados, o, incluso, de algoritmos heurísticos. 3.2. Complejidad computacional La teoría de complejidad computacional es la encargada de estudiar la efectividad de los diferentes algoritmos. Para ello, se centra en acotar el número de operaciones que necesitará el algoritmo en función de unos datos arbitrarios que especicarían el problema. 3.2.1. Diferentes medidas de complejidad El número de pasos requeridos por un algoritmo es la suma de todos sus pasos intermedios, entre los cuales se encuentran los pasos de asignación, pasos de cálculos aritméticos y pasos de evaluaciones lógicas. Habitualmente el rendimiento de un algoritmo se suele medir mediante alguno de los siguientes enfoques: 1 Se escogerá λ > 1 o λ < 1 en función de si es un problema de minimización o de maximización, respectivamente. 3.2. COMPLEJIDAD COMPUTACIONAL 25 1. El análisis empírico: El objetivo consiste en estimar como se comporta el algoritmo en la práctica ejecutándolo con distintos ejemplos del problema. Desventajas de este enfoque: El rendimiento del algoritmo depende del lenguaje de programación empleado, del compilador, del ordenador utilizado para la ejecución, así como de la habilidad del propio programador. Es muy costoso realizar un análisis de este tipo, además, a menudo los resultados son inconclusos puesto que el resultado puede depender del problema elegido para los test. 2. Análisis del caso promedio: El objetivo se basa en estimar el número medio de pasos que necesitará el algoritmo para devolver una solución. Se suele escoger una distribución de probabilidad sobre los posibles problemas y, mediante el uso de técnicas estadísticas, se derivan los tiempos de ejecución asintóticos del algoritmo. Desventajas de este enfoque: El análisis se ve condicionado por la distribución de probabilidad seleccionada. Habitualmente es complicado determinar la distribución que mejor se adapta a los problemas que surgen en la práctica. Además, se trata de un análisis muy complicado de llevar a cabo para algoritmos complejos. 3. Análisis del peor caso: Este enfoque proporciona cotas superiores para el número de operaciones que va a necesitar un algoritmo al resolver cualquier problema dentro de la clase en estudio. Ventajas de este enfoque: El análisis es independiente del entorno computacional, es más sencillo de realizar y proporciona un tiempo de ejecución máximo para el algoritmo. Además, es capaz de comparar de forma inequívoca dos algoritmos dados. Desventajas de este enfoque: Puede llegar a clasicar como malo un algoritmo que solo funciona mal en ejemplos patológicos, a pesar de que estos aparecen raramente en la práctica. Esto es lo que ocurría con el método símplex, que tiene un tiempo exponencial según el peor caso, pero en los casos prácticos es polinomial. 3.2.2. Notación O Se dice que un algoritmo tiene una velocidad O(f(n)) si existen dos constantes k y n0 tales que, para un problema de tamaño n≥n0 , el número de operaciones efectuadas por el algoritmo para resolverlo es menor o igual que kf(n) . Un algoritmo se dice polinomial si tiene una velocidad O(f(n)) donde f es un polinomio. Por ejemplo, si tenemos un algoritmo cuyo tiempo de ejecución es 1000n2+0,01n3 , tomando n≥104 , n3 es mayor que 1000n2+ 0,01n3 , con lo que la complejidad del algoritmo será O(n3) , y, por tanto, el algoritmo es polinomial. 26 CAPÍTULO 3. CONCEPTOS ADICIONALES DE OPTIMIZACIÓN EN REDES En la práctica nos interesará trabajar con algoritmos, a lo sumo, de tiempo polinomial puesto que los algoritmos no polinomiales pueden llegar a ser muy poco útiles en el estudio de problemas grandes. 3.3. Algoritmos de búsqueda Los algoritmos de búsqueda están diseñados para encontrar entre todos los nodos de una red aquellos que cumplan una cierta propiedad impuesta. Este tipo de algoritmos son utilizados habitualmente en el diseño de algoritmos más complejos, como pueden ser los algoritmos de resolución para el problema de ujo máximo. Entre las aplicaciones más comunes de un algoritmo de búsqueda se incluyen el encontrar todos los nodos de la red a los que se puede llegar a través de un camino dirigido desde un nodo prejado, identicar todos los nodos que contienen un camino dirigido hasta un nodo t prejado,... Supongamos que queremos identicar todos los nodos que se pueden alcanzar partiendo de un nodo fuente, s , en una red dirigida R= (G, (l,u,c)) . Para ello, se denen dos conjuntos, el conjunto de nodos marcados y el de nodos no marcados . El conjunto de nodos marcados estará formado por aquellos nodos que son alcanzados desde la fuente, y, por tanto, será nuestra solución al problema. Por otra parte, se dirá que un arco (i, j) es admisible siempre y cuando el nodo i pertenezca al conjunto de los nodos marcados y el nodo j no; en otro caso, se dirá que el arco es inadmisible . Además, cuando el arco (i, j) es admisible, el nodo j se puede introducir en el conjunto de los nodos marcados, pues tenemos un camino dirigido de s a j formado por el camino de s a i (que existe por ser i un nodo marcado) más el arco (i, j) . En este caso se dice que j tiene como predecesor al nodo i , pred( j )= i . Para analizar los arcos admisibles de la red, el algoritmo parte de un nodo marcado i y examina todos los arcos que salen de i para ver si son admisibles o no. Para ello, hace uso de la lista de adyacencia del nodo, A(i) . Dados dos nodos j , k , con j < k , y (i, j),(i, k)∈A(i) , se impone que el algoritmo analice primero el arco (i, j) y después el arco (i, k) . Una vez que se hayan analizado todos los arcos, decimos que i ya no posee arcos admisibles y, entonces, el algoritmo salta a otro de los nodos marcados para analizar, de la misma forma, su lista de adyacencia. Una vez que el algoritmo ha nalizado, es decir, una vez que ya no queden nodos marcados sin analizar sus listas de adyacencia, haciendo uso de los predecesores se puede crear un árbol conocido como el árbol de búsqueda . Tomando como ejemplo la red dada en la Figura 3.1(a), podemos obtener los árboles de búsqueda 3.1(b) y3.1(c). Como vemos, 3.4. PROBLEMA DEL CAMINO MÁS CORTO 27 existen múltiples árboles de búsqueda para una misma red dependiendo del orden en el cual vayamos seleccionando los nodos para analizar. Pese a ello, notar que el conjunto de nodos marcados siempre será el mismo. 1 2 3 5 4 6 (a) Red original. 1 2 3 5 4 6 (b) Primer árbol de búsqueda. 1 2 3 5 4 6 (c) Segundo árbol de búsqueda. Figura 3.1: Ejemplos de árboles de búsqueda para una red Se puede ver fácilmente que el algoritmo de búsqueda proporciona una solución en un tiempo máximo de O(m) , donde m=|A| para la red R= (G, (l,u,c)) . Esto es así pues el algoritmo analiza cada arco, a lo sumo, una única vez. 3.4. Problema del camino más corto No podemos continuar con el desarrollo del trabajo sin mencionar el problema del camino más corto. Este problema resulta de gran interés a la hora de estudiar problemas de optimización en redes pues, al igual que ocurría con los algoritmos de búsqueda, aparece frecuentemente como subproblema de otros más complejos. El problema del camino más corto en una red dirigida R= (G, (l,u,c)) con vector de costes c∈Rn consiste en encontrar el camino entre los nodos 1 y n de la red cuyo coste sea mínimo. El coste de un camino no es más que la suma de los costes de los arcos que lo forman. Se puede ver fácilmente que el problema del camino más corto no deja de ser un caso 34 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS Hay que tener en cuenta que, como las capacidades residuales de los arcos de la red residual son siempre positivas, la capacidad residual de una trayectoria aumentada también será positiva. Es por ello que si existe una camino dirigido de la fuente al sumidero, podremos incrementar la cantidad de ujo que se puede enviar entre la fuente y el sumidero en δ unidades. El trabajo del algoritmo de trayectorias aumentadas consiste en ir identicando los caminos dirigidos de s a t existentes en la red, con sus respectivas capacidades residuales, hasta que no existan más trayectorias de este tipo. Algoritmo 1: Algoritmo de trayectorias aumentadas. inicio f:= 0 ; mientras R(f) contenga un camino dirigido de s a t hacer identicar una trayectoria aumentada P de s a t ; δ:= m´ın{rij : (i, j)∈P} ; aumentar δ unidades de ujo a lo largo de P y actualizar R(f). n n El algoritmo de trayectorias aumentadas descrito de esta forma no queda totalmente determinado, por lo que su eciencia dependerá, por ejemplo, de la forma en la que se identiquen y se elijan las diferentes trayectorias aumentadas, como veremos más adelante. 4.1. Ejemplo de resolución Procedemos a ilustrar, paso a paso, cómo se obtiene el ujo máximo del nodo 1 al nodo 7 para la siguiente red con ujos empleando el algoritmo de trayectorias aumentadas. 4.1. EJEMPLO DE RESOLUCIÓN 35 1 2 3 4 5 6 7 6 5 5 5 34 1 1 7 3 8 Figura 4.2: Ilustración del algoritmo para el PFM. PASO 1: Inicializamos el vector de ujo f=0 , con ujo asociado F= 0 . PASO 2 (Iteración 1): Con el vector de ujos f=0 , R=R(f) , con lo que uij =rij . Seleccionamos un camino dirigido de s a t , por ejemplo, el camino P1= { (1,2),(2,3),(3,7) }. Dicha trayectoria tiene una capacidad residual de δ= m´ın{6,5,4}= 4 unidades. Enviamos, por tanto, δ unidades de ujo a lo largo de P1 , con lo cual F= 4 , y actualizamos R(f) : 1 2 3 4 5 6 7 2 5 5 4 1 34 1 1 7 3 8 4 Figura 4.3: Iteración 1. PASO 3 (Iteración 2): Puesto que todavía existen caminos dirigidos entre la fuente y el sumidero, el algoritmo continúa. Escogemos otra de las trayectorias aumentadas, en este caso, P2={(1,2),(2,5),(5,6),(6,7)} y δ= m´ın{2,3,7,8}= 2 . Actualizamos el valor del ujo F= 4 + 2 = 6 y la red residual resultante tras enviar δ unidades de ujo a lo largo de P2 : 36 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS 1 2 3 4 5 6 7 5 5 6 1 14 1 21 5 3 2 6 4 2 Figura 4.4: Iteración 2. PASO 4 (Iteración 3): Observando la nueva red residual vemos que todavía existen trayectorias aumentadas, luego el algoritmo actúa de forma análoga a la iteración anterior. Identicamos un camino dirigido desde el nodo 1 al nodo 7 , por ejemplo P3= {(1,4),(4,6),(6,7)} , cuyo valor residual es δ= m´ın{5,1,6}= 1 . Actualizamos nuestra red residual para los nuevos ujos y aumentamos el valor de F= 6 + 1 = 7 : 1 2 3 4 5 6 7 4 5 6 1 14 1 21 5 3 1 2 5 4 3 Figura 4.5: Iteración 3. PASO 5 (Iteración 4): Observamos que P4={(1,5),(5,6),(6,7)} es una trayectoria aumentada con capacidad residual δ= m´ın{5,5,5}= 5 . Tenemos, por tanto, una actualización en el ujo F= 7 + 5 = 12 y una nueva red residual: 4.2. RELACIONES ENTRE LA RED ORIGINAL Y LA RED RESIDUAL 37 1 2 3 4 5 6 7 4 5 6 1 14 1 21 3 1 7 4 8 Figura 4.6: Iteración 4 PASO 6 (Iteración 5): No existe ningún camino dirigido entre el nodo 1 y el nodo 7 en la red residual, por lo que el algoritmo naliza y el valor del ujo máximo de la red es F= 12 . Dicho valor tiene asociadas las variables de ujo f12 = 6, f15 = 5, f14 = 1 , f23 = 4, f25 = 2, f37 = 4, f46 = 1, f56 = 7, f67 = 8 y, en cualquier otro caso, fij = 0 . 4.2. Relaciones entre la red original y la red residual En el ejemplo anterior hemos visto que el algoritmo nos devuelve el valor del ujo máximo para la red. Sin embargo, para dar una solución completa, debemos proporcionar también las variables de ujo correspondientes a cada arco. Hay que tener en cuenta que cuando denimos el algoritmo de trayectorias aumentadas estamos siempre trabajando sobre la red residual, con lo que obtenemos los resultados en función de las capacidades residuales de caminos entre la fuente y el sumidero, de donde obtenemos posteriormente las variables de ujo. Sin embargo esta elección no es obligatoria, podríamos utilizar la red original y obtener directamente los ujos asociados a las aristas. Para ver cómo podemos pasar de una alternativa a otra, debemos entender las relaciones que existen entre los ujos asociados a las aristas en la red original y las capacidades residuales de los caminos en la red residual. Una trayectoria aumentada en la red original es un camino entre la fuente y el sumidero donde la arista (i, j) se puede recorrer en el sentido natural si, para el ujo f actual, se tiene fij < uij , y en sentido inverso si fij >0 . Si la red original R contiene una trayectoria aumentada con respecto a un ujo f , existe un camino dirigido de la fuente al sumidero en R(f) . De igual modo, si existe un camino dirigido en la red residual, entonces existe una trayectoria aumentada en la red original. Supongamos que hemos actualizado las capacidades residuales. ¾Cómo afecta dicho 38 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS aumento a las variables de ujo? Sabemos que las capacidades residuales están denidas como rij =uij −fij +fji , luego si aumentamos δ unidades en el arco (i, j) , podrían ocurrir cualquiera de los siguientes casos: 1. Un aumento de δ unidades en fij en la red original. 2. Una disminución de δ unidades en fji en la red original. 3. Una combinación lineal de ambas. ij (fij, uij) 1 2 3 4 5 6 (1,3) (0,3 ) (0,1) (1,4) (0,1) (0,3) (1,2) (a) Red original con ujo. ij rij 1 2 3 4 5 6 2 3 1 1 3 1 3 11 1 (b) Red residual asociada. 1 2 3 4 5 6 2 2 14 11 12 1 1 1 (c) Red residual actualizada después de mandar una unidad de ujo por el camino 1−3−5− 2−4−6 . 1 2 3 4 5 6 (1,3) (1,3 ) (1,1) (0,4) (1,1) (1,3) (1,2) (d) Vuelta a la red original. Figura 4.7: Ilustración de cómo cambian las variables de ujo. Para la red proporcionada en la Figura 4.7 si comparamos la red inicial (4.7(a)) con la solución obtenida tras enviar una unidad de ujo por el camino 1−3−5−2−4−6 (4.7(d)), entonces observamos que los arcos (1,3),(3,5),(2,4) y (4,6) aumentaron en una unidad su ujo, mientras que el arco (2,5) disminuyó esta misma unidad. Nos queda por ver cómo se transforman las capacidades residuales rij nuevamente en ujos fij . Tenemos que rij =uij −fij +fji , o, lo que es lo mismo, fij −fji =uij −rij . Obviamente, existen diferentes combinaciones de fij y fji que proporcionan un mismo resultado. Por ello, si tenemos uij ≥rij tomaremos fij =uij −rij y fji = 0 . En otro caso, fij = 0 y fji =rij −uij . 4.3. EFECTOS DEL AUMENTO EN LA DESCOMPOSICIÓN DE FLUJO 39 Vamos a detallar este cálculo para obtener el ujo de los arcos después de enviar una unidad de ujo por el camino 1−3−5−2−4−6 , es decir, vamos a ver cómo transformamos la red 4.7(c) en la red 4.7(d). Primeramente, sacamos las capacidades de los arcos de la red original y las capacidades residuales de 4.7(c) no nulas: u12 = 3 r12 = 2 u25 = 5 r25 = 4 u46 = 3 r46 = 2 r56 = 1 u13 = 3 r13 = 2 r31 = 1 r53 = 1 u24 = 1 u35 = 1 u56 = 2 r56 = 1 r21 = 1 r42 = 1 r64 = 1 Tenemos que u12 ≥r12 , u13 ≥r13 , u24 ≥r14 = 0 , u25 ≥r25 , u35 ≥r35 = 0 , u46 ≥r46 y u56 ≥r56 , luego, en estos casos, se tiene que fij =uij −ri y fji = 0 , es decir, f12 = 3 −2 = 1; f13 = 3 −2 = 1; f24 = 1 −0 = 1; f25 = 5 −4 = 1; f35 = 1 −0 = 1; f46 = 3 −2 = 1; f56 = 2 −1 = 1; En otro caso, uij < rij , tendremos que fij = 0 y fji =rij −uij : f12 = 1 −0 = 1; f24 = 1 −0 = 1; f56 = 1 −0 = 1; f13 = 1 −0 = 1; f46 = 1 −0 = 1; Observamos que hay variables de ujo que se repiten en los dos casos, pero su valor siempre va a coincidir. 4.3. Efectos del aumento en la descomposición de ujo Dedicaremos esta sección a mejorar la interpretación que se tiene del algoritmo de trayectorias aumentadas. Para ello, ilustraremos el efecto que supone un aumento en la descomposición de ujo sobre la siguiente red con ujos: 1 2 3 4 (1,3) (0,2) (1,3) (0,1) (1,2) Estos ujos iniciales pueden descomponerse como se representa en la Figura 4.8(a). Ahora bien, si consideramos el camino 1−3−2−4 sobre la red residual asociada y enviamos una unidad de ujo a través del mismo, obtenemos la descomposición de ujo dada en la 40 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS 1 2 3 4 1 1 1 (a) 1 2 3 4 1 1 1 1 (b) Figura 4.8: Descomposiciones de ujo individuales. Figura 4.8(b). Vemos que, a pesar de estar enviando ujo por el camino 1−3−2−4 , dicho camino no aparece en la nueva descomposición de ujo. La argumentación de por qué pasa esto es bastante sencilla de ilustrar. Primeramente, el camino 1−2−3−4 podemos descomponerlo en tres segmentos: el primero sería el camino hasta el nodo 2 , el segundo sería el arco (2,3) recorrido en sentido natural, y el camino hasta el nodo 4 . De igual forma, el camino 1−3−2−4 se descompone como el camino hasta el nodo 3 , el arco (2,3) recorrido en sentido inverso, y el camino hasta el nodo 4 (ver Figura 4.9(a)). El aumento por el camino 1−3−2−4 podemos verlo como la unión del primer segmento del camino 1−2−3−4 con el último segmento del aumento, la unión del último segmento del camino 1−2−3−4 con el primer segmento del aumento, y la cancelación de ujo en los arcos (2,3) y (3,2) , pues la unión de ambos se anula. Estas uniones dan lugar a una descomposición neta del ujo en la cual no aparece el arco (2,3) (ver Figura 4.9(b)). En general, cada aumento no es más que pegar segmentos de las descomposiciones de ujo para obtener una nueva descomposición de ujo unicada. 1 2 3 4 P1 Q1 P2 Q2 Q3P3 (a) Representación de los dos aumentos. 1 2 3 4 P1 Q1 Q3P3 (b) Efecto neto de los aumentos. Figura 4.9: Descomposición de ujo unicada. 4.4. ALGORITMO DE ETIQUETADO 41 4.4. Algoritmo de etiquetado En la sección anterior no hemos mencionado ningún procedimiento concreto para identicar las trayectorias aumentadas ni se ha comprobado que, cuando el algoritmo termina en un número nito de operaciones, la solución obtenida es efectivamente un ujo máximo. Por ello, esta sección está pensada para abordar dichas cuestiones sobre el algoritmo de etiquetado , que no es más que una implementación especíca del algoritmo genérico de trayectorias aumentadas que acabamos de ver. El algoritmo de etiquetado se apoya en las técnicas de búsqueda vistas en la Sección 3.3 para identicar, en la red residual, las diferentes trayectorias aumentadas. La idea general del algoritmo consiste en, partiendo del nodo fuente, s , desplazarse a través de caminos dirigidos para identicar aquellos nodos que pueden ser alcanzados desde la fuente. Es por ello que dene dos grupos: el conjunto de nodos etiquetados y el conjunto de nodos no etiquetados . Los nodos etiquetados son aquellos que se han alcanzado a través de la búsqueda realizada por el algoritmo, es decir, aquellos para los que existe un camino dirigido desde la fuente en la red residual. Por contra, el conjunto de nodos no etiquetados está formado por aquellos nodos a los que el algoritmo no ha llegado todavía. El proceso realizado por el algoritmo es muy simple: de manera iterativa, el algoritmo selecciona un nodo etiquetado y analiza su lista de adyacencia en la red residual con el n de alcanzar, y por tanto etiquetar, nuevos nodos. Cuando el algoritmo llega a etiquetar el sumidero, se envía la mayor cantidad de ujo posible a lo largo del camino empleado para llegar al nodo t , el cual se reconstruye gracias al uso de los predecesores, y se actualizan las capacidades residuales. Seguidamente, desetiqueta todos los nodos y vuelve a empezar el proceso para la nueva red residual. El algoritmo termina cuando ya se han analizado todos los nodos etiquetados y el sumidero se mantiene sin etiquetar. Ilustración del algoritmo Antes de continuar vamos a ver como el algoritmo de etiquetado resolvería, paso a paso, el problema del ujo máximo para un ejemplo particular. Consideramos la red residual R(f) de la Figura 4.10 asociada al ujo f=0 . 42 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS Algoritmo 2: Algoritmo de etiquetado. inicio Etiquetar el nodo t ; mientras t esté etiquetado hacer inicio Desetiquetar todos los nodos; Establecer pred( j )=0 para todo j∈N ; Etiquetar s y jar LISTA:={ s }; mientras LISTA 6=∅ y t no esté etiquetado hacer inicio Seleccionar y retirar el nodo i de LISTA con índice más pequeño; para cada arco (i, j) en R(f) con i como nodo de inicio hacer si el nodo j no está etiquetado entonces pred( j )= i ; Etiquetar el nodo j ; Añadir j a LISTA; n n n n si t está etiquetado entonces Ejecutar aumento (ver Algoritmo 3) n n n n Algoritmo 3: Aumento. inicio Haciendo uso de los predecesores reconstruir, desde el sumidero a la fuente, la trayectoria aumentada P ; δ= m´ın{rij : (i, j)∈P} ; Aumentar δ unidades de ujo a lo largo de P y actualizar las capacidades residuales; n 4.4. ALGORITMO DE ETIQUETADO 43 s 2 3 4 t 2 4 3 1 1 2 Figura 4.10: Ilustración algoritmo de etiquetado. PRIMERA ITERACIÓN: Etiquetamos el nodo t ; Desetiquetamos todos los nodos; pred(j)=0 ∀j∈N ; Nodos etiquetados={ s }; LISTA={ s }; Eliminamos un nodo de LISTA, en este caso s por ser el único. LISTA= ∅ ; Los arcos (s, 2),(s, 3) ∈A(s) y los nodos 2 y 3 no están etiquetados; Nodos etiquetados={ s , 2, 3}; pred(2)=pred(3)= s ; LISTA={2, 3}; Eliminamos el nodo 2 de LISTA por ser el de índice menor. LISTA={3}; El arco (2, t)∈A(2) y t no está etiquetado; Nodos etiquetados={ s , 2, 3, t }; pred( t )=2; LISTA={3, t } Como t está etiquetado, ejecutamos aumento : Tenemos pred( t )=2 y pred(2)= s ; P={(s, 2),(2, t)} , cuya capacidad residual es δ= m´ın{2,3}= 2 ; Aumentamos 2 unidades de ujo a lo largo de P , con lo que F=δ= 2 . Actualizamos la red residual. 50 CAPÍTULO 4. ALGORITMO DE TRAYECTORIAS AUMENTADAS termina, sin embargo, se obtienen una sucesión de valores del ujo que resulta convergente. Así a todo, siempre converge a un valor estrictamente menor al valor del ujo máximo. Notar, sin embargo, que el Teorema max-ow min-cut se verica incluso si las capacidades son irracionales. Por último, un tercer inconveniente del algoritmo de etiquetado viene dado por el hecho de que cuando se naliza una iteración las etiquetas generadas son eliminadas, perdiéndose así una gran cantidad de información que podría ser reciclada para las siguientes iteraciones. Por tanto, lo ideal sería mantener dichas etiquetas para ahorrarnos el coste computacional que supone volver a empezar la búsqueda de los nodos etiquetados. En el siguiente capítulo presentamos variantes del algoritmo de trayectorias aumentadas que tratan de subsanar las debilidades del algoritmo de etiquetado que acabamos de comentar. Capítulo 5 Mejoras del algoritmo Este último capítulo se centra en ver cómo aplicando pequeñas variantes al algoritmo de trayectorias aumentadas, utilizando recursos denidos a lo largo de esta memoria, se consiguen subsanar las principales debilidades del algoritmo de etiquetado además de ir mejorando con cada uno de ellos el tiempo de resolución empleado. Para el desarrollo de estos, hemos tomado como referencia la Sección 7.3 y la Sección 7.4 del libro Ahuja et al. (1993). Como nalización, ilustraremos brevemente una familia de algoritmos con una losofía distinta a la construcción de trayectorias aumentadas y que no sufre algunas de las debilidades de estos últimos. Para esto tomaremos como referencia la Sección 7.6 del libro antes mencionado. 5.1. Algoritmo de trayectorias aumentadas de máxima capacidad A continuación presentamos informalmente el algoritmo de trayectorias aumentadas de máxima capacidad, en cuya idea se apoya el algoritmo de escalado de capacidades que veremos en la Sección 5.2 y que puede verse como una implementación eciente de la misma. El algoritmo de trayectorias aumentadas de máxima capacidad proporciona un método para escoger de una forma más eciente los caminos dirigidos entre la fuente y el sumidero, mejorando así los tiempos de ejecución para el algoritmo de etiquetado. Partiendo de una red residual, el algoritmo identica todas las trayectorias aumentadas entre la fuente y el sumidero y calcula sus respectivas capacidades residuales. Una vez tiene todos los valores, realizará el envío de ujo sobre aquel camino que posea la mayor capacidad residual. Observemos que utilizando este algoritmo resolveríamos el ejemplo 51 52 CAPÍTULO 5. MEJORAS DEL ALGORITMO dado en la Figura 4.11 en 2 iteraciones pues se escogería o el camino 1−2−4 o el camino 1−3−4 en primer lugar. Si F es el valor del ujo máximo, dado un ujo f∗ con valor F∗ , se pueden encontrar como mucho m caminos dirigidos en R(f∗) desde la fuente al sumidero de modo que la suma de todas las capacidades residuales sea (F−F∗) . Esto es así puesto que cada vez que enviamos ujo a lo largo de una trayectoria estamos saturando al menos una arista de la red residual, con lo que después de realizar, como mucho, m trayectorias deberíamos haber sido capaces de enviar el ujo máximo entre la fuente y el sumidero 1 . Pero entonces, como aún se pueden enviar (F−F∗) unidades de ujo a lo largo de la red, la trayectoria de máxima capacidad debe tener una capacidad residual de al menos (F−F∗) m unidades. Supongamos ahora que tenemos 2m aumentos consecutivos de máxima capacidad en la red R(f∗) . Si para todos los aumentos se envían al menos (F−F∗) 2m unidades de ujo, habremos alcanzado el valor del ujo máximo al nalizarse dichos aumentos, y puede que incluso antes. Por otro lado, si tuviésemos un aumento con menos de (F−F∗) 2m unidades de ujo, esto supondría que se ha reducido la capacidad residual de la trayectoria de máxima capacidad por un factor de al menos 2. Sabemos que para reducir un valor U a una unidad mediante el uso de un factor 2 necesitaremos log2U unidades. Como la capacidad residual de cualquier trayectoria aumentada siempre está entre 1 y 2U unidades (recordemos que U es la cota para las capacidades de los arcos), después de O(mlog2U) iteraciones el ujo obtenido debe ser máximo. Hemos conseguido, por tanto, reducir el tiempo del algoritmo de etiquetado a un tiempo O(mlog2U) . Pese a esto, debemos tener en cuenta que el algoritmo de trayectorias aumentadas de máxima capacidad necesita un trabajo adicional en cada ejecución, pues debe identicar la trayectoria aumentada con mayor capacidad. A continuación presentamos un algoritmo que se apoya en esta idea para conseguir mejorar la eciencia computacional del algoritmo de etiquetado. 5.2. Algoritmo de escalado de capacidades El algoritmo de escalado de capacidades es una mejora computacional del algoritmo de trayectorias aumentadas de máxima capacidad para eliminar el coste que supone el identicar todas las trayectorias aumentadas en la red residual. La idea del algoritmo se basa en que solamente se enviará ujo por aquellas trayectorias 1 Para demostrar formalmente esta idea habría que tener algo de cuidado con el hecho de que una trayectoria puede liberar capacidad en un arco saturado en alguna trayectoria anterior. La demostración formal que nos garantiza que con m trayectorias siempre será suciente se puede ver en el Teorema 3.5 del libro Ahuja et al. (1993). 5.2. ALGORITMO DE ESCALADO DE CAPACIDADES 53 aumentadas cuyas capacidades residuales sean lo sucientemente grandes, es decir, dado un parámetro ∆ , solo trabajaremos con aquellas trayectorias que tengan una capacidad residual igual o superior a ∆ . Este parámetro se podrá actualizar, y por tanto disminuir, cuando no exista ninguna trayectoria que verique estas condiciones. Partiendo de una red residual R(f) denimos la red ∆ -residual , R(f,∆) , como la red resultante tras seleccionar aquellos arcos de R(f) cuya capacidad residual es mayor o igual que ∆ . Nótese que en el caso ∆=1 la red residual coincide con la red ∆ -residual. Estas nuevas redes serán las que sustituirán a la red residual habitual en el algoritmo de escalado de capacidades. 1 2 3 4 5 6 4 2 21 6 1 4 3 7 5 (a) Red residual para un ujo f . 1 2 3 4 5 6 4 6 4 3 7 5 (b) Red ∆ -residual para ∆ = 3 . Figura 5.1: Ejemplo de una red ∆ -residual. El conjunto de iteraciones del algoritmo en las que ∆ permanece constante forman lo que se conoce como una fase de escala . Si además queremos especicar en qué valor de ∆ nos encontramos diremos que es una fase de ∆ -escala . Observemos que en una fase de ∆ -escala el algoritmo estará trabajando sobre la red R(f,∆) , por lo que si existe una trayectoria aumentada, su capacidad residual será de al menos ∆ unidades. El algoritmo comienza inicializando ∆ = 2blog2Uc y, tras nalizar una fase de escala, actualiza este valor a ∆ 2 hasta llegar a ∆=1 , que será la última iteración del algoritmo. Se realizarán, por lo tanto, 1 + blog2Uc=O(log2U) fases de escala. Como la última fase de escala se hace sobre la red R(f) , el algoritmo de etiquetado nos asegura que el resultado será un ujo máximo. 54 CAPÍTULO 5. MEJORAS DEL ALGORITMO Algoritmo 4: Algoritmo de escalado de capacidades. inicio f=0 ; ∆=2blog2Uc; mientras ∆≥1 hacer mientras R(f,∆) contenga una trayectoria aumentada hacer Identicar la trayectoria aumentada P en R(f,∆) ; δ= m´ın{rij : (i, j)∈P} ; Aumentar δ unidades de ujo a lo largo de P y actualizar R(f,∆) ; n ∆ = ∆ 2 ; n n Implementación del algoritmo Dada la siguiente red, resolveremos el problema del ujo máximo mediante el algoritmo de escalado de capacidades: 1 2 3 4 5 6 7 20 35 32 41 37 17 37 32 13 11 40 Tomando U= 41 tenemos una cota superior para todas las capacidades de las aristas. PASO 1: Inicializamos f=0 . Además, ∆=2blog2Uc= 25= 32 . Obtenemos R(f,∆) : 5.2. ALGORITMO DE ESCALADO DE CAPACIDADES 55 1 2 3 4 5 6 7 35 32 41 37 37 32 40 PASO 2: Como ∆≥1 , y existe un camino dirigido entre el nodo 1 y el nodo n : Identicamos la trayectoria aumentada P={(1,4),(4,6),(6,7)} cuya capacidad residual es δ= m´ın{35,32,40}= 32 . Aumentamos δ unidades de ujo a lo largo de P , con lo que F= 32 , y actualizamos la red ∆ -residual. 1 2 3 4 5 6 7 3 32 32 41 37 37 32 8 32 PASO 3: Como no existen trayectorias aumentadas de la fuente al sumidero, actualizamos ∆ = ∆ 2= 16 . Obtenemos la red ∆ -residual: 1 2 3 4 5 6 7 3 20 32 32 17 41 37 37 32 8 32 PASO 4: Como no existen trayectorias aumentadas de la fuente al sumidero, volvemos a actualizar ∆ = ∆ 2= 8 . Obtenemos la red ∆ -residual: 56 CAPÍTULO 5. MEJORAS DEL ALGORITMO 1 2 3 4 5 6 7 3 20 32 32 17 11 41 37 37 32 8 32 13 PASO 5: Tenemos ∆≥1 y un camino dirigido entre la fuente y el sumidero: Identicamos P={(1,2),(2,5),(5,7)} cuya capacidad residual es δ= m´ın{20,41,13}= 13 . Aumentamos δ unidades de ujo a lo largo de P , así F= 32 + 13 = 45 , y actualizamos la red ∆ -residual: 1 2 3 4 5 6 7 3 713 32 32 17 11 28 13 37 37 32 8 32 13 PASO 6: Como no existen caminos dirigidos desde la fuente al sumidero, actualizamos ∆ = ∆ 2= 4 y obtenemos la red ∆ -residual: 1 2 3 4 5 6 7 3 713 32 32 17 11 28 13 37 37 32 8 32 13 PASO 6: Como todavía no existen caminos dirigidos desde la fuente al sumidero, actualizamos ∆ = ∆ 2= 2 y obtenemos la red ∆ -residual R(f,2) = R(f,4) . PASO 7: Nuevamente, como no se ha añadido ningún arco en la iteración anterior, sigue sin existir una trayectoria aumentada, con lo que actualizamos ∆ = ∆ 2= 1 . Esta 5.3. ALGORITMO DE TRAYECTORIAS AUMENTADAS MÁS CORTAS 57 actualización no nos proporciona ningún arco nuevo tampoco, luego R(f,1) = R(f,2) . PASO 8: Obviamente, sigue sin haber trayectorias aumentadas de la fuente al sumidero. Actualizamos ∆ = ∆ 2=1 2 . Como ∆<1 , el algoritmo naliza. Devuelve que el valor del ujo máximo es F= 45 asociado a f14 =f46 =f47 = 32 y f12 =f25 =f57 = 13 . 5.2.1. Complejidad del algoritmo Para analizar la eciencia del algoritmo, nos queda por determinar cuántos aumentos se realizarán por cada fase de escala. Veamos que, como mucho, se realizarán 2m aumentos: Supongamos que obtenemos un ujo f0 al nalizar una fase de ∆ -escala cuyo valor es F0 . Sea S el conjunto formado por todos los nodos que son alcanzables desde la fuente en R(f0,∆) y S=N−S . Puesto que la fase ha acabado, no existen trayectorias aumentadas desde la fuente al sumidero en dicha red, luego t∈S y (S, S) dene un corte s−t . Por denición de S sabemos que la capacidad residual de los arcos en (S, S) es menor estrictamente que ∆ , por lo que la capacidad del conjunto de corte no superará el valor m∆ . Si suponemos que F es el valor del ujo máximo, por el Lema 2.1 tenemos que F−F0≤m∆ = U(S, S) . Por otra parte, la siguiente fase de escala será la fase de ∆ 2 - escala, luego cada trayectoria aumentada en R(f0,∆ 2) tendrá como mínimo una capacidad residual de ∆ 2 unidades, lo que supone que no se podrán realizar más de 2m aumentos. Como estamos escogiendo un ∆ arbitrario, podemos concluir que para toda fase de ∆ -escala se realizarán como mucho 2m aumentos. Hemos visto en el algoritmo de etiquetado que se requiere un tiempo de O(m) para identicar una trayectoria aumentada, luego para cada actualización de la red ∆ -residual se requiere también un tiempo O(m) . Podemos deducir, por lo tanto, el siguiente resultado: Proposición 5.1. El algoritmo de escalado de capacidades resuelve el problema de ujo máximo después de O(mlog2U) aumentos en un tiempo O(m2log2U) . 5.3. Algoritmo de trayectorias aumentadas más cortas El algoritmo de trayectorias aumentadas más cortas se basa en enviar ujo a lo largo de aquellas trayectorias aumentadas que tengan longitud mínima, es decir, a lo largo de aquellos caminos entre la fuente y el sumidero formados por la menor cantidad de arcos posibles. Para identicar los caminos de longitud mínima el algoritmo realiza un primer análisis de la red residual para asociar, posteriormente, una etiqueta de distancia válida a cada nodo de la red. A raíz de estos valores se crearán caminos admisibles entre la fuente y el sumidero a través de los cuales incrementaremos el envío de ujo. Recordemos que un 58 CAPÍTULO 5. MEJORAS DEL ALGORITMO camino se dice que es admisible cuando todos los arcos que lo componen son admisibles, es decir, si se verica d(i) = d(j)+1 para todo arco (i, j) perteneciente al camino. Con el n de alcanzar el sumidero a través de un camino admisible, el algoritmo irá creando un camino admisible parcial desde la fuente a un nodo i , denominado nodo actual , i6=t , al que, iterativamente, le aplica operaciones o bien de avance o bien de retroceso . En el caso de que exista un arco (i, j) admisible realiza una operación de avance añadiendo el arco (i, j) a nuestro camino parcial; en caso contrario, realiza un retroceso eliminando el arco (k, i) que pertenece al camino y un reetiquetado que consistirá en aumentar el valor de la etiqueta de distancia asociada al nodo i . Este proceso se repetirá hasta que alcancemos el sumidero que es cuando haremos el aumento de ujo. Puesto que, como sabemos, la distancia mínima entre un nodo arbitrario de la red y el sumidero es monótona creciente tras realizar un aumento, explotando esta propiedad se consigue reducir el tiempo promedio de cada aumento de O(m) a O(n) . Ilustración del algoritmo Antes de ilustrar cómo trabaja el algoritmo notemos que, por convención, si tenemos dos arcos admisibles (i, j) y (i, k) , siempre seleccionaremos aquel cuyo índice sea más pequeño. Procedemos, por tanto, a resolver el problema de ujo máximo para un ejemplo particular mediante el algoritmo de trayectorias aumentadas más cortas descrito en el Algoritmo 5. Consideremos la siguiente red con ujo donde el nodo 1 será la fuente y el nodo 8 el sumidero: 1 2 3 4 5 6 7 8 (0,3) (0,1) (0,1) (0,1) (0,2) (0,1) (0,1) (0,4) (0,1) PRIMERA ITERACIÓN: f=0 ; Se obtienen las etiquetas de distancia válidas d(i) para la red R(f) ; (ver Figura 5.2) 5.3. ALGORITMO DE TRAYECTORIAS AUMENTADAS MÁS CORTAS 59 i=s ; Como d(s)<8 y s tiene arcos admisibles en R(f) , ejecutamos avance( s ) : Escogemos el arco admisible (1,2) ∈A(i) ; pred(2)=1; i=2; 1 3 2 2 3 2 4 2 5 1 6 1 7 1 8 0 d(i) ij d(j) rij 3 1 1 1 2 1 1 4 1 Figura 5.2: Red residual con etiquetas de distancia. SEGUNDA ITERACIÓN: Como d(s)<8 puesto que no se ha actualizado, y el nodo 2 tiene un arco admisible, ejecutamos avance(2) : El arco (2,5) ∈A(2) es el único arco admisible; pred(5)=2; i=5; TERCERA ITERACIÓN: Como d(s)<8 , y el nodo 5 tiene un arco admisible, ejecutamos avance(5) : El arco (5,8) ∈A(5) es el único arco admisible; pred(8)=5; i=8; 66 CAPÍTULO 5. MEJORAS DEL ALGORITMO 1 2 2 3 3 1 4 4 3 1 7 Supongamos que la gura anterior nos muestra la lista de adyacencia del nodo 1. Entonces, el algoritmo comienza seleccionando el arco (1,2) como el arco actual y comprueba si se trata de un arco admisible. En este caso no es un arco admisible pues d(1) 6=d(2) + 1 por lo que, para poder continuar con el algoritmo, se actualiza la elección del arco actual al siguiente arco en la lista de adyacencia, es decir, el arco (1,3) , que si que resulta ser admisible. Si se diera el caso de que el algoritmo analizase toda la lista de adyacencia y no encontrara ningún arco admisible, entonces se realizaría un reetiquetado del nodo 1 y el algoritmo volvería a comprobar, uno a uno, cada arco de la lista de adyacencia. Cada vez que el algoritmo necesita hacer un reetiquetado del nodo i debe sustraer las etiquetas de distancia para todos aquellos nodos j tales que (i, j)∈A(i) , luego el tiempo empleado en un reetiquetado coincide con el tiempo empleado en identicar los arcos admisibles. Podemos deducir, por tanto, el siguiente resultado: Proposición 5.3. Si el algoritmo reetiqueta un nodo como mucho k veces, entonces el tiempo total que se necesita para encontrar arcos admisibles y reetiquetar los nodos es O(kPi∈N|A(i)|) = O(km) . Otro de los resultados en los que nos apoyaremos para deducir la complejidad del algoritmo de trayectorias aumentadas más cortas es el que anunciamos a continuación. Lema 5.4. Si el algoritmo reetiqueta un nodo a lo sumo k veces, el algoritmo satura arcos en la red residual (es decir, reduce su capacidad residual a cero) como mucho km veces. Demostración. La base de la demostración se basa en ver que dadas dos saturaciones consecutivas del arco (i, j) , tanto d(i) como d(j) aumentan su valor al menos 2 unidades. Si esto es cierto, como por hipótesis el algoritmo aumenta cada etiqueta a lo sumo k veces, entonces el algoritmo podría saturar el arco como mucho k veces.Así, se realizarían como mucho km saturaciones en la red residual. Supongamos, por tanto, que tenemos un aumento que satura el arco (i, j) . Como este arco 5.3. ALGORITMO DE TRAYECTORIAS AUMENTADAS MÁS CORTAS 67 es admisible, se satisface que d(i) = d(j)+1. Para que el arco (i, j) pueda volver a ser saturado, es necesario que antes exista un envío de ujo a lo largo del arco (j, i) pero entonces, por ser (j, i) un arco admisible, las nuevas etiquetas de distancia deben vericar que d0(j) = d0(i)+1. Análogamente, si ahora se satura el arco (i, j) de nuevo, tenemos d00(i) = d00(j)+1. Por el Lema 5.2 sabemos que un reetiquetado aumenta el valor de la etiqueta de distancia del nodo, con lo que tenemos las siguientes desigualdades: d00(i) = d00(j)+1≥d0(j) + 1 = d0(i)+2≥d(i)+2, d00(j) = d00(i)−1≥d(i) + 1 = d(j)+2. Obtenemos, por tanto, que dos saturaciones consecutivas del arco (i, j) implican que las etiquetas d(i) y d(j) aumenten su valor en al menos dos unidades. Lema 5.5. (a) En el algoritmo de trayectorias aumentadas más cortas cada etiqueta de distancia aumenta su valor como mucho n veces. Por tanto, en total se tendrán como mucho n2 reetiquetados. (b) El número de aumentos es como mucho nm . Demostración. En cada reetiquetado el valor de la etiqueta de distancia aumenta como mínimo una unidad, por lo que después de n reetiquetados tendríamos que d(i)≥n . Esto supone que el algoritmo nunca volverá a seleccionar el nodo i para realizar un avance, pues para todo nodo k perteneciente al camino admisible parcial se tiene que d(k)< d(s)< n . Podemos concluir por lo tanto que el algoritmo reetiquetará cada nodo un máximo de n veces, realizando así como mucho n2 reetiquetados. Por el lema anterior, y dado que acabamos de probar que el algoritmo reetiqueta un nodo a lo sumo n veces, tenemos que se saturarán como mucho nm arcos. Además, por denición, cada aumento satura al menos un arco, luego nm es una cota para el número total de aumentos en la red. 68 CAPÍTULO 5. MEJORAS DEL ALGORITMO Combinando los resultados vistos en la Proposición 5.3 con los del Lema 5.5 se tiene que el tiempo necesario para encontrar los arcos admisibles en la red residual y el tiempo empleado en reetiquetar los nodos son ambos O(nm) . Por otra parte, el Lema 5.5 también nos dice que el número total de reetiquetados, o lo que es lo mismo, de retrocesos, será O(n2) y que se realizarán como mucho O(nm) aumentos, lo que supone un tiempo total de O(n2m) para los aumentos. Teniendo en cuenta ahora que cada avance añade un arco al camino parcial admisible y que cada retroceso lo elimina, puesto que toda trayectoria aumentada tiene a lo sumo longitud n , necesitaremos realizar como mucho n avances limpios (sin ningún retroceso) para alcanzar el sumidero y poder realizar un aumento. Además debemos compensar con los avances los retrocesos realizados, con lo que necesitaremos O(n2+n2m) avances. Obtenemos, por lo tanto, que la suma de todas las operaciones de los distintos tipos nos proporciona un orden O(n2+n2m) o, lo que es equivalente, O(n2m) . 5.3.3. Mejora práctica Como ya hemos visto, el algoritmo de trayectorias aumentadas más cortas no termina hasta que d(s)≥n . A pesar de que este criterio es aceptable para el análisis del peor caso, puede suponer un coste computacional elevado cuando el ujo máximo ya se ha alcanzado en pocas iteraciones. El problema reside en que el algoritmo no es capaz de saber si se ha alcanzado un ujo máximo, con lo la nalidad de este apartado será el desarrollar una técnica que nos permita identicar un corte de capacidad mínima en la red. 1 3 2 4 3 2 4 2 5 1 6 1 7 1 8 0 21 1 1 1 1 1 1 1 3 1 1 Figura 5.3: Red residual tras el último aumento. Consideramos la red residual resultante tras ejecutar el último aumento en la ilustración del algoritmo de trayectorias aumentadas más cortas. Como podemos observar, esta red no posee ningún camino dirigido entre la fuente y el sumidero, lo cual implica que no se 5.4. ALGORITMO DE ESCALADO DE CAPACIDADES CON CAMINOS MÁS CORTOS 69 podrá mandar ujo adicional entre estos nodos y que, por tanto, tenemos un ujo máximo. Para que el algoritmo sea capaz de identicar este hecho y nalizar sin necesidad de hacer más iteraciones, creamos un vector n -dimensional, numb , tal que cada entrada numb(k) reejará el número de nodos de la red cuya etiqueta de distancia tenga el valor k . Para nuestro ejemplo, ver Figura 5.2, el vector se inicializaría con los valores numb(0) = 1 , numb(1) = 3 , numb(2) = 3 , numb(3) = 1 y el resto de entradas serían cero. Cuando el algoritmo realice un reetiquetado y una etiqueta pase de un valor k1 a un valor k2 , el valor de numb(k1) disminuirá una unidad para aumentar en esa misma unidad el valor de numb(k2) . Si numb(k1) =0, el algoritmo naliza asegurando que ya se ha alcanzado el ujo máximo para la red. Si aplicamos este criterio sobre la Figura 5.3, como el nodo 1 no posee arcos admisibles, se aumenta el valor de su etiqueta de distancia de 3 a 5 unidades y se obtiene numb(3) = 0 y numb(5) = 1 , lo cual nalizaría el algoritmo. Para argumentar por qué esto funciona, consideramos los subconjuntos de N denidos como S={i∈N:d(i)> k1} y S={i∈N:d(i)< k1} . Es fácil ver que s∈S y t∈S , con lo que tenemos un corte s−t tal que d(i)> d(j)+1 para todo (i, j)∈(S, S) . Como las etiquetas de distancia son válidas, deben vericar las condiciones de validación, en particular, deben vericar que d(i)≤d(j)+1 para todo (i, j)∈R(f,∆) con rij >0 , por lo que deducimos que rij = 0 para todo (i, j)∈(S, S) . Es decir, hemos encontrado un corte s−t en la red residual cuya capacidad es 0, luego es un corte de capacidad mínima y el valor de ujo máximo sobre esta red también será 0. En otras palabras, no es posible enviar más unidades de ujo a lo largo de la red residual R(f) , por lo que f será un ujo máximo para la red original. 5.4. Algoritmo de escalado de capacidades con caminos más cortos En la Sección 5.2 hemos desarrollado el algoritmo de escalado de capacidades capaz de resolver el problema de ujo máximo en un tiempo O(m2log2U) . Ahora bien, veamos se puede mejorar el rendimiento de dicho algoritmo si introducimos las ideas del algoritmo de trayectorias aumentadas más cortas. Este nuevo algoritmo combinado consistirá en aumentar ujo a lo largo de los caminos de longitud mínima entre la fuente y el sumidero en la red R(f,∆) . Dichos caminos serán identicados por medio de las etiquetas de distancia de igual forma que se hacía para el algoritmo de trayectorias aumentadas más cortas. Recordemos que el algoritmo de escalado de capacidades realizaba O(log2U) fases de escala y en cada una de ellas necesitaba O(m) aumentos. Por el análisis de complejidad 70 CAPÍTULO 5. MEJORAS DEL ALGORITMO visto para el algoritmo de trayectorias aumentadas más cortas, para O(m) aumentos se requiere un tiempo O(mn) . Como el resto de operaciones no sen ven afectadas con esta modicación del algoritmo mantienen un tiempo O(nm) , con lo que podemos concluir que este nuevo algoritmo, al que denominaremos algoritmo de escalado de capacidades con caminos más cortos tendrá un tiempo de ejecución O(nm log2U) . 5.5. Algoritmo preow-push Para nalizar este capítulo ilustraremos cuál es la losofía detrás del algoritmo genérico preow-push . Supongamos que tenemos el siguiente caso extremo: ij rij 1234 5 6 7 8 ∞∞∞ 1 1 1 1 1 1 Utilizando cualquier algoritmo de trayectorias aumentadas tendríamos que identicar los tres caminos de longitud cinco de la red y enviar a través de cada uno de ellos una unidad de ujo. Sin embargo, puesto que en todos los aumentos se repiten las tres primeras aristas, el algoritmo estará identicando y recorriendo el camino entre el nodo 1 y el nodo 4 tres veces. El algoritmo preow-push pretende evitar esta situación teniendo en cuenta que si se enviaran 3 unidades de ujo del nodo 1 al nodo 4 y después se distribuyeran entre los tres caminos de longitud dos, el algoritmo se ahorraría el coste computacional derivado de repetir los arcos. El algoritmo preow-push consiste en enviar ujo a lo largo de arcos admisibles, en lugar de por una trayectoria aumentada completa. Este hecho podría propiciar que en algún nodo intermedio entre más cantidad de ujo de la que puede salir, es decir, tendremos nodos con exceso de ujo, e(i)>0 . La presencia de estos nodos, sin embargo, indica que el ujo no es factible para el problema puesto que no se verican la condición de conservación de ujo en los nodos intermedios. El algoritmo, por tanto, identicará un nodo i con exceso y distribuirá dicha cantidad de ujo sobrante entre aquellos nodos adyacentes al mismo para los que exista un arco (i, j) admisible. El algoritmo nalizará cuando no existan nodos intermedios con exceso de ujo. 5.5. ALGORITMO PREFLOW-PUSH 71 Nótese que si realizamos un envío de δ unidades desde el nodo i al nodo j , tanto e(i) como rij disminuyen su valor δ unidades, mientras que e(j) y rji aumentan tales unidades. Consideremos el ejemplo dado en la Figura 5.4. Vamos a describir sobre la red inicial, Figura 5.4(a), los pasos que realizaría el algoritmo preow-push para resolver el problema de ujo máximo: Primeramente, el algoritmo proporciona a todos los nodos adyacentes a la fuente un exceso positivo, es decir, satura todos los arcos (1, j) de la red, consiguiendo así que e(j) = r1j . Además, como el nodo 1 ya no posee arcos admisibles, ja d(1) = n= 4 (ver Figura 5.4(b)). Supongamos que el algoritmo selecciona el nodo 2 por tener exceso de ujo. Entonces, como el arco (2,4) es admisible, envía δ= m´ın{e(2), r24}= 2 unidades de ujo a través del mismo, con lo que se actualizan los valores e(2) = e(2) −δ= 0 y e(4) = e(4) + δ= 2 (ver Figura 5.4(c)). El algoritmo selecciona el nodo 3 por ser el único con exceso positivo. Como el arco (3,4) es admisible, mandamos δ= m´ın{e(3), r34}= 2 unidades de ujo por este arco y actualizamos los excesos e(3) = e(3) −δ= 1 y e(4) = e(4) + δ= 4 (ver Figura 5.4(d)). Puesto que el nodo 3 posee exceso de ujo pero no arcos admisibles, aumentamos el valor de su etiqueta de distancia, d(3) = m´ın{d(j) : (3, j)∈A(3), rij >0}= 5 (ver Figura 5.4(e)). El algoritmo vuelve a seleccionar el nodo 3 por tener exceso de ujo, e identica el arco admisible (3,1) . Aumenta δ= m´ın{e(3), r31}= 1 unidades de ujo a lo largo del arco y actualiza e(3) = e(3) −δ= 0 y e(1) = e(1) −δ=−1 (ver Figura 5.4(f)). Como la red residual ya no posee nodos intermedios con exceso de ujo, el algoritmo naliza y el valor del ujo máximo será e(4) = 4 . Cuando el algoritmo termina el ujo obtenido es un ujo factible pues se verican las condiciones de conservación de ujo para los nodos intermedios. Además, como en la primera iteración hemos jado d(s) = n , la Proposición 3.3 nos asegura que no existe ningún camino dirigido de la fuente al sumidero, con lo que estamos ante un ujo máximo. Por último, vamos a ver una interpretación física del algoritmo preow-push: Supongamos que los arcos están representando trozos de tuberías, los nodos, intersecciones de tuberías y la función distancia mide la longitud, en número de nodos, entre el nodo actual y el suelo. La idea consiste en crear una tubería que conecte la fuente y el sumidero. 72 CAPÍTULO 5. MEJORAS DEL ALGORITMO 1 e(1) = 0 d(1) = 2 2 e(2) = 0 d(2) = 1 3 e(3) = 0 d(3) = 1 4 e(4) = 0 d(4) = 0 2 3 1 2 2 (a) 1 e(1) = 0 d(1) = 4 2 e(2) = 2 d(2) = 1 3 e(3) = 3 d(3) = 1 4 e(4) = 0 d(4) = 0 2 3 1 2 2 (b) 1 e(1) = 0 d(1) = 4 2 e(2) = 0 d(2) = 1 3 e(3) = 3 d(3) = 1 4 e(4) = 2 d(4) = 0 2 3 1 2 2 (c) 1 e(1) = 0 d(1) = 4 2 e(2) = 0 d(2) = 1 3 e(3) = 1 d(3) = 1 4 e(4) = 4 d(4) = 0 2 3 1 2 2 (d) 1 e(1) = 0 d(1) = 4 2 e(2) = 0 d(2) = 1 3 e(3) = 1 d(3) = 5 4 e(4) = 4 d(4) = 0 2 3 1 2 2 (e) 1 e(1) = −1 d(1) = 4 2 e(2) = 0 d(2) = 1 3 e(3) = 0 d(3) = 5 4 e(4) = 4 d(4) = 0 2 2 2 1 2 2 (f) Figura 5.4: Ilustración del algoritmo preow-push. 5.5. ALGORITMO PREFLOW-PUSH 73 Para ello, inundamos todas las tuberías que conectan con la fuente. Si conseguimos que el agua uya hacia el sumidero (lo cual se corresponde con que un arco sea admisible para el algoritmo) será porque existe una intersección a la que acoplar nuestra tubería que se encuentra por debajo de la misma. En caso de que el agua no uya en una intersección, levantaremos dicha intersección hasta conseguir que se retome la bajada de agua. Debemos notar que si continuamos levantando las intersecciones podríamos provocar que el exceso de agua volviera a la fuente. Por tanto, podrían darse dos escenarios: que consigamos crear la tubería y llegue agua al sumidero, o que el agua vuelva hacia la fuente. En cualquiera de estos casos, el algoritmo nalizaría. Para las variantes más ecientes de la familia de algoritmos preow-push se tienen una complejidad computacional de O(n2√m) y O(nm +n2log2U) , las cuales mejoran la complejidad O(n2m) del algoritmo de trayectorias más cortas aumentadas y la complejidad O(m2log2U) del algoritmo de escalado de capacidades, respectivamente. 74 CAPÍTULO 5. MEJORAS DEL ALGORITMO Bibliografía Ahuja, R. K., T. L. Magnanti, and J. B. Orlin (1993): Network Flows: Theory, Algorithms, and Applications. , Prentice Hall. Julio González Díaz (2018-2019): Programación Lineal y Entera . 75