Problemas de emparejamiento

Traballo Fin de Grao Problemas de emparejamiento Estela Vázquez-Monjardín Lorenzo 2018/2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Problemas de emparejamiento Estela Vázquez-Monjardín Lorenzo Setembro, 2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estadística e Investigación Operativa Título: Problemas de emparejamiento Breve descrición do contido El objetivo de este trabajo es que el alumno se familiarice con una importante clase de problemas de programación lineal y entera: los problemas de emparejamiento. Se trata de una clase de problemas que engloban, como caso particular, al problema de asignación, visto en la asignatura de Programación Lineal y Entera. El alumno deberá familiarizarse bien con los distintos problemas de emparejamiento, y también con las similitudes y diferencias entre ellos que requerirán el uso de unas u otras técnicas de resolución. iii Índice general Resumen viii Introducción xi 1. Repaso 1 1.1. Introducción a la teoría de grafos y redes con flujo .............. 1 1.2. El problema de flujo en redes a coste mínimo (PFCM) ............ 5 1.2.1. Casos particulares del PFCM ...................... 6 1.2.2. PFCM con variables enteras: Unimodularidad ............. 9 1.3. Dualidad en problemas de optimización en redes ............... 10 1.4. Complejidad computacional ........................... 13 2. Preliminares 17 2.1. Transformaciones de redes ............................ 17 2.1.1. Eliminando las cotas inferiores no nulas ................ 17 2.1.2. Trabajando con costes reducidos .................... 18 2.1.3. Convirtiendo una red general en una red simple ............ 19 2.1.4. Trabajando con redes residuales ..................... 20 2.2. Emparejamientos, caminos aumentadores y flores ............... 22 2.3. Algoritmos de búsqueda ............................. 28 2.3.1. Algoritmo de búsqueda de caminos aumentadores ........... 30 2.4. Algoritmo de caminos más cortos sucesivos para el PFCM .......... 32 2.4.1. Ejemplo de resolución .......................... 35 3. El problema del flujo máximo 37 3.1. Algoritmo de trayectorias aumentadas (Ford-Fulkerson) ........... 38 3.1.1. Ejemplo de resolución .......................... 39 3.2. PFM en redes con capacidades unitarias .................... 41 v vi ÍNDICE GENERAL 3.2.1. Algoritmo de etiquetado ......................... 42 3.2.2. Algoritmo de trayectorias aumentadas más cortas ........... 47 3.2.3. Algoritmo del flujo máximo para capacidades unitarias ........ 51 4. El problema de emparejamiento bipartito 53 4.1. El problema bipartito de máxima cardinalidad ................. 53 4.1.1. Algoritmo para el emparejamiento bipartito de máxima cardinalidad 55 4.2. El problema bipartito ponderado ........................ 59 4.2.1. Algoritmo de caminos más cortos sucesivos .............. 60 4.2.2. El método húngaro ............................ 61 5. El problema de emparejamiento no bipartito 65 5.1. El problema no bipartito de máxima cardinalidad ............... 65 5.1.1. Algoritmo para el emparejamiento no bipartito de máxima cardinalidad 67 5.2. El problema no bipartito ponderado ...................... 73 A. Aplicaciones del problema de emparejamiento 75 A.1. Recableando máquinas de escribir ........................ 75 A.2. Asociando altavoces estéreo ........................... 76 A.3. Asignación de personal .............................. 77 A.4. El problema del camino más corto ....................... 78 Bibliografía 79 2CAPÍTULO 1. REPASO Grafos dirigidos uorientados: en este caso A⊆N×N, los arcos son pares ordenados de la forma (i, j), siendo iel nodo inicial y jel nodo final. 1 2 3 4 5 6 7 1 2 3 4 56 Figura 1.1: Ejemplos de grafos no dirigido y dirigido. Dos nodos iyjson adyacentes si el arco (i, j)(o el (j, i)) está presente en el grafo G. En este caso, se dice que iyjson incidentes en el arco (i, j)y que el arco (i, j) es incidente en los nodos iyj. Se define la lista de adyacencia de un nodo i, que denotamos por Ai, al conjunto de aristas que se originan en i, es decir, Ai={(i, j)∈A}. Nótese que en los grafos no dirigidos Aicoincide con el conjunto de arcos incidentes en i. Un grafo simple es aquel que solo admite un arco entre cada par de nodos. Por ejemplo, en la figura anterior el primer grafo es simple, mientras que el segundo no lo es. Un subgrafo de un grafo Ges un grafo G0= (N0, A0)que tiene todos sus arcos y nodos en G, es decir, N0⊆NyA0⊆A. Sea Gun grafo no dirigido y sea a1,→a2,→. . . ,→aruna secuencia de arcos distintos. Si existen nodos i0,→i1,→. . . ,→irtales que, para l∈ {1,2, . . . , r}, al= (il−1, il), decimos que la secuencia es una cadena. Podemos referirnos a la cadena tanto por la secuencia de arcos como por la secuencia de nodos que la forman. Además, existen varios tipos de cadenas: Cadena cerrada: es una cadena en la que i0=ir. Camino: es una cadena en la que todos los nodos son distintos. Circuito o ciclo: es una cadena cerrada en la que no hay más nodos coincidentes que el primero y el último. Un grafo es conexo si para cada par de vértices existe una cadena que los une. Un grafo se dice que es un árbol si es conexo y no contiene ciclos. Las definiciones que acabamos de presentar se pueden adaptar inmediatamente para grafos dirigidos. 1.1. INTRODUCCIÓN A LA TEORÍA DE GRAFOS Y REDES CON FLUJO 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Figura 1.2: Dos ejemplos de árboles. Dado un grafo dirigido G= (N, A), se dice que Ges un grafo bipartito si el conjunto de nodos se puede dividir en dos subconjuntos, N=N1∪N2, de manera que N1yN2son disjuntos y no vacíos. Además, si es dirigido, cada arco de Ase origina en N1y termina en N2, es decir, A⊆N1×N2. En la siguiente figura se muestran dos representaciones de un mismo grafo bipartito G= (N1∪N2, A), donde N1={1,2,3,4}yN2={5,6,7,8}. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Figura 1.3: Dos representaciones del mismo grafo bipartito. Para poder expresar problemas de optimización sobre grafos como problemas de programación lineal es conveniente que seamos capaces de resumir la información relativa a los grafos en forma de matrices. Sea G= (N, A)un grafo dirigido, este puede ser representado por su matriz de adyacencia (nodo-nodo) An×n, definida por: ¯aij =(1 si (i, j)es un arco de G 0 en otro caso. Otra posible representación matricial del grafo Ges a través de la matriz de incidencia (nodo-arco) Bn×m, definida por: ¯ bik =       1 si ies el nodo inicial del arco ak -1 si ies el nodo terminal del arco ak 0 en otro caso. 4CAPÍTULO 1. REPASO Por ejemplo, para el siguiente grafo se tienen las matrices de adyacencia e incidencia asociadas: 1 2 3 4 A=      0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0       ,B=      −1−1 0 0 0 1 0 −1−1 0 0110−1 00011       . Redes con flujo Una red es un grafo con uno o más números asociados a cada arco y/o nodo, que pueden representar precios, distancias u otros parámetros de interés. Las propiedades que definimos para los grafos se aplican también a redes, por ejemplo una red se dirá bipartita cuando el grafo subyacente lo sea. Llamaremos flujo al envío de elementos de un lugar a otro de una red, nos referiremos a estos elementos que fluyen por la red como unidades de flujo. Las unidades de flujo pueden ser bienes, personas, información o casi cualquier cosa. Asociados a cada arco tenemos varios parámetros importantes: Flujo:fij, es el flujo que pasa por el arco (i, j). Cota inferior:lij ≥0, es la cantidad mínima de flujo que debe pasar por el arco (i, j).2 Cota superior o capacidad:uij ≥lij, es la cantidad máxima de flujo que puede pasar por el arco (i, j). Coste:cij, es el coste de enviar una unidad de flujo por el arco (i, j). Si cij <0, este parámetro representa beneficio por unidad de flujo. Asociado a los nodos tenemos: Suministro/demanda:bi, es un número entero asociado al nodo i∈Nque representa suministro si bi>0, demanda si bi<0o la existencia de un nodo de enlace si bi= 0. 2Más adelante aclararemos por qué si este parámetro no aparece en la red se supone que es 0 y demostraremos que una red siempre es equivalente a otra con lij = 0,∀(i, j)∈A. 1.2. EL PROBLEMA DE FLUJO EN REDES A COSTE MÍNIMO (PFCM) 5 1 2 [−3] 3[−2] 4 5 [5] (0,2,3) (1,6,2) (2,7,1) (0,1,-1) (1,3,2) (1,2,-1) (0,5,3) Figura 1.4: Ejemplo de red con flujo. Como se observa en la figura anterior, asociada a cada arco se tiene una terna donde se muestran los parámetros de interés en el siguiente orden: (lij, uij, cij). Además, al lado de cada nodo aparece su suministro/demanda, que supondremos nulo en caso de no aparecer. Entonces, una red con flujo Rconstruida sobre el grafo G= (N, A)vendrá caracterizada por una tupla R= ((N, A),l,u,c,b), donde l,u,cybdenotan los vectores de cotas inferiores, capacidades, costes y suministros/demandas respectivamente. Durante todo el texto supondremos que Pn i=1 bi= 0, lo cual quiere decir que no hay flujos externos en la red. En caso de presentársenos un problema en redes con flujos externos, podemos convertirlo fácilmente en un problema sin flujos externos sin más que añadir nodos ficticios. La explicación detallada de cómo hacer esta conversión se encuentra en González-Díaz (2018), en el apartado dedicado a las redes con flujo. 1.2. El problema de flujo en redes a coste mínimo (PFCM) El problema de flujo en redes a coste mínimo (problema estudiado en profundidad en el Grado y al que nos referiremos como PFCM de ahora en adelante) es el problema de flujo en redes esencial, ya que muchos de los problemas de redes con flujo que aparecen en la vida real son casos particulares o generalizaciones del mismo. Dada una red dirigida R= ((N, A),l,u,c,b), un PFCM es un problema de optimización que consiste en determinar el flujo que ha de pasar por cada arco de la red, de modo que el coste asociado al flujo total sea mínimo y que además se satisfagan las demandas de ciertos nodos a partir de los suministros de otros, todo ello cumpliendo las restricciones de capacidad de los arcos. Todo problema de flujo en redes a coste mínimo se puede formular como un problema de programación lineal, donde las variables de decisión son los flujos fij de cada arco, como sigue: 6CAPÍTULO 1. REPASO Minimizar X (i,j)∈A cijfij Sujeto a X {j:(i,j)∈A} fij −X {j:(j,i)∈A} fji =bi,para todo i∈N lij ≤fij ≤uij,para todo (i, j)∈A. Obsérvese que tenemos: Un total de nrestricciones de balance de flujo, una por cada nodo, que establecen que el flujo que sale de cada nodo menos el que entra debe ser igual a su suministro/demanda. Un total de 2mrestricciones de capacidad, dos por cada arco, que exigen que cada arco alcance su cota inferior de flujo sin superar su capacidad. El problema anterior se puede expresar matricialmente, usando la matriz de incidencia Bn×mdel grafo, como sigue: Minimizar cTf Sujeto a Bn×mf=b l≤Im×mf≤u, donde cT(vector fila) es el vector traspuesto del vector de costes ceIm×mes la matriz identidad de tamaño m. Considerando esta expresión se ve claramente que estamos ante un caso particular de problema de programación lineal como los vistos en la primera parte de la asignatura de Programación Lineal y Entera. En esa misma asignatura se estudia el método símplex para la resolución de problemas de programación lineal generales, que tiene un tiempo de ejecución en el peor caso exponencial, aunque solamente conlleva un tiempo mayor a O(n3.5)en ejemplos patológicos.3Sin embargo, el método símplex no se aprovecha de la estructura adicional de la red subyacente a los PFCM, por lo que no es competitivo con otros algoritmos que han sido específicamente diseñados. 1.2.1. Casos particulares del PFCM Algunos casos particulares del PFCM aparecen frecuentemente como subproblemas de otros problemas más complejos. A continuación, se presentan algunos de estos casos particulares: 3Explicaremos qué representa esta notación en la Sección 1.4 sobre complejidad computacional. 1.2. EL PROBLEMA DE FLUJO EN REDES A COSTE MÍNIMO (PFCM) 7 i.El problema del camino más corto Este problema surge en el estudio de otros problemas de optimización y, debido a esto, muchos algoritmos para problemas más generales requieren la resolución de problemas del camino más corto en sus fases intermedias. El problema del camino más corto consiste en encontrar un camino de coste mínimo entre un nodo fuente sy un nodo sumidero t, donde el coste de un camino es la suma de los costes de los arcos que lo forman. Transformamos el problema del camino más corto en un PFCM general fijando todas las cotas inferiores a 0 y las superiores a 1; bs= 1, bt=−1ybi= 0 para el resto de nodos de la red. Así, la solución del problema de programación lineal enviará una unidad de flujo desde el nodo sal nodo ta lo largo del camino con menor coste. Observación. El problema del camino más corto no se puede representar como un PFCM si la red contiene ciclos de longitud (coste) negativa. De hecho, este es un problema para el que no se conocen algoritmos polinomiales.4 1 2 3 4 5 6 7 8 [1] [−1] 2 9 3 5 5 21 2 8 2 2 1 Figura 1.5: Uno de los caminos de mínima longitud entre los nodos 2 y 7, donde en cada arista aij se explicita el coste por unidad de flujo cij. Este problema tiene muchas aplicaciones distintas, algunas más intuitivas como encontrar las rutas más rápidas de conducción entre distintos lugares o las rutas más baratas para enviar cargas. Otra aplicación menos intuitiva es la resolución del cubo de Rubik en el menor número de movimientos posibles. En este caso los nodos representarían los distintos estados del cubo, mientras que los arcos representarían movimientos o giros, así, los algoritmos para el problema del camino más corto encontrarían la manera de resolver el cubo utilizando el menor número de movimientos a partir de una posición dada. 4Explicaremos en la Sección 1.4 qué significa que un algoritmo sea polinomial. 8CAPÍTULO 1. REPASO ii.El problema del flujo máximo El problema del camino más corto modela situaciones donde no nos preocupan las restricciones de capacidad, pues por un arco se puede enviar o no enviar flujo, pero está sometido a costes. El problema del flujo máximo es complementario al problema del camino más corto, pues en él nos despreocupamos de los costes y sin embargo sí que existen restricciones de capacidad. El problema del flujo máximo busca una solución que envíe la máxima cantidad de flujo desde un nodo fuente shasta un nodo sumidero t, respetando las cotas de capacidad, lij ≤fij ≤uij, en cada arco de la red. Este problema también aparece a menudo como subproblema de otros más complicados, por lo que se estudiará más a fondo en el Capítulo 3. Transformamos el problema del flujo máximo en un PFCM general fijando bi= 0 para todo i∈Nycij = 0 para todo (i, j)∈A. Además, debemos introducir en la red un “arco de vuelta” del sumidero a la fuente, con coste negativo cts =−1y capacidad infinita uts =∞, de modo que será beneficioso enviar flujo de sat. Así, la solución del problema maximiza el flujo que pasa por el arco (t, s), o lo que es lo mismo, maximiza la cantidad de flujo que va desde shasta tpor arcos de la red original. s 2 3 t F F s 2 3 t (0,∞,−1) Figura 1.6: Transformando un PFM en un PFCM. Una de las aplicaciones más intuitivas de este problema es la de transportar bienes de un lugar a otro a través de una red de tuberías, carreteras, etc. Si una empresa de gas quiere calcular la máxima cantidad de gas que puede transportar de una ciudad (fuente) a otra (sumidero) a través de su red de gasoductos, tendrá que resolver el problema del flujo máximo donde las restricciones de capacidad de cada arco vienen dadas por el diámetro del gasoducto correspondiente. Para modelar este problema también habría que tener en cuenta otras restricciones físicas, por ejemplo las asociadas a la presión del gas en los distintos nodos de la red. 1.2. EL PROBLEMA DE FLUJO EN REDES A COSTE MÍNIMO (PFCM) 9 iii.El problema del transporte Partimos de una red bipartita R, donde N1yN2pueden tener distinto número de elementos. En este problema cada nodo de N1es un nodo de suministro (bi>0) y cada nodo de N2es un nodo de demanda (bj<0). El coste de cada arco (i, j)∈A puede representar, por ejemplo, las distancia entre los nodos iyj. El problema del transporte busca una solución que envíe unidades de flujo desde los nodos suministro en N1para satisfacer las demandas de N2a un menor coste. Para que el problema tenga solución, claramente las demandas no podrán exceder a los suministros, es decir, debe cumplirse Pi∈N1bi≥Pj∈N2bj. En una de las aplicaciones más comunes del problema del transporte los nodos de suministro representan fábricas de bienes materiales o plantas energéticas, mientras que los nodos de demanda son los centros de almacenamiento de dichos bienes. iv.El problema de asignación Es un caso particular del problema del transporte y también del problema de emparejamiento, por lo que lo estudiaremos más ampliamente en la Sección 4.2. En este caso se parte de una red bipartita donde |N1|=|N2|y los arcos, A⊆N1×N2, representan las posibles asignaciones, cada una con coste cij. Se busca emparejar, con el menor coste posible, cada elemento de N1con un elemento de N2. Transformamos el problema de asignación en un PFCM general fijando: bi= 1 para los nodos de N1,bi=−1para los nodos de N2,lij = 0 yuij = 1 para todos los arcos de A. Así, la solución del problema establecerá una correspondencia entre los nodos de N1y los de N2al menor coste posible. 1.2.2. PFCM con variables enteras: Unimodularidad En muchas aplicaciones de los problemas de flujo en redes en la vida real los flujos representan objetos indivisibles. En este caso, al modelar el problema como un PFCM, los flujos deben tomar valores enteros y tenemos un problema de programación lineal entera. Estos problemas no son fáciles en general, sin embargo la estructura adicional de los PFCM nos permite sortear este inconveniente gracias a la propiedad de unimodularidad. Una matriz cuadrada A∈Zp×pse dice unimodular si su determinante es 1 o −1. Una matriz A∈Zp×qse dice totalmente unimodular si cualquier submatriz cuadrada es singular o unimodular. Esta condición ha de cumplirse también para las submatrices de tamaño 1×1, por lo que cada elemento de una matriz totalmente unimodular ha de ser 0, 1 o −1, es decir, A∈ {−1,0,1}p×q. 10 CAPÍTULO 1. REPASO A continuación se muestran varios resultados que ilustran cómo se relaciona la propiedad de unimodularidad de una matriz con las soluciones de un PFCM. Las demostraciones están escritas en detalle en González-Díaz (2018). Proposición 1.1. Dados una matriz totalmente unimodular A∈Zp×qy un vector b∈Zp, tenemos que cualquier solución básica factible definida por las restricciones Ax =b,x≥0, tiene todas sus componentes enteras. Corolario 1.2. Dado un problema de programación lineal en forma estándar (Ax =b,x≥ 0), si la matriz de restricciones es totalmente unimodular y el vector de lados derechos es entero, entonces todo punto extremo de la región factible tiene todas sus componentes enteras. En particular, si el problema tiene óptimos finitos, al menos uno será entero. La estructura de los PFCM nos permite usar estos resultados para concluir lo siguiente. Proposición 1.3. La matriz de incidencia Bde un grafo dirigido es totalmente unimodular. Proposición 1.4. Si todas las capacidades de un PFCM toman valores enteros, entonces habrá al menos un óptimo entero. Por último, nótese que la hipótesis de que las capacidades sean enteras no es restrictiva. Podemos convertir cualquier PFCM en otro equivalente con capacidades enteras sin más que redondear cada cota superior uij al entero más próximo no mayor que uij y redondear cada cota inferior lij al entero más próximo no menor que lij. Además estos cambios no afectarán al óptimo del problema, que sabemos que existe por el resultado anterior. 1.3. Dualidad en problemas de optimización en redes La dualidad es una herramienta fundamental para el estudio de problemas de optimización y fuente de inspiración para el desarrollo de algoritmos eficientes. A todo problema de programación lineal le podemos asociar un nuevo problema de programación lineal, conocido como el problema dual, con importantes propiedades. Si llamamos primal al problema original, podemos usar las propiedades del dual para ayudarnos a resolver el problema primal. Las demostraciones de los resultados que presentamos en esta sección se pueden consultar en González-Díaz (2018). 1.3. DUALIDAD EN PROBLEMAS DE OPTIMIZACIÓN EN REDES 11 Formulaciones en forma canónica de un problema (P)y su dual (D): Problema primal (P)Problema dual (D) Minimizar cTxMaximizar bTπ(⇔πTb) Sujeto a Ax ≥bSujeto a ATπ≤c(⇔πTA≤cT) x≥0,π≥0. De donde se puede deducir que: Si el primal es un problema de minimización, entonces el dual lo es de maximización y viceversa. Variables y restricciones se intercambian los papeles. Cada variable del primal se corresponde con una restricción del dual y cada restricción del primal se corresponde con una variable del dual. El vector bde lados derechos del primal es el vector de costes del dual y el vector de costes del primal ces el vector de lados derechos en el dual. Dualidad débil y dualidad fuerte A continuación presentamos un par de resultados que relacionan las soluciones del problema primal y las del dual. Teorema 1.5. (Dualidad débil). Dado un par de problemas duales, (P) y (D), la función objetivo asociada a cualquier solución factible del problema de minimización es mayor o igual que la función objetivo asociada a cualquier solución factible del problema de maximización. Demostración. Suponemos, sin pérdida de generalidad, que tenemos el problema primal expresado en forma canónica y que xyπson soluciones factibles del primal y del dual, respectivamente. Entonces, Ax ≥b,x≥0,πTA≤cTyπ≥0. Aplicando estas relaciones a la función objetivo del primal obtenemos que cTx≥(πTA)x=πT(Ax)≥πTb. Este resultado implica que las soluciones factibles del primal siempre nos darán cotas superiores para las del dual. Análogamente, las soluciones factibles del dual siempre nos darán cotas inferiores para las del primal. Esta relación se cumple para cualquier par de problemas de optimización duales entre sí, sean o no lineales, y es de gran relevancia para el desarrollo de algoritmos. 18 CAPÍTULO 2. PRELIMINARES Después de repetir este procedimiento tantas veces como aristas haya en Rcon lij >0, obtenemos la red equivalente R∗. Por tanto, si partimos de un problema de optimización sobre R, esta transformación da lugar a un problema de optimización equivalente sobre R∗. Al resolverlo obtendremos un flujo f∗, que se corresponde con un flujo en la red R obtenido sumando a cada componente de f∗la cota inferior lij correspondiente. 1 2 3 4 (1,3,2) (0,3,4) (0,2,3) (2,7,2) [3] [0] [0] [−3] (a) Red Rcon l= (1,0,0,2). 1 2 3 4 (2,2) (3,4) (2,3) (5,2) [2] [1] [−2] [−1] (b) Red R∗con l∗=0. Modificando los parámetros de los arcos (1,2) y(3,4), y por tanto los suministros/demandas de los cuatro nodos, conseguimos una red R∗con cotas inferiores nulas. Si queremos abastecer los nodos con demanda a partir de los suministros de los nodos con bi>0, sobre la nueva red obtenemos un flujo f∗= (f12, f13, f24, f34) = (0,2,1,0). Podemos obtener el flujo correspondiente en la red original sin más que hacer fij =f∗ ij +lij, de modo que en este ejemplo obtenemos f= (1,2,1,2) con coste asociado 17. 2.1.2. Trabajando con costes reducidos Sea R= ((N, A),u,c,b)la red sobre la cual se plantea un PFCM. Recordemos que en el problema dual de un PFCM (Sección 1.3) las variables, πi, i ∈N, deben cumplir πi−πj≤cij, es decir, cij −πi+πj≥0,∀(i, j)∈A. Definimos: Potenciales de los nodos:πi, es un número entero asociado a cada nodo i∈N que representa cuánto estaría dispuesta a pagar por cada nodo ien el problema dual. El vector π= (π1, . . . , πn)es el vector de potenciales. Costes reducidos:cπ ij, es un número asociado a cada arco (i, j)∈Aque viene dado por cπ ij =cij −πi+πj≥0. Representa la holgura que tenemos en la restricción del dual asociada a la arista (i, j)∈Acon respecto a los costes del primal. 2.1. TRANSFORMACIONES DE REDES 19 A continuación veremos un resultado que afirma que, cuando se trata de problemas de flujo en redes a coste mínimo, podemos trabajar en una red cuyos costes son los costes reducidos de otros dados y obtendremos la solución al problema inicial. Es decir, si queremos resolver un problema de optimización cuya función objetivo es z(0) = P(i,j)∈Acijfij, podemos buscar las soluciones del problema que tiene como función objetivo z(π) = P(i,j)∈Acπ ijfij. Formalicemos este hecho: Propiedad 2.1. Dos problemas de flujo en redes a coste mínimo sobre una misma red, con costes cij ycπ ij respectivamente, tienen las mismas soluciones óptimas. Es más, siendo z(0)la función objetivo del problema original y z(π)la función objetivo del problema correspondiente a los costes reducidos, se cumple z(π) = z(0)−πb. Demostración. Para entender la relación entre las funciones objetivo z(0)yz(π), supongamos que partimos de un vector de potenciales π=0e incrementamos el potencial del nodo khasta πk. Por definición de cπ ij, este cambio disminuye el coste reducido de cada unidad de flujo que sale del nodo ken πkunidades y aumenta el coste reducido de cada unidad de flujo que entra en ken πkunidades. Por tanto el coste total (el valor de la función objetivo z(0)) disminuye en total πk veces el flujo saliente menos el flujo entrante al nodo k. Así, para todo flujo cumpliendo las restricciones de balance de flujo, el valor de z(0)disminuye en πkbkunidades. Repitiendo este proceso para cada nodo i∈N, se obtiene que z(π) = z(0)−X i∈N πibi=z(0)−πb. Para un vector de potenciales dado πb es constante, por tanto un flujo que minimice z(π) también minimiza z(0). Por esto, ambos PFCMs tendrán las mismas soluciones óptimas. 2.1.3. Convirtiendo una red general en una red simple En la siguiente sección nos referimos a la construcción de redes residuales a partir de una red Ry un flujo f0, la cual puede presentar dificultades si no imponemos que la red original sea simple.1Veamos que, dado un problema de optimización en redes sobre una red R(que puede tener más de un arco entre cada par de nodos) es posible obtener otro problema equivalente sobre una red simple. Para convertir una red con costes general en una red simple equivalente, para cada par de nodos i, j ∈Ncon más de un arco entre ellos se añade un nuevo nodo ky se reestablecen los costes y capacidades del siguiente modo: 1En ese caso, en Rf0existirán 2 arcos desde el nodo ihasta el j, cada uno con distintos costes y capacidades, y otros 2 arcos desde el nodo jhasta el i, también con distintos costes y capacidades. 20 CAPÍTULO 2. PRELIMINARES ij ij k (uij, cij) (uji, cji) (uij, cij) (uji, cji) (∞,0) En particular cuando tratamos el problema del flujo máximo estas dificultades no aparecen, pues los costes de todos los arcos son nulos y por tanto podemos combinar los distintos arcos entre iyjsin más que sumar sus capacidades. 2.1.4. Trabajando con redes residuales Un concepto de suma importancia en el diseño de algoritmos es el de las redes residuales. En cada paso se construye una red auxiliar, llamada red residual, que funciona como una red de flujos restantes. Veremos una propiedad que establece que las formulaciones de un problema de optimización sobre la red original y sobre la red residual son equivalentes, ya que se establece una correspondencia entre las soluciones factibles de ambos problemas. Denotaremos por Rf0a la red residual correspondiente a la red Ry el flujo f0. A continuación damos una idea intuitiva de cómo se construye. Si por el arco (i, j)se envían f0 ij unidades de flujo, podemos enviar por él uij −f0 ij unidades de flujo adicionales. También podemos enviar hasta f0 ij unidades de flujo del nodo jal nodo ia través del arco (i, j), lo cual equivale a eliminar el flujo existente en ese arco. Mientras que enviar una unidad de flujo a través de (i, j)aumenta el coste total en cij unidades, enviar flujo de jaipor el mismo arco disminuye el coste en cij unidades. Usando estas ideas, partiendo de una red simple R= ((N, A),u,c,b)) y un flujo f0, se construye la red residual Rf0= ((N0, A0),u0,c0,b0)como sigue: RyRf0tienen el mismo conjunto de nodos, N=N0. Si el arco (i, j)está en Ryf0 ij < uij, entonces incluimos el arco (i, j)en Rf0con coste c0 ij =cij y capacidad residual: u0 ij =uij −f0 ij. Si el arco (i, j)está en Ryf0 ij >0, entonces incluimos el arco (j, i)en Rf0con coste c0 ji =−cij y capacidad residual: u0 ji =f0 ij. Además actualizamos los suministros/demandas del siguiente modo: b0 i=bi−f0 ij yb0 j=bj+f0 ij. 2.1. TRANSFORMACIONES DE REDES 21 ijij [bi][bj] [bi−f0 ij] [bj+f0 ij] (uij, cij) (uij −f0 ij, cij) (f0 ij,−cij) Dados un flujo f0a partir del cual se construye la red residual y un flujo fsobre R, definimos el flujo f0≥0sobre Rf0como el flujo que cumple: f0 ij −f0 ji =fij −f0 ij (2.1) y f0 ijf0 ji = 0.(2.2) El siguiente resultado nos garantiza que todo flujo factible en Rse corresponde con un flujo factible en Rf0y además establece una relación entre los costes en ambas redes. Propiedad 2.2. Un flujo fes un flujo factible en Rsi, y solo si, el flujo correspondiente f0es factible en la red residual Rf0. Además, cf =c0f0+cf0. Demostración. La condición (2.2) implica que f0 ij yf0 ji no pueden ser positivos simultáneamente. Si fij ≥f0 ij entonces fijamos f0 ij =fij −f0 ij yf0 ji = 0. En este caso, si fij < uij se tiene que f0 ij ≤uij −f0 ij =u0 ij, por tanto f0 ij satisface las restricciones de capacidad. Mientras tanto, si fij < f0 ij fijamos f0 ij = 0 yf0 ji =f0 ij −fij. En este caso 0≤f0 ji ≤f0 ij =u0 ji, por tanto f0 ji también satisface las restricciones de capacidad del problema. Queda demostrado que si fes un flujo factible en R, entonces el flujo f0correspondiente es un flujo factible en Rf0. Análogamente se demuestra que, siendo f0un flujo factible en la red residual Rf0, la solución dada por fij = (f0 ij −f0 ji) + f0 ij es un flujo factible en R. Establezcamos pues la relación entre los costes de un flujo fen Ry el correspondiente flujo f0en Rf0. Para todo arco (i, j)∈A,c0 ij =cij yc0 ji =−cij. Para un flujo fij sobre el arco (i, j)de la red original R, el coste del flujo de los arcos (i, j)y(j, i)en la red residual es: c0 ijf0 ij +c0 jif0 ji =c0 ij(f0 ij −f0 ji) = cijfij −cijf0 ij, donde la última igualdad se sigue de (2.1). Por tanto queda demostrado que c0f0=cf −cf0. Como consecuencia de esta propiedad, una vez determinada una solución óptima en la red residual podemos convertirla fácilmente en una solución óptima en la red original. Cabe destacar que varios de los algoritmos para el problema del flujo máximo y para el PFCM que presentaremos utilizan este resultado. 22 CAPÍTULO 2. PRELIMINARES 2.2. Emparejamientos, caminos aumentadores y flores En esta sección presentaremos algunos conceptos y resultados sobre teoría de grafos que serán necesarios para el estudio de los problemas de emparejamiento. Estos resultados, que aparecen en el Capítulo 12 de Ahuja et al. (1993), serán especialmente útiles a la hora de estudiar las distintas versiones del problema de emparejamiento no bipartito (Capítulo 5). Por considerar triviales las propiedades que presentamos, sus demostraciones no están incluidas en el trabajo, así como tampoco lo están en la bibliografía consultada. Arcos y nodos emparejados Un emparejamiento Msobre un grafo G= (N, A)es un subconjunto de arcos, M⊆A, con la propiedad de que no hay dos arcos en Mque sean incidentes en el mismo nodo. Los arcos de Mse llaman arcos emparejados, mientras que los de A\Mson arcos no emparejados. Análogamente, Nse puede dividir en nodos emparejados (nodos incidentes en arcos emparejados) y nodos no emparejados. Si (i, j)∈Mdecimos que el nodo iestá emparejado con el nodo j. Nótese que un emparejamiento en un grafo Gcon nnodos está formado por, a lo sumo, bn/2carcos. Se dice que un emparejamiento es máximo si empareja el mayor número posible de nodos de G. Dado un emparejamiento M={a1, . . . , ak} ⊆ Aformado por karcos, también podemos referirnos a él mencionando los pares de nodos que están emparejados, es decir, M={(i1, j1),(i2, j2),...,(ik, jk)} ⊆ (N×N)k. 1 2 3 4 5 6 Figura 2.1: En este ejemplo M={(2,4),(3,5)}y los nodos 1 y 6 son nodos no emparejados. Caminos y ciclos alternados Sea P=i1,→i2,→. . . ,→ikun camino en un grafo G, decimos que Pes un camino alternado con respecto al emparejamiento Msi empieza en un nodo no emparejado y, para cada par de arcos consecutivos, uno pertenece al emparejamiento y el otro no. Además un camino alternado es par si está formado por un número par de arcos y es impar si 2.2. EMPAREJAMIENTOS, CAMINOS AUMENTADORES Y FLORES 23 está formado por un número impar de arcos. También podemos hablar de ciclo alternado cuando el camino empieza y termina en el mismo nodo. Caminos aumentadores Un camino alternado impar Pcon respecto a un emparejamiento Mse dice que es un camino aumentador. Nótese que el primer y el último nodo de un camino aumentador no están emparejados, de hecho se llama aumentador porque se puede usar para encontrar emparejamientos de mayor cardinalidad que uno dado, sin más que cambiar los arcos emparejados del camino por arcos no emparejados y viceversa. 1 2 3 4 5 6 (a) Emparejamiento M 1 2 3 4 5 6 (b) Emparejamiento M0 Figura 2.2: Usando un camino aumentador para encontrar un emparejamiento de mayor cardinalidad. Por ejemplo, en la figura anterior tenemos un emparejamiento M={(2,4),(3,5)}de cardinalidad 2. En este grafo encontramos fácilmente un camino alternado: 1,→2,→4,→ 3,→5; además, P= 1 ,→2,→4,→3,→5,→6es un camino aumentador, que podemos utilizar para detectar el emparejamiento M0={(1,2),(3,4),(5,6)}de cardinalidad 3. Además, este último emparejamiento es máximo, ya que empareja todos los nodos de N. Diferencia simétrica Sean S1yS2dos conjuntos, su diferencia simétrica es: S1⊕S2= (S1∪S2)−(S1∩S2), es decir, la diferencia simétrica de dos conjuntos está formada por los elementos que están en uno de ellos pero no en ambos. Este concepto nos será de gran utilidad a la hora de estudiar emparejamientos gracias al siguiente resultado. Propiedad 2.3. Sean Mun emparejamiento sobre un grafo GyPun camino aumentador con respecto a M. Entonces M⊕Pes un emparejamiento de cardinalidad |M|+1 sobre G, en el cual todos los nodos que estaban emparejados en Msiguen emparejados y se añaden el primer y el último nodo de P. 24 CAPÍTULO 2. PRELIMINARES Nótese que cuando reemplazamos un emparejamiento por su diferencia simétrica con Plo que hacemos es intercambiar los arcos emparejados y los no emparejados de P. Por ejemplo, en la figura anterior:        M={(2,4),(3,5)}, P={(1,2),(2,4),(4,3),(3,5),(5,6)}, M0=M⊕P={(1,2),(4,3),(5,6)}. Propiedad 2.4. Si MyM∗son dos emparejamientos, su diferencia simétrica define el subgrafo G∗= (N, M ⊕M∗)con la propiedad de que cada componente es de uno de los tipos mostrados en la siguiente figura. (a) (b) MM∗M. . . MM∗ (c) MM∗M. . .M∗M (d) M∗MM∗. . . MM∗ (e) M∗MM∗. . .M∗M (f) M∗MM∗. . .M∗M M M∗MM∗. . . M∗M M∗ Figura 2.3: Posibles componentes formadas al hacer M⊕M∗. Esta propiedad se sigue del hecho de que en el subgrafo G∗cada nodo cuenta con 0, 1 o 2 arcos incidentes en él, y las únicas posibles componentes que siguen este esquema son las seis mostradas en la Figura 2.3. Teorema del camino aumentador La demostración del siguiente teorema se puede consultar en Berge (1957). Teorema 2.5. Un emparejamiento M∗sobre un grafo Ges máximo si, y solo si, Gno contiene ningún camino aumentador con respecto a M∗. 2.2. EMPAREJAMIENTOS, CAMINOS AUMENTADORES Y FLORES 25 Una versión alternativa de este resultado es el siguiente teorema, que será crucial en el desarrollo de los algoritmos para el problema de emparejamiento. Teorema 2.6. (Teorema del camino aumentador). Si un nodo pno está emparejado en un emparejamiento MyMno contiene caminos aumentadores que empiecen en p, entonces existe algún emparejamiento máximo sobre Gen el cual el nodo pno está emparejado. Demostración. Sea M∗un emparejamiento máximo. Si el nodo pes un nodo no emparejado en M∗, claramente el teorema es cierto. Supongamos entonces que pestá emparejado en M∗. Si consideramos el subgrafo definido por la diferencia simétrica de ambos emparejamientos, M⊕M∗, sabemos por la propiedad 2.4 que cada componente será del tipo de las mostradas en la Figura 2.3. Dado que, por hipótesis, pno está emparejado en M y no existen caminos aumentadores en Mque comiencen en p, nos queda sólamente la posibilidad (e). El camino mostrado en (e), al que llamaremos P, es un camino alternado de longitud par que empieza en p. Nótese que M0=M∗⊕Pes también un emparejamiento máximo en el cual pes un nodo no emparejado. Hemos construido a partir de M∗ otro emparejamiento máximo M0donde pes un nodo no emparejado, con lo que queda demostrado el teorema. Flores y corolas En los problemas de emparejamiento sobre grafos no bipartitos pueden presentarse dificultades por la presencia de ciertos subgrafos llamados flores, por lo que enunciaremos algunas de sus propiedades para hacer uso de ellas en el Capítulo 5. Dado un emparejamiento Msobre G= (N, A), una flor en Mcon nodo raíz pes un subgrafo de Gcon dos componentes: Tallo: es un camino alternado de longitud par que empieza en el nodo raíz py termina en algún nodo w. Se permite que p=w, en cuyo caso la flor no tendría tallo. Corola:2es un ciclo alternado de longitud impar, que empieza y termina en el nodo final del tallo, w, y que no tiene ningún otro nodo en común con él. Llamamos base de la corola al nodo w. Nótese que dado que los grafos bipartitos no contienen ciclos de longitud impar, no pueden contener flores. 2Denotaremos las corolas con la letra Bpor la palabra inglesa para este tipo de subgrafos, blossom. 26 CAPÍTULO 2. PRELIMINARES 1 2 3 4 5 6 7 8 9 Corola p w (a) Flor sin tallo. 12345 6 7 8 9 10 11 Corola pw (b) Flor con tallo. Figura 2.4: Dos ejemplos de flores. Podemos definir una corola a partir del conjunto de arcos o de nodos que la forman, igual que hacíamos con las cadenas, dependiendo de qué sea más conveniente en cada caso. Propiedad 2.7. Una flor en un emparejamiento Msobre el grafo G= (N, A)cumple: a) Existe un entero l≥0tal que el tallo abarca 2l+ 1 nodos y larcos emparejados. b) Existe un entero k≥1tal que la corola abarca 2k+ 1 nodos y karcos emparejados, estos arcos emparejan a todos los nodos de la corola excepto al nodo base w. c) La base de la corola es un nodo Par, es decir, el único camino que va desde el nodo raíz hasta el nodo base (el tallo) es de longitud par. La siguiente propiedad, aunque pueda parecer intrascendente, conlleva un gran contratiempo a la hora de buscar caminos aumentadores en grafos que contengan flores. Por eso, en el siguiente apartado, explicamos cómo deshacerse de este tipo de subgrafos. Propiedad 2.8. Sea Mun emparejamiento sobre un grafo G= (N, A)yBuna corola en M. Todo nodo ide la corola, excepto su base w, se puede alcanzar desde el nodo raíz p(o desde la propia base w) a través de dos caminos alternados distintos, uno de longitud par y otro de longitud impar. El camino alternado de longitud par llega al nodo ia través de un arco emparejado y el de longitud impar a través de un arco no emparejado. 123 4 5 6 7 8 9 Raíz pw P= 1 ,→2,→3,→4,→6,→8 P0= 1 ,→2,→3,→5,→7,→9,→8 Figura 2.5: Dos caminos alternados con distinta paridad desde phasta un nodo de la corola. 2.2. EMPAREJAMIENTOS, CAMINOS AUMENTADORES Y FLORES 27 Contraer una corola Uno de los algoritmos que presentaremos para resolver el problema de emparejamiento de máxima cardinalidad (que busca emparejamientos máximos sobre un grafo G) se basa en encontrar caminos aumentadores y hacer uso de la Propiedad 2.3 para ir aumentando la cardinalidad del emparejamiento de partida. Este algoritmo asignará a cada nodo una etiqueta, Par o Impar, dependiendo de la longitud del camino que va desde otro nodo concreto del grafo hasta él. En los grafos que contienen una flor, por la Propiedad 2.8, estas etiquetas no estarán bien definidas. Un mismo nodo puede obtener etiqueta Par o Impar dependiendo del camino alternado por el que lleguemos hasta él desde el nodo raíz po desde la base de la corola w. Una de las propuestas más populares para remediar este problema consiste en contraer la corola en un único nodo. Esta operación reemplaza la corola B, que consiste en una secuencia de nodos i1,→i2,→. . . ,→ik,→i1, por un nuevo nodo bde la siguiente manera: 1. Introducimos en el grafo un nuevo nodo by definimos su lista de adyacencia como Ab=Ai1∪Ai2∪. . . ∪Aik. 2. Actualizamos la lista de adyacencia de todo nodo j∈Abhaciendo Aj=Aj∪{b}. 3. Para poder recuperar posteriormente la información sobre los nodos de la corola contraída, creamos una lista con los nodos que la forman, para después eliminar del grafo los nodos i1, i2, . . . , iky los arcos incidentes en ellos. Nótese que esta operación conlleva la actualización de las listas de adyacencia de todos los nodos adyacentes a los eliminados. Si partimos de un emparejamiento Men un grafo G= (N, A)que contiene una corola, llamaremos grafo contraído,Gc= (Nc, Ac), al grafo resultante después de contraer la corola. Además Ac iserá la lista de adyacencia del nodo ien el grafo GcyMcel emparejamiento correspondiente en el grafo contraído. Cada vez que se contrae una corola se crea un nuevo nodo en G. Para diferenciar estos nodos de los nodos del grafo original los llamaremos pseudo-nodos.3Nótese que un pseudo-nodo será siempre un nodo Par, ya que se podría decir que se encogen todos los nodos de una corola hacia su base, la cual es siempre un nodo Par (por la Propiedad 2.7). Por tanto, contraer una corola en un único pseudo-nodo equivale a asignar etiquetas Par a todos los nodos de Gque la forman. 3A la hora de dibujar un grafo, los pseudo-nodos se representan mediante rectángulos para de diferenciarlos de los nodos del grafo original. 34 CAPÍTULO 2. PRELIMINARES Restamos ∆funidades de flujo a los arcos (i, j)∈Aque el camino Cfrecorre en el sentido contrario al dado por R. Por tanto, actualizamos el vector de flujos fde manera que incrementamos el flujo del nodo sal nodo ten ∆funidades. Datos: Partimos de una red R= ((N, A),u,c,b), un pseudo-flujo factible f=0y un vector de potenciales π0=0. ei←bipara todo nodo i∈N inicializar E={i∈N:ei>0}yD={i∈N:ei<0} mientras E6=∅hacer seleccionar un nodo fuente s∈Ey un nodo sumidero t∈D determinar las distancias ds identificar el camino más corto Cfde sat actualizar los potenciales de los nodos πf←πf−ds ∆f= m´ın{m´ın(i,j)∈Cfu0 ij, es,−et} aumentar ∆funidades de flujo a lo largo de Cf actualizar los desequilibrios es←es−∆fyet←et+ ∆f actualizar f, Rf, E, D y los costes reducidos cπ ij ←cij −πf i+πf j fin Algoritmo 2: Algoritmo de caminos más cortos sucesivos. En cada iteración los potenciales de los nodos se actualizan en función de la mínima distancia del nodo fuente sa cada uno de ellos. Los costes se van actualizando a medida que lo hacen los potenciales de los nodos, pues cuanto menor sea el coste de un camino en el primal, estaré dispuesta a pagar menos por el trueque de los nodos inicial y final. En cada iteración el algoritmo resuelve un problema del camino más corto que disminuye el exceso de algún nodo y por tanto el déficit de otro. El algoritmo termina cuando todos los nodos están equilibrados, es decir, cuando se cumplen las nrestricciones de balance de flujo, encontrando un óptimo para el PFCM correspondiente. Por tanto, si llamamos Ual valor absoluto del desequilibrio más grande de la red, el algoritmo de caminos más cortos sucesivos encontrará un óptimo en un máximo de nU iteraciones. Si llamamos S(n, m, C)al coste computacional de resolver el problema del camino más corto sin ciclos de longitud negativa (donde Ces el mayor coste de la red), el algoritmo terminará en un tiempo O(nUS(n, m, nC)). Nótese que en esta última expresión usamos nC en lugar de C, ya que los costes en la red residual están acotados por nC. 2.4. ALGORITMO DE CAMINOS MÁS CORTOS SUCESIVOS PARA EL PFCM 35 Este algoritmo requiere un tiempo pseudo-polinomial para resolver un PFCM. Aunque vimos en la Sección 1.4 que éste no es un tipo de algoritmo muy eficiente, aplicado al problema de emparejamiento bipartito ponderado será más eficiente, ya que para esa clase de problemas se tiene U= 1. 2.4.1. Ejemplo de resolución A continuación resolveremos un problema de flujo en redes a coste mínimo, paso a paso, con el algoritmo de caminos más cortos sucesivos. En cada arco de la red hay dos parámetros, que son (u0 ij, cπ ij). Partimos de la siguiente red R= ((N, A),u,c,b)) 1 2 3 4 (4,2) (2,2) (2,1) (3,3) (5,1) e1= 4 πf 1= 0 e2= 0 πf 2= 0 e3= 0 πf 3= 0 e4=−4 πf 4= 0 Figura 2.9: Ejemplo de PFCM. Red Rfen la iteración I. Tenemos un único nodo con exceso, e1= 4, y un único nodo con déficit, e4=−4, por tanto buscamos sucesivamente los caminos más cortos para llevar flujo del nodo 1 al 4. Iteración 1: Partimos de un pseudo-flujo f=0y un vector de potenciales π=0. Nótese que para estos datos iniciales Rf=R. Tenemos E={1}yD={4}, por tanto s= 1 yt= 4. Las distancias de los caminos más cortos desde sson ds= (0,2,2,3) y Cf= 1 ,→3,→4. Actualizamos el vector πfy después el vector de costes. En esta iteración ∆f= m´ın{u0 13, u0 34, e1,−e4}= m´ın{2,5,4,4}= 2, por tanto incrementamos el flujo del nodo 1 al nodo 4 en dos unidades y actualizamos los desequilibrios e1ye4. Iteración 2: Partimos de la siguiente red Rf. Tenemos E={1}, D ={4}y por tanto s= 1 yt= 4. Las distancias de los caminos más cortos desde sson ds= (0,0,1,1) y Cf= 1 ,→2,→3,→4. Actualizamos el vector πfy después el vector de costes. En esta iteración ∆f= m´ın{u0 12, u0 23, u0 34, e1,−e4}= m´ın{4,2,3,2,2}= 2, por tanto incrementamos el flujo del nodo 1 al nodo 4 en dos unidades y actualizamos los desequilibrios e1ye4. 36 CAPÍTULO 2. PRELIMINARES 1 2 3 4 (4,0) (2,0) (2,1) (3,2) (5,0) e1= 4 πf 1= 0 e2= 0 πf 2=−2 e3= 0 πf 3=−2 e4=−4 πf 4=−3 (a) Cfen la iteración 1, πfycπactualizados. 1 2 3 4 (4,0) (2,0) (2,1) (3,2) (3,0) (2,0) e1= 2 πf 1= 0 e2= 0 πf 2=−2 e3= 0 πf 3=−2 e4=−2 πf 4=−3 (b) Red Rfen la iteración 2. Iteración 3: Partimos de la siguiente red Rf, en la que todos los nodos están equilibrados. En particular E=∅, por lo que el algoritmo termina. 1 2 3 4 (4,0) (2,0) (2,0) (3,1) (3,0) (2,0) e1= 2 πf 1= 0 e2= 0 πf 2=−2 e3= 0 πf 3=−3 e4=−2 πf 4=−4 (c) Cfen la iteración 2, πfycπactualizados. 1 2 3 4 (2,0) (2,0) (2,0) (2,0) (3,1) (1,0) (4,0) e1= 0 πf 1= 0 e2= 0 πf 2=−2 e3= 0 πf 3=−3 e4= 0 πf 4=−4 (d) Red Rfen la iteración 3. Obtenemos la siguiente distribución de flujos con coste total 14: f12 = 2, f13 = 2, f23 = 2, f34 = 4, z= 2c12 + 2c13 + 2c23 + 4c34 = 14. Capítulo 3 El problema del flujo máximo En este capítulo estudiaremos el problema del flujo máximo, al que a veces nos referiremos como PFM. La información sobre los algoritmos que aparecen en la última sección del capítulo, como resultados sobre su convergencia y tiempo de ejecución, se puede ver con más detalle en los Capítulos 6, 7 y 8 de Ahuja et al. (1993). En particular, nos interesa estudiar este problema de optimización porque el problema de emparejamiento bipartito de máxima cardinalidad (Sección 4.1) se puede convertir, tras unos sencillos pasos, en un PFM donde todas las capacidades son unitarias. Por tanto, los algoritmos que presentemos en esta sección para encontrar un flujo máximo en una red, nos servirán más adelante para encontrar un emparejamiento de máxima cardinalidad sobre un grafo bipartito. Recordemos en qué consiste el problema del flujo máximo: partiendo de una red dirigida y simple, en la que la capacidad de los arcos es limitada, buscamos maximizar la cantidad de flujo que se puede enviar de un nodo fuente sa un nodo sumidero trespetando las capacidades de cada arco. Si denotamos al flujo máximo que buscamos como F, el PFM se puede plantear como un problema de programación lineal como sigue: Maximizar F Sujeto a X {j:(s,j)∈A} fsj −X {j:(j,s)∈A} fjs =F X {j:(i,j)∈A} fij −X {j:(j,i)∈A} fji = 0, i ∈N, i 6=s, t X {j:(t,j)∈A} ftj −X {j:(j,t)∈A} fjt =−F 0≤fij ≤uij,(i, j)∈A. 37 38 CAPÍTULO 3. EL PROBLEMA DEL FLUJO MÁXIMO 3.1. Algoritmo de trayectorias aumentadas (Ford-Fulkerson) Esta sección está basada en los apuntes de la asignatura de Programación Lineal y Entera de González-Díaz (2018), a pesar de que el tema en cuestión no se cubre actualmente en la asignatura del Grado en Matemáticas. El algoritmo de trayectorias aumentadas para el problema del flujo máximo, al que a veces nos referiremos como FFA por sus siglas en inglés, es muy similar el algoritmo de caminos más cortos sucesivos para el PFCM. Este hecho no es de extrañar ya que el problema del flujo máximo se puede ver como un caso particular del PFCM. Dada una red R= ((N, A),u)y un vector de flujos factibles f, se construye la red residual Rf= ((N0, A0),u0)como se explicó en la Sección 2.1.4.1En Rfllamamos trayectoria aumentada a cualquier camino dirigido desde el nodo fuente shasta el sumidero t. El FFA consiste en ir identificando sucesivamente trayectorias aumentadas en Rfy actualizando el flujo fhasta que no exista ningún camino dirigido entre la fuente y el sumidero, momento en el cual el algoritmo termina. Supongamos que en la red Rfexiste una trayectoria aumentada Cf,2en ese caso podemos conseguir un nuevo flujo mayor al anterior. Sea ∆fel mínimo cambio de flujo permitido sobre el camino Cf, es decir: ∆f= m´ın (i,j)∈Cf{u0 ij}>0, hacemos los siguientes cambios en el vector de flujos f, de manera que el flujo que va de sataumenta en ∆funidades. Añadimos ∆funidades de flujo a los arcos (i, j)∈Aque el camino Cfrecorre en el sentido dado por R. Restamos ∆funidades de flujo a los arcos (i, j)∈Aque el camino Cfrecorre en el sentido contrario al dado por R. Además, cuando trabajamos en redes con capacidades finitas este algoritmo encuentra un flujo máximo óptimo en un tiempo limitado por O(mF), donde mes el número de arcos que componen el grafo y Fes el flujo máximo. Este límite es debido a que, en cada iteración del algoritmo se encuentra una trayectoria aumentada en un tiempo O(m), que incrementa el valor del flujo en al menos una unidad, es decir, el algoritmo termina en un máximo de Fiteraciones. 1Recordemos que se puede suponer lij = 0,∀(i, j)∈Ay que en el PFM no nos preocupan los costes. 2Deberíamos llamar a este camino Cf,s,tpara explicitar que depende del flujo y de los nodos fuente y sumidero. Para simplificar la notación lo denotamos simplemente por Cf. 3.1. ALGORITMO DE TRAYECTORIAS AUMENTADAS (FORD-FULKERSON) 39 Datos: Partimos de un vector de flujo factible f=0y una red R= ((N, A),u). mientras Rfcontiene un camino dirigido de sathacer identificar un camino Cfde sat ∆f:= m´ın(i,j)∈Cf{u0 ij} aumentar ∆funidades de flujo a lo largo de Cfy actualizar Rf fin Algoritmo 3: Algoritmo de trayectorias aumentadas (Ford-Fulkerson). 3.1.1. Ejemplo de resolución A continuación ilustraremos la resolución de un problema del flujo máximo usando el algoritmo de trayectorias aumentadas. Partimos de la siguiente red con flujos: 1 2 3 4 st 4 2 4 23 1 1 13 Figura 3.1: Ejemplo de PFM. Red Rfen la iteración 1. Iteración 1: Partimos de un vector de flujos f=0, con flujo asociado F= 0. Para este vector de flujos R=Rf. Encontramos la trayectoria aumentada Cf=s ,→4,→3,→t, con ∆f= m´ın{u0 s4, u0 43, u0 3t}= m´ın{2,1,1}= 1. Actualizamos las siguientes componentes de f:fs4= 0 + 1 = 1, f43 = 0 + 1 = 1 yf3t= 0 + 1 = 1, de modo que el nuevo flujo es F= 0 + 1 = 1. Iteración 2: Para este vector de flujos tenemos la siguiente red Rf 1 2 3 4 st 4 2 4 23 1 1 13 (a) Camino Cfen la iteración 1 1 2 3 4 st 4 1 1 4 23 1 1 13 (b) Red Rfen la iteración 2 40 CAPÍTULO 3. EL PROBLEMA DEL FLUJO MÁXIMO Encontramos la trayectoria aumentada Cf=s ,→1,→2,→t, con ∆f= m´ın{u0 s1, u0 12, u0 2t}= m´ın{4,4,3}= 3. Actualizamos las siguientes componentes de f:fs1= 0 + 3 = 3, f12 = 0 + 3 = 3 yf2t= 0 + 3 = 3, de modo que el nuevo flujo es F= 1 + 3 = 4. Iteración 3: Para este vector de flujos tenemos la siguiente red Rf 1 2 3 4 st 4 1 1 4 23 1 1 13 (c) Camino Cfen la iteración 2 1 2 3 4 st 1 3 1 1 1 3 23 1 1 13 (d) Red Rfen la iteración 3 Encontramos las trayectoria aumentada Cf=s ,→4,→t, con ∆f= m´ın{u0 s4, u0 4t}= m´ın{1,3}= 1. Actualizamos las siguientes componentes de f:fs4= 1 + 1 = 2 yf4t= 0 + 1 = 1, de modo que el nuevo flujo es F= 4 + 1 = 5. Iteración 4: Para este vector de flujos tenemos la siguiente red Rf 1 2 3 4 st 1 3 1 1 1 3 23 1 1 13 (e) Camino Cfen la iteración 3 1 2 3 4 st 1 3 2 1 3 23 1 1 1 2 1 (f) Red Rfen la iteración 4 Encontramos la trayectoria aumentada Cf=s ,→1,→3,→4,→t, con ∆f= m´ın{u0 s1, u0 13, u0 34, u0 4t}= m´ın{1,2,1,2}= 1. Actualizamos las siguientes componentes de f:fs1= 1 + 1 = 2, f13 = 0 + 1 = 1, f34 = 1 + 1 = 2 yf4t= 0 + 1 = 1, de modo que el nuevo flujo es F= 5 + 1 = 6. Iteración 5: Para este vector de flujos tenemos la siguiente red Rf 3.2. PFM EN REDES CON CAPACIDADES UNITARIAS 41 1 2 3 4 st 1 3 2 1 3 23 1 1 1 2 1 (g) Camino Cfen la iteración 4 1 2 3 4 st 4 2 1 3 113 1 1 1 1 2 (h) Red Rfen la iteración 5 En esta última red no existe ninguna trayectoria aumentada de sat, por lo que el algoritmo termina y obtenemos un flujo máximo de F= 6. La distribución de los flujos obtenida (que no tiene por qué ser única) es la siguiente: 1 2 3 4 st 4 2 3 13 1 2 Figura 3.2: Resolución del PFM, F= 6. 3.2. PFM en redes con capacidades unitarias Existen algoritmos específicos para resolver el problema del flujo máximo cuando se trata de una red simple con capacidades unitarias, es decir, donde uij = 1 para todo arco (i, j)de la red. Normalmente, es posible resolver problemas de flujo en redes con capacidades unitarias más eficientemente que en redes generales. Partiendo del algoritmo de etiquetado y del algoritmo de trayectorias aumentadas más cortas, los cuales tienen cada uno un tiempo de O(nm)cuando se aplican a redes unitarias, desarrollaremos el algoritmo del flujo máximo para capacidades unitarias. Este algoritmo es un híbrido de los dos mencionados y consigue un mejor tiempo de ejecución que cualquiera de ellos, ya que encuentra un flujo máximo en un tiempo de O(√nm). Nótese que este algoritmo mejora el tiempo de computación del algoritmo de Ford-Fulkerson de O(mF)hasta un O(√nm). 42 CAPÍTULO 3. EL PROBLEMA DEL FLUJO MÁXIMO Este algoritmo consta de dos fases: en la primera aplica el algoritmo de trayectorias aumentadas más cortas para encontrar un flujo casi óptimo y en la segunda aplica el algoritmo de etiquetado para convertirlo en un flujo máximo. La primera fase termina cuando se satisface la condición ds≥m´ın{d2n2/3e,dm1/2e}, donde dses la distancia del nodo fuente al nodo sumidero con la que trabaja el algoritmo de trayectorias aumentadas más cortas. A continuación describimos los dos algoritmos en los que se basa el algoritmo del flujo máximo para capacidades unitarias. 3.2.1. Algoritmo de etiquetado Mientras que el algoritmo de trayectorias aumentadas no explicita una manera de elegir por qué camino enviamos flujo desde la fuente al sumidero en cada iteración, el algoritmo de etiquetado proporciona una manera específica para elegir Cf. Ya que una vez encontrado ese camino la manera de actualizar los flujos fy la red Rfes la misma que en el anterior algoritmo, explicaremos únicamente cómo busca Cfel algoritmo de etiquetado. Nótese que el algoritmo de etiquetado utiliza una técnica de búsqueda para identificar un camino dirigido en Rfdesde shasta tcomo las descritas en la Sección 2.3. El algoritmo de etiquetado empieza en el nodo fuente y se aleja de él, identificando todos los nodos que son alcanzables desde la fuente a través de un camino orientado de la red residual, con el fin de llegar a alcanzar el nodo sumidero. En cada paso se clasifican los nodos de la red en dos grupos: etiquetados (E) y no etiquetados. Los etiquetados son aquellos nodos que el algoritmo ha alcanzado en el proceso de búsqueda, por lo que ya ha determinado un camino dirigido en la red residual desde el nodo fuente hasta ellos. El algoritmo de etiquetado selecciona en cada iteración uno de los nodos etiquetados y examina su lista de adyacencia para alcanzar y etiquetar nuevos nodos. Además, se guarda la información de los nodos alcanzados que faltan por examinar en una lista (L), es decir, una vez que se etiqueta un nodo, se incluye en Lhasta que se examine su lista de adyacencia. Cuando el sumidero entra en el grupo de los etiquetados, el algoritmo envía la máxima cantidad de flujo posible (∆f) a través del camino construido de satusando los predecesores. Después borra todas las etiquetas, actualiza la red Rfy empieza de nuevo el proceso. El algoritmo termina cuando, después de examinar las listas de adyacencia de todos los nodos etiquetados, el sumidero sigue sin estar etiquetado, es decir, cuando no existe en la red residual ningún camino dirigido entre el nodo fuente y el sumidero. 3.2. PFM EN REDES CON CAPACIDADES UNITARIAS 43 Nótese que cuando usemos este algoritmo para resolver un problema de emparejamiento bipartito de máxima cardinalidad partiremos de una red con capacidades unitarias, por lo que ∆fserá siempre igual a 1. Datos: Partimos de un flujo factible f=0y una red sin costes R= ((N, A),u). Etiquetar el nodo t mientras testé etiquetado hacer desetiquetar todos los nodos etiquetar el nodo sy establecer L={s} mientras L 6=∅ytno está etiquetado hacer eliminar un nodo ide L para cada arco (i, j)∈A0hacer si jno está etiquetado entonces fijar predj←i etiquetar j añadir el nodo jaL fin fin fin si testá etiquetado entonces subrutina aumentar fin fin subrutina aumentar identificar Cfde satusando los predecesores ∆f:= m´ın(i,j)∈Cf{u0 ij} aumentar ∆funidades de flujo a lo largo de Cfy actualizar Rf Algoritmo 4: Algoritmo de etiquetado. Este algoritmo sugiere varios resultados importantes, enunciamos dos a continuación. Teorema 3.1. (Teorema de trayectorias aumentadas). Un flujo fes máximo si, y solo si, la red residual Rfno contiene trayectorias aumentadas. Teorema 3.2. Si todas las capacidades de una red son enteras, entonces el PFM asociado tiene un flujo máximo entero. 50 CAPÍTULO 3. EL PROBLEMA DEL FLUJO MÁXIMO Iteración 2: Una vez actualizada la red, buscamos de nuevo un camino dirigido. Partiendo del nodo fuente s, a través de arcos admisibles encontramos el camino Cf= 1,→3,→8,→10, por el que enviamos una unidad de flujo. 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 1 1 0 (c) Trayectoria aumentada más corta. 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 1 1 0 (d) Red Rfen la iteración 3. Iteración 3: Una vez actualizada la red, buscamos de nuevo un camino dirigido. Partiendo del nodo fuente s, a través de arcos admisibles encontramos el camino 1,→4,→ 8. Como del nodo 8 no sale ningún arco admisible, actualizamos su distancia haciendo d8= m´ın{dj+ 1 : (8, j)∈A0}=d3+ 1 = 3 y volvemos al nodo 4 (4 = pred8) para seguir buscando caminos admisibles. Partiendo del nodo 4, a través de arcos admisibles encontramos el camino Cf= 1 ,→4,→9,→10, por el que enviamos una unidad de flujo. 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 1 1 0 (e) No podemos avanzar en el nodo 8. 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 3 1 0 (f) Actualizamos d8= 3 y buscamos otro camino. Iteración 4: Una vez actualizada la red, buscamos de nuevo un camino dirigido. Partiendo del nodo fuente s, a través de arcos admisibles encontramos el camino Cf= 1,→5,→7,→10, por el que enviamos una unidad de flujo. 3.2. PFM EN REDES CON CAPACIDADES UNITARIAS 51 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 3 1 0 (g) Red Rfen la iteración 4. 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 3 1 0 (h) Trayectoria aumentada más corta. Iteración 5: En la última iteración del algoritmo, una vez actualizada la red Rf comprobamos que As=∅, en particular no hay ningún camino admisible desde shasta t, por lo que el algoritmo termina. El flujo máximo enviado a través de la red original R sigue el siguiente esquema: 1 2 3 4 5 6 7 8 9 10 st 3 2 2 2 2 1 1 3 1 0 (i) Red Rfen la iteración 5. 1 2 3 4 5 6 7 8 9 10 st (j) Distribución del flujo máximo, F= 4. 3.2.3. Algoritmo del flujo máximo para capacidades unitarias Teniendo en cuenta todo lo mencionado en las secciones anteriores podemos presentar formalmente uno de los algoritmos que usaremos para resolver el problema de emparejamiento bipartito de máxima cardinalidad. 52 CAPÍTULO 3. EL PROBLEMA DEL FLUJO MÁXIMO Datos: Partimos de un flujo factible f=0y una red sin costes R= ((N, A),u). mientras ds<m´ın{d2n2/3e,dm1/2e} hacer aplicar Algoritmo de trayectorias aumentadas más cortas fin aplicar Algoritmo de etiquetado (con los datos, fyRf, correspondientes a la última iteración del algoritmo de trayectorias aumentadas más cortas) Algoritmo 6: Algoritmo del flujo máximo para capacidades unitarias. Este algoritmo termina, devolviendo un flujo máximo sobre R, cuando cualquiera de los dos algoritmos de los que es combinación termina. Capítulo 4 El problema de emparejamiento bipartito El problema de emparejamiento bipartito es un caso particular del problema de emparejamiento en el cual los objetos están divididos en dos grupos y deseamos emparejarlos intentando cumplir algún tipo de objetivo. Consideraremos dos versiones de este problema: el problema bipartito de máxima cardinalidad (Sección 4.1), que consiste en encontrar un emparejamiento máximo y el problema bipartito ponderado (Sección 4.2), donde hay un coste asociado a cada arco y se desea encontrar el emparejamiento que empareje todos los nodos de la red con menor coste. Nótese que el problema de máxima cardinalidad se puede ver como un problema ponderado donde los costes de todos los arcos son iguales a −1, por tanto, los algoritmos que presentemos para resolver el problema ponderado pueden usarse también para resolver el de máxima cardinalidad. Sin embargo, encontraremos algoritmos específicos para el problema de máxima cardinalidad que lo resolverán más eficientemente. Veremos que los problemas bipartitos son fáciles de resolver, ya que los podemos modelar como casos particulares de los problemas de flujo en redes vistos en los anteriores capítulos. 4.1. El problema bipartito de máxima cardinalidad Como explicamos previamente, en el problema bipartito de máxima cardinalidad se busca un emparejamiento que asocie el mayor número de nodos posibles de un grafo bipartito no dirigido G= (N1∪N2, A). Una manera de resolver este problema es transformarlo en un problema de flujo máximo haciendo modificaciones sobre el grafo Gcomo se describe a continuación. 53 54 CAPÍTULO 4. EL PROBLEMA DE EMPAREJAMIENTO BIPARTITO Para empezar convertiremos el grafo no dirigido Gen uno dirigido, haciendo que cada arco tenga origen en un nodo de N1y termine en un nodo de N2. Además introduciremos dos nuevos nodos, un nodo fuente sy un nodo sumidero t, y nuevos arcos conectando scon cada nodo de N1y conectando cada nodo de N2con t. Obtenemos así el grafo G0= (N0, A0), a partir del cual construiremos la red R0fijando la capacidad de cada arco igual a 1. Tras estos sencillos pasos obtenemos R0= ((N0, A0),u)que además es una red simple. a1 a2 a3 a4 b1 b2 b3 b4 b5 (a) Grafo original G. s a1 a2 a3 a4 b1 b2 b3 b4 b5 t (b) Red R0,uij = 1 ∀(i, j)∈A0. Figura 4.1: Transformando un problema bipartito de máxima cardinalidad en un problema de flujo máximo con capacidades unitarias. Veamos cómo se establece una correspondencia entre un emparejamiento de cardinal k en el grafo original Gy un flujo entero de valor ken la red R0. Dado un emparejamiento {(ai1, bi1),(ai2, bi2),...,(aik, bik)} ⊆ (N1×N2)kde cardinalidad ksobre G, construiremos el flujo correspondiente en R0. Para satisfacer las restricciones de balance de flujo fijamos el flujo de cada arco (s, aij),(aij, bij)y(bij, t)igual a 1 para todo j= 1,2, . . . , k, obteniendo así un flujo de valor kdesde la fuente al sumidero. De manera análoga, dado un flujo entero de valor kdel nodo fuente al nodo sumidero en la red R0, obtendremos el emparejamiento correspondiente en el grafo original G. El flujo de valor kse descompone en kcaminos de la forma s ,→aij,→bij,→t, con j= 1,2, . . . , k. Dado que todas los capacidades en R0son unitarias tenemos asegurado que ningún nodo forma parte de más de un camino, por tanto, los arcos {(ai1, bi1),(ai2, bi2),...,(aik, bik)} definen un emparejamiento de cardinalidad ksobre G. Establecida por tanto la correspondencia entre los emparejamientos en Gy los flujos en R0concluimos que, para resolver un problema de emparejamiento bipartito de máxima 4.1. EL PROBLEMA BIPARTITO DE MÁXIMA CARDINALIDAD 55 cardinalidad podemos resolver el problema de flujo máximo correspondiente con el algoritmo de trayectorias aumentadas visto en la Sección 3.1, que proporciona un flujo entero óptimo en tiempo O(mF). Además, por ser la red R0una red con capacidades unitarias, este tiempo de ejecución es mejorable con el algoritmo visto en la Sección 3.2, con el que conseguimos un tiempo de computación de O(√nm). 4.1.1. Algoritmo para el emparejamiento bipartito de máxima cardinalidad A continuación presentamos un algoritmo específico para resolver el problema de emparejamiento bipartito de máxima cardinalidad, sin necesidad de transformar el grafo original, que se apoya en las propiedades de la diferencia simétrica y en el algoritmo de búsqueda de caminos aumentadores (Sección 2.3.1). Partiendo de un emparejamiento factible, por ejemplo M=∅, el algoritmo busca caminos aumentadores que comiencen en los nodos no emparejados del grafo, p∈N. Si se encuentra tal camino Pentonces se reemplaza Mpor M⊕P, obteniendo un emparejamiento de mayor cardinalidad (véase la Propiedad 2.3). En caso de no existir este camino se elimina del grafo el nodo py todos los arcos incidentes en él, pues por el Teorema 2.6 sabemos que existe un emparejamiento máximo en el cual pno está emparejado. Usando el Teorema del camino aumentador es fácil ver que este algoritmo encuentra un emparejamiento óptimo, pues en cada iteración reduce el número de nodos no emparejados en al menos uno, ya sea emparejando algún nodo o eliminándolo del grafo. Dado que los nodos que están emparejados inicialmente permanecen emparejados a lo largo de la ejecución del algoritmo (por la Propiedad 2.3), cuando el algoritmo termina cada nodo en el subgrafo obtenido está emparejado. Por tanto, Mdebe ser un emparejamiento máximo sobre dicho subgrafo que, por el Teorema 2.6, también es un emparejamiento máximo sobre G. Véase que hemos reducido el problema de emparejamiento de máxima cardinalidad a encontrar si el grafo contiene o no un camino aumentador que empiece en un nodo p. Este algoritmo, que siempre establece un emparejamiento de máxima cardinalidad cuando se aplica a grafos bipartitos, tiene un tiempo de O(nm). Esto es debido a que el algoritmo ejecuta un máximo de nveces las subrutinas de búsqueda yaumentar. Mientras que el proceso de aumentar requiere claramente un tiempo de O(n), ya comprobamos en el segundo capítulo que el proceso de búsqueda requiere un tiempo de O(m)por cada ejecución. 56 CAPÍTULO 4. EL PROBLEMA DE EMPAREJAMIENTO BIPARTITO Datos: Partimos del emparejamiento factible M=∅sobre un grafo bipartito no dirigido G= (N1∪N2, A). para cada nodo p∈Nhacer si el nodo pno está emparejado entonces subrutina búsqueda(p, found) si found = true entonces subrutina aumentar en otro caso borrar el nodo py todos los arcos incidentes a él en G fin fin fin subrutina aumentar identificar el camino aumentador Pempezando en qy usando los predecesores actualizar el emparejamiento haciendo M←M⊕P Algoritmo 7: Algoritmo del emparejamiento bipartito de máxima cardinalidad. Ejemplo de resolución Veamos un ejemplo de resolución de un problema de emparejamiento bipartito de máxima cardinalidad usando el algoritmo presentado. Partimos del siguiente grafo G: 1 2 3 4 5 6 7 8 9 Figura 4.2: Ejemplo de problema de emparejamiento bipartito de máxima cardinalidad. Inicialización: Partimos del emparejamiento nulo M0=∅sobre el grafo bipartito G. 4.1. EL PROBLEMA BIPARTITO DE MÁXIMA CARDINALIDAD 57 Iteración 1: Tomemos el nodo 1∈Nque no está emparejado en M0. Ejecutamos el algoritmo búsqueda(1, found), que asigna etiqueta Par al nodo 1 y examina su lista de adyacencia A1. Encontramos el camino aumentador P1= 1 ,→5, con lo que found =true y conseguimos un emparejamiento de cardinalidad 1, M1=M0⊕P1. 1 2 3 4 5 6 7 8 9 E (a) Etiquetas asignadas en la iteración 1. 1 2 3 4 5 6 7 8 9 (b) M1={(1,5)}. Iteración 2: Tomemos el nodo 2∈Nque no está emparejado en M1. Ejecutamos el algoritmo búsqueda(2, found), que asigna etiqueta Par al nodo 2 y examina su lista de adyacencia A2. Encontramos el camino aumentador P2= 2 ,→6, con lo que found =true y conseguimos un emparejamiento de cardinalidad 2, M2=M1⊕P2. 1 2 3 4 5 6 7 8 9 E (c) Etiquetas asignadas en la iteración 2. 1 2 3 4 5 6 7 8 9 (d) M2={(1,5),(2,6)}. Iteración 3: Tomemos el nodo 3∈Nque no está emparejado en M2. Ejecutamos el algoritmo búsqueda(3, found), que asigna etiqueta Par al nodo 3 y examina su lista de adyacencia A3. Encontramos el camino aumentador P3= 3 ,→7, con lo que found =true 58 CAPÍTULO 4. EL PROBLEMA DE EMPAREJAMIENTO BIPARTITO y conseguimos un emparejamiento de cardinalidad 3, M3=M2⊕P3. 1 2 3 4 5 6 7 8 9 E (e) Etiquetas asignadas en la iteración 3. 1 2 3 4 5 6 7 8 9 (f) M3={(1,5),(2,6),(3,7)}. Iteración 4: Tomemos el nodo 4∈Nque no está emparejado en M3. Ejecutamos el algoritmo búsqueda(4, found), que asigna etiqueta Par al nodo 4 y examina su lista de adyacencia. Como el nodo 7∈A4ya está emparejado, se le asigna etiqueta Impar y se añande a L. Examinamos ahora el nodo 7, que está emparejado al nodo 3, con lo cual se le asigna etiqueta Par al nodo 3 y se añade a L. Al examinar la lista de adyacencia A3 encontramos el camino aumentador P4= 4 ,→7,→3,→8, con lo que found =true y conseguimos un emparejamiento de cardinalidad 4, M4=M3⊕P4. 1 2 3 4 5 6 7 8 9 E O E (g) Etiquetas asignadas en la iteración 4. 1 2 3 4 5 6 7 8 9 (h) M4={(1,5),(2,6),(3,8),(4,7)}. Iteración 5: Tomemos el nodo 9∈Nque no está emparejado en M4. Ejecutamos el algoritmo búsqueda(9, found), que asigna etiqueta Par al nodo 9 y examina su lista de adyacencia. Como el nodo 2∈A9ya está emparejado, se le asigna etiqueta Impar y se 4.2. EL PROBLEMA BIPARTITO PONDERADO 59 añande a L. Examinamos ahora el nodo 2, que está emparejado al nodo 6, con lo cual se le asigna etiqueta Par al nodo 6 y se añade a L. Al examinar la lista de adyacencia A6 encontramos el nodo 1, que ya está emparejado, por lo que se le asigna etiqueta Impar y se añade a L. Examinamos ahora el nodo 1, que está emparejado al nodo 5, con lo cual se le asigna etiqueta Par al nodo 5 y se añade a L. Después de examinar la lista de adyacencia A5, nos encontramos con una lista L=∅y volvemos al algoritmo principal. Como found =false procedemos a eliminar el nodo 9 y todos los arcos incidentes en él, obteniendo el emparejamiento M4sobre el subgrafo final. 1 2 3 4 5 6 7 8 9E O E O E (i) Etiquetas asignadas en la iteración 5. 1 2 3 4 5 6 7 8 (j) Emparejamiento M4sobre el subgrafo. Ahora bien, como en el subgrafo todos los nodos están emparejados el algoritmo termina, proporcionando un emparejamiento de máxima cardinalidad sobre el grafo bipartito original. 4.2. El problema bipartito ponderado Este es el único caso de las cuatro versiones del problema de emparejamiento que se estudia en la asignatura de Programación Lineal y Entera del Grado. El problema de emparejamiento bipartito ponderado también se conoce como problema de asignación por lo que, a partir de ahora, nos referiremos a él indistintamente de cualquiera de las dos maneras. El planteamiento de este problema y la información correspondiente al método húngaro está basado en los apuntes de González-Díaz (2018), donde se habla siempre de problema de asignación. Las cuestiones que presentamos a mayores de lo estudiado en el Grado están basadas en el Capítulo 12 de Ahuja et al. (1993). Dada una red bipartita R= ((N1∪N2, A),u,c)con uij = 1 para todo (i, j)∈A, el problema de asignación consiste en emparejar cada elemento de N1con un elemento de N2 66 CAPÍTULO 5. EL PROBLEMA DE EMPAREJAMIENTO NO BIPARTITO algoritmo no lo encuentra? Probaremos que esto último se verifica si el grafo posee la propiedad de la etiqueta única (que definimos a continuación); en otro caso, la conclusión será incorrecta. Se dice que un grafo posee la propiedad de la etiqueta única con respecto a un emparejamiento dado My un nodo raíz p, si el algoritmo búsqueda(p, found) descrito en la Sección 2.3.1 asigna la misma etiqueta (Par o Impar) a cada nodo marcado independientemente del orden en el que los examine. Propiedad 5.1. Si un grafo posee la propiedad de la etiqueta única, entonces el algoritmo de búsqueda siempre encontrará un camino aumentador en caso de que exista. Demostración. Supongamos que el grafo contiene un camino aumentador p ,→i1,→j1,→ i2,→j2,→. . . ,→ij,→jl,→qdesde el nodo raíz phasta qcon respecto al emparejamiento M. Si se examinan los nodos en este orden, el algoritmo asignará la etiqueta Par a los nodos p, j1, j2, . . . , jl, mientras que los nodos i1, i2, . . . , il, q tendrán etiqueta Impar. Como por hipótesis el grafo posee la propiedad de la etiqueta única, al algoritmo asignará estas mismas etiquetas sea cual el orden en el que examina los nodos. Así, el procedimiento de búsqueda siempre asignará etiqueta Impar al nodo qy por tanto encontrará un camino aumentador. Los grafos bipartitos satisfacen trivialmente la propiedad de la etiqueta única, con respecto a cualquier emparejamiento My cualquier nodo raíz p. Es por esto que, teniendo en cuenta la propiedad anterior, el algoritmo para el emparejamiento bipartito de máxima cardinalidad siempre encontrará un emparejamiento óptimo. Veamos a continuación por qué este algoritmo falla cuando se aplica a una red no bipartita. Un grafo no bipartito puede no satisfacer la propiedad de la etiqueta única (véase la Propiedad 2.8), caso en el cual el algoritmo de búsqueda de un camino aumentador puede fallar aunque este camino exista. Consideremos la situación dada en la siguiente figura: 123 4 5 6 7 8 Raíz Figura 5.1: Problema de emparejamiento no bipartito. 5.1. EL PROBLEMA NO BIPARTITO DE MÁXIMA CARDINALIDAD 67 Si el nodo 5 recibe su etiqueta a través del camino 1,→2,→3,→4,→5recibirá la etiqueta Par. En este caso, al examinar la lista de adyacencia A5, se le atribuye al nodo 6 la etiqueta Impar descubriendo así un camino aumentador sobre el grafo de partida. Sin embargo, si el nodo 5 recibe etiqueta Impar al ser alcanzado a través del camino 1,→2,→3,→7,→8,→5, sólamente examinamos el arco emparejado que sale de él. Con esto llegamos al nodo 4 sin haber examinado el arco no emparejado (5,6), por lo tanto, en este caso el algoritmo presentado en la Sección 2.3.1 no encuentra ningún camino aumentador. 5.1.1. Algoritmo para el emparejamiento no bipartito de máxima cardinalidad El algoritmo que presentamos en esta sección es análogo al usado para el caso bipartito, con la excepción de que modifica el proceso de búsqueda del camino aumentador. El proceso de búsquedaNB(p,found) difiere del presentado en la Sección 2.3.1 en que se utiliza una subrutina adicional, llamada contraer(i,j), que convierte una corola en un pseudo-nodo y actualiza las estructuras de datos tal y como se explicó en la Sección 2.2. Expliquemos cómo funciona el algoritmo para el problema de emparejamiento no bipartito de máxima cardinalidad. Cuando estamos buscando un camino aumentador desde un nodo no emparejado p∈Ny nos encontramos con un nodo, digamos i, al que se le puede asignar una etiqueta distinta a la que ya tiene, el algoritmo suspende el proceso de búsqueda. En este momento hemos encontrado dos caminos alternados con distinta paridad que llegan al nodo idesde p. Si examinamos los predecesores de esos caminos, llegará un momento en el que encontremos un nodo común a ambos. Así, los arcos examinados hasta ese momento constituyen una corola y el primer nodo común a ambos caminos alternados, que tendrá etiqueta Par, es la base de la corola. Llegados a este punto no hay más que contraer la corola en un pseudo-nodo, actualizar los datos y continuar con el proceso de búsqueda. Nótese que podríamos necesitar contraer varias corolas distintas antes de encontrar un camino aumentador en el grafo contraído o antes de quedarnos sin nodos que examinar, lo cual indica que el grafo no contiene caminos aumentadores que comiencen en el nodo raíz p. Cuando encontramos un camino aumentador del nodo pa algún otro nodo no emparejado qdebemos comprobar si este camino contiene algún pseudo-nodo. Si es así expandimos las corolas representadas por estos pseudo-nodos hasta que el camino aumentador no contenga pseudo-nodos. Cada vez que se ejecuta la subrutina contraer(i,j) se crea un nuevo pseudo-nodo en el grafo. Para hacer un seguimiento de estos nodos creados a lo largo del proceso de búsque- 68 CAPÍTULO 5. EL PROBLEMA DE EMPAREJAMIENTO NO BIPARTITO da los numeraremos como n+1, n+2, . . . Por lo que iserá un pseudo-nodo si, y solo si, i>n. Datos: Partimos de un emparejamiento factible M=∅sobre un grafo no bipartito y no dirigido G= (N, A). para cada nodo p∈Nhacer si el nodo pno está emparejado entonces subrutina búsquedaNB(p, found) si found = true entonces subrutina aumentar en otro caso borrar el nodo py todos los arcos incidentes a él en G fin fin fin subrutina aumentar identificar el camino aumentador P0empezando en qy usando predecesores si el camino P0contiene pseudo-nodos entonces expandir las correspondientes corolas y obtener el camino aumentador Pen el grafo original fin actualizar el emparejamiento haciendo M←M⊕P Algoritmo 9: Algoritmo del emparejamiento no bipartito de máxima cardinalidad. A continuación presentamos dos resultados, cuyas demostraciones se pueden consultar en la Sección 12.6 de Ahuja et al. (1993), que nos permitirán asegurar que el algoritmo encuentra un emparejamiento máximo. Lema 5.2. Si el grafo contraído Gccontiene un camino aumentador Pcque empieza en el nodo raíz p(o en el pseudo-nodo que contiene a p) con respecto a un emparejamiento Mc, entonces el grafo original Gcontiene un camino aumentador empezando en el nodo pcon respecto al emparejamiento M. Este lema prueba que si descubrimos un camino aumentador en el grafo contraído, podemos usar este camino para identificar un camino aumentador en el grafo original. Además cuando contraemos una corola no añadimos ningún camino aumentador más allá de los contenidos en el grafo original. Faltaría probar el resultado opuesto, que cuando contraemos una corola no pasamos por alto ningún camino aumentador de la red original. 5.1. EL PROBLEMA NO BIPARTITO DE MÁXIMA CARDINALIDAD 69 Datos: Partimos de un emparejamiento factible Msobre un grafo no bipartito y no dirigido Gy un nodo pno emparejado. fijar Ac i←Aipara todos los nodos i∈N found ←false desetiquetar todos los nodos etiquetar el nodo pcomo Par e inicializar L={p} mientras L 6=∅hacer eliminar un nodo ide L si el nodo itiene etiqueta Par entonces subrutina examinarNB-Par(i,found) en otro caso subrutina examinarNB-Impar(i,found) fin si found = true entonces return fin fin subrutina examinarNB-Par(i, found) para todo nodo j∈Ac ihacer si jtiene etiqueta Par entonces subrutina contraer(i,j) return fin si jno está emparejado entonces fijar q←jypredq←i found ←true return fin si jestá emparejado y no etiquetado entonces predj←i etiquetar jcomo Impar añadir el nodo jaL fin fin Algoritmo 10: Subrutina búsquedaNB(p,found). 70 CAPÍTULO 5. EL PROBLEMA DE EMPAREJAMIENTO NO BIPARTITO subrutina examinarNB-Impar(i, found) sea jel nodo emparejado al nodo i si jtiene etiqueta Impar entonces subrutina contraer(i,j) return fin si el nodo jno está emparejado ni etiquetado entonces predj←i etiquetar el nodo jcomo Par añadir el nodo jaL fin subrutina contraer(i,j) examinar los predecesores de los nodos iyjpara identificar una corola B crear un nuevo nodo by definir Ac b=∪k∈BAc k etiquetar el nodo bcomo Par añadir el nodo baL actualizar Ac j←Ac j∪{b}para cada j∈Ac b crear una lista con la información de los nodos de B eliminar del grafo todos los nodos de By los arcos incidentes en ellos Algoritmo 11: Continuación de búsquedaNB. Lema 5.3. Si Gcontiene un camino aumentador desde en el nodo pal nodo qcon respecto a un emparejamiento M, entonces Gccontiene un camino aumentador desde p(o el pseudonodo que lo contiene) hasta qcon respecto al emparejamiento Mc. Estos dos lemas nos permiten concluir que el grafo contraído contiene un camino aumentador que empieza en el nodo psi, y solo si, el grafo original contiene también un camino aumentador que empiece en p. Como consecuencia, podemos asegurar que el algoritmo presentado para el problema de emparejamiento no bipartito de máxima cardinalidad encuentra un emparejamiento máximo. Además, se puede probar que este algoritmo tiene un tiempo de ejecución, en el peor caso, de O(n3), pues cada proceso de búsquedaNB requiere un tiempo por ejecución de O(n2)y el algoritmo ejecuta este proceso un máximo de nveces. 5.1. EL PROBLEMA NO BIPARTITO DE MÁXIMA CARDINALIDAD 71 Ejemplo de resolución Ilustremos el funcionamiento del algoritmo presentado aplicándolo al siguiente ejemplo, donde partimos de un grafo Gno bipartito y un emparejamiento M={(3,5),(4,6),(7,8)} de cardinalidad 3. 1 2 3 4 5 6 7 8 Figura 5.2: Problema de emparejamiento no bipartito. Supongamos que el algoritmo selecciona el nodo 1 como nodo raíz. El algoritmo de búsqueda del camino aumentador examina los nodos en el siguiente orden: 1 (Impar), 3 (Par), 4 (Par), 5 (Impar), 6 (Impar), 7 (Par), 8 (Par). Examinando ahora el nodo 7, el algoritmo explora el arco (7,8) y descubre la corola 5,→7,→8,→5. Contraemos esta corola en el pseudo-nodo con el número 9 y obtenemos el siguiente grafo contraído. 1 E Raíz 3 O 4 O 5 E 6 E 7 O 8O Corola (a) Etiquetas asignadas. 1 2 3 4 6 9 (b) Grafo contraído 1. En este momento, el nodo 9 es el único nodo no examinado. Examinando la lista de adyacencia del nodo 9 descubrimos otra corola que abarca los nodos 1,→3,→9,→6,→ 4,→1. Contraemos esta corola en el pseudo-nodo con el número 10 y obtenemos el siguiente grafo contraído. 72 CAPÍTULO 5. EL PROBLEMA DE EMPAREJAMIENTO NO BIPARTITO 1 E Raíz 3 O 4 O6E 9 E Corola (c) Corola. 2 O 10 E (d) Grafo contraído 2. Ahora examinando el nodo 10, que es el pseudo-nodo que contiene al nodo raíz, se le asigna etiqueta Impar al nodo 2 que no está emparejado y por tanto descubrimos el camino aumentador 10 ,→2. Para identificar el camino aumentador en el grafo original expandimos los pseudo-nodos que formen parte del camino aumentador que encontramos. Para empezar expandimos el pseudo-nodo 10. El nodo 2 es adyacente al nodo 4 de la corola, por lo que al arco (2,4) le unimos el camino alternado par que va desde el nodo raíz 1 hasta el nodo 4, obteniendo así el camino 1,→3,→9,→6,→4,→2. Por último expandimos el pseudo-nodo 9, obteniendo el camino aumentador en el grafo original P= 1 ,→3,→5,→7,→8,→6,→4,→2. 1 2 3 4 6 9 (e) Después de expandir el nodo 10. 1 2 3 4 5 6 7 8 (f) Después de expandir el nodo 9. Actualizando el emparejamiento con la operación M←M⊕Pconseguimos el siguiente emparejamiento sobre el grafo original de cardinalidad 4, M={(1,3),(5,7),(8,6),(4,2)}. 1 2 3 4 5 6 7 8 Figura 5.3: Problema de emparejamiento no bipartito. 5.2. EL PROBLEMA NO BIPARTITO PONDERADO 73 5.2. El problema no bipartito ponderado Sea R= ((N, A),u,c)una red con costes donde el grafo subyacente es no bipartito, no dirigido y que además cumple uij = 1 para todo (i, j)∈A. Un emparejamiento de coste mínimo es un emparejamiento sobre Rcon el menor coste posible. Hay varias variantes del problema no bipartito ponderado: el problema de emparejamiento de mínimo coste y máxima cardinalidad que busca un emparejamiento con el mayor número de arcos posibles y que, sujeto a esta restricción, tiene el menor coste posible; el problema de emparejamiento de mínimo coste y cardinalidad k(para un entero dado k); el problema de emparejamiento de máximo coste; etc. Cuando hablamos de problema de emparejamiento no bipartito ponderado nos referimos a cualquiera de estas versiones. De este caso particular de problema de emparejamiento enunciaremos la existencia de un par de algoritmos eficientes para su resolución, pues su desarrollo en profundidad excedería la extensión adecuada para un trabajo de este tipo. Se puede consultar en la Sección 11.3 de Papadimitriou and Steiglitz (1998) un estudio en profundidad de este problema de optimización en redes. En él se contempla el algoritmo primal-dual como una herramienta para transformar las versiones ponderadas de los problemas de emparejamiento en sus versiones de máxima cardinalidad. Encontramos pues un algoritmo que hace uso del primal-dual para resolver el problema no bipartito ponderado en un tiempo de O(n4). Actualmente, los algoritmos más rápidos conocidos para resolver este problema son: un algoritmo de velocidad O(nm +n2log n)debido a Gabow (1990), y un algoritmo de velocidad O(mlog(nC)pnα(m, n) log n)debido a Gabow and Tarjan (1989). Anexo A Aplicaciones del problema de emparejamiento Los problemas de emparejamiento surgen en una variedad muy amplia de contextos en la vida real. A continuación mostramos ejemplos de situaciones que podemos plantear, y posteriormente resolver, como problemas de emparejamiento de los que hablamos a lo largo del trabajo. A.1. Recableando máquinas de escribir Una compañía lleva años utilizando un tipo específico de máquinas de escribir eléctricas que perforan cintas de papel, con hasta 6 agujeros, para introducir datos en un ordenador. Así que puede hacer 26= 64 patrones binarios distintos teniendo en cuenta que, en cada una de esas 6 posiciones, puede perforar o no hacerlo. Las máquinas de escribir tienen 46 caracteres, cada uno de los cuales se corresponde con uno de los 64 patrones. Ahora bien, la compañía decide adquirir nuevos ordenadores que utilizan otro código distinto para representar los caracteres dentro del mismo modelo de papel perforado. Por ejemplo, si usamos 1 para representar un agujero y 0 para representar un no-agujero, la letra A se corresponde con 111100 en el código del ordenador antiguo y con 011010 en el código de los ordenadores nuevos. Dado que la máquina de escribir está adaptada al código del ordenador antiguo, el problema consiste en modificarla para que perfore el papel siguiendo el nuevo código. Cada tecla de la máquina de escribir está conectada a una barra de acero, por lo que modificar el código que sigue esa tecla requiere cambios mecánicos en el sistema de barras de acero. Por ejemplo, fijándonos de nuevo en la letra A, deberíamos hacer tres cambios 75