Comportamiento similar a XOR en redes de flujo

8

XOR no es el nombre correcto, pero estoy buscando algún tipo de comportamiento exclusivo.

Actualmente estoy resolviendo un conjunto de problemas diferentes (asignación) modelando redes de flujo y ejecutando un algoritmo de costo mínimo-flujo máximo. Las redes de flujo son bastante útiles porque se les pueden reducir muchos problemas de una manera fácil y comprensible. En mi caso, estos son emparejamientos con algunas restricciones adicionales. A medida que estas restricciones se vuelven más complejas, me preguntaba si hay algunas construcciones existentes para modelar comportamientos específicos.

En este caso, quiero restringir el flujo saliente de un nodo a un solo borde.

Dado un gráfico sol=(V,mi), capacidades integrales y costos . Un nodo arbitrario se llama . Sus vecinos directos se llaman . ¿Podemos reemplazar los bordes (rojo) con alguna construcción para que solo un borde pueda recibir flujo ? Lo que significa que si obtiene algo de flujo (por ejemplo, ), ningún otro borde (rojo) puede recibir flujo.C(tu,v)k(tu,v)UNAsi1,..sinorteUNAsi1,...UNAsinorteUNAsi15 5/ /10

Podríamos agregar nodos / bordes intermedios y jugar con costos y capacidades. La capacidad total de nuestra nueva construcción tiene que permanecer igual y el costo de las diferentes alternativas tiene que mantenerse proporcional.

Entonces mis preguntas son:

  1. ¿Hay construcciones como esta en general? (Cualquier palabra clave, enlaces, documentos)
  2. ¿Me puede sugerir una solución a mi problema específico?
Patrick Schmidt
fuente
Para ser claros, ¿es un problema de flujo mínimo de costo máximo o un problema de flujo de costo mínimo , donde se necesita enviar una cierta cantidad de flujo de la manera más barata posible?
Paresh
Es un problema de costo mínimo, flujo máximo. Actualicé mi pregunta.
Patrick Schmidt
1
¿Puedo preguntar cuál fue el problema original que asignó a una red de flujo con estas restricciones? Pregunto porque hay una solución alternativa simple, y solo quiero asegurarme de que ese no sea el algoritmo original que está intentando asignar al flujo máximo.
Paresh
1
¿Significa eso que solo hay un vértice en el que esta condición de solo 1 flujo de recepción de borde saliente debe aplicarse? ¿O es esta limitación para todos los vértices (en cuyo caso mi respuesta debería proporcionarle la solución más simple)? Además, no entendí bien cómo modeló su problema en la construcción anterior.
Paresh
1
Los problemas de flujo que limitan los flujos a ser caminos generalmente se denominan "flujos no divisibles". El flujo no dividible de costo mínimo es NP-Hard en general. Sin embargo, esa versión tiene demandas sobre los bordes, que carece de su versión.
Nicholas Mancuso

Respuestas:

6

En general, la respuesta es no. Si ponemos restricciones tipo XOR en los bordes salientes de un vértice, podemos demostrar que encontrar un flujo mínimo-corte-máximo es NP-Hard. La técnica es reducir 3-SAT.

Asumamos que hay norte variables X1,X2,...,Xnorte en el 3-SAT y metro cláusulas C1,C2,...,Cmetro. Creamos un gráficosol(V,mi)codificando la instancia del problema 3-SAT. Para cada variableXyo, creamos un vértice vyo conectado a la fuente s con un borde de capacidad. Dos vértices mástuyo,wyo, que están conectados a vyo, se crean para representar Xyo tomando el valor 0 o 1 también con bordes de capacidad .

Para cada una de las cláusulas Cyo, creamos un vértice oyosol correspondiente a ella y oyo está conectado a las variables o sus negaciones en la cláusula con bordes de capacidad 1. Por ejemplo, siCyo=(X3X4 4¬X5 5), lo conectamos a tu3,tu4 4,w5 5con bordes de capacidad. Todasoyo están conectados al fregadero con bordes de capacidad 1.

Ya que Xyo y ¬Xyo no puede tomar el mismo valor, ponemos la restricción XOR en los bordes (vyo,tuyo), (vyo,wyo), yo=1,2,3,...,norte. Se puede demostrar que hay un flujo máximo de tamañometrosi y solo si la instancia 3-SAT es satisfactoria. Dado que el problema es trivial ennortePAGS y la reducción es polinómica, concluimos que la versión de decisión del flujo de la red de restricción XOR es NP-Complete.

Strin
fuente
3

Para su primera pregunta, no conozco ninguna técnica general o regla general que pueda usar para modelar restricciones arbitrarias en redes de flujo. La mayoría de los ejemplos que he visto se basan generalmente en cierta intuición sobre la naturaleza de las restricciones y, a menudo, al principio parecen arbitrarios.

Para su caso particular, todavía tengo que encontrar un buen mapeo para max-flow. Sin embargo, puedo sugerir una solución alternativa simple (es posible que ya lo haya descubierto): Profundizar primero en la búsqueda desde el origens.

Como el flujo está restringido a un solo borde de salida para cada vértice, lo que tiene es una ruta desde el origen hasta el destino. Esta ruta satisface las dos propiedades que puede transportar el flujo máximo entre otras rutas desde la fuentes apuntar ty que tiene el costo más bajo entre todos los caminos que podrían llevar el mismo flujo desde s a t.

  • Inicie un DFS desde s
  • A medida que avanza por el DFS, realice un seguimiento de la capacidad mínima actual de todos los bordes encontrados hasta ahora.
  • También realice un seguimiento del costo total actual (longitud de ruta) encontrado hasta ahora.
  • Si t se alcanza durante el DFS, compare estos dos valores con los valores globales y actualice los valores globales si es necesario.
  • Retroceder desde t y continuar con el DFS.

Básicamente, enumera todas las rutas desde s a tutilizando el DFS y elija el que satisfaga sus criterios de costo mínimo y flujo máximo. El DFS mismo tomaO(El |miEl |) tiempo, que es más eficiente que un algoritmo de flujo máximo.

Paresh
fuente
Gracias, pero como quiero aplicar la regla a un subconjunto de vértices, la solución no será tan simple.
Patrick Schmidt
2

Para construir sobre la respuesta de Paresh, si todas las capacidades máximas son una (y todo lo demás es entero), también podría dividir cada nodo en dos para que el nodo (n-) tenga todos los bordes, el nodo (n +) tiene todo bordes, y (n-) y (n +) están conectados con un borde de capacidad máxima 1. Resuelva esta nueva red de costo mínimo y ya está.

Si las capacidades máximas no son todas una, entonces el problema es más difícil. Puede formular el problema como un MIP (Programa de enteros mixtos). Las únicas restricciones enteras son las restricciones XOR.

Afortunadamente, estos se pueden modelar como Conjuntos ordenados especiales: escriba SOS1 (consulte http://en.wikipedia.org/wiki/Special_ordered_set ). La mayoría de los solucionadores de MIP representan específicamente las restricciones de SOS1 y las manejarán de manera mucho más eficiente (a veces necesita decirlo, a veces lo resolverá; verifique sus documentos de solucionador).

Aunque el MIP finalmente convergerá en la respuesta óptima, para modelos realmente grandes, es posible que no tenga tiempo para esperar a que termine. Conseguir que los MIP grandes converjan suele ser más arte que ingeniería.

La siguiente sugerencia es mucho más trabajo. Puede usar un solucionador de red de costo mínimo como una subrutina y posee su propia ramificación en los bordes XOR utilizando técnicas SOS1. Por ejemplo, en cada rama, apague la mitad menos utilizada de los bordes de salida, resuelva la red de costo mínimo (muy rápido), repita hasta que se cumplan todas las restricciones XOR.

Puede priorizar la secuencia de ramificación según sus propios criterios (volumen de flujo, volumen X costo, capacidad reservada, número de bordes posibles, etc.). Al guiar la búsqueda usted mismo, puede perfeccionar las partes de la solución que son más importantes para usted.

No indica si siempre sabe si su problema es factible o no. Si siempre es factible, es posible que pueda salirse con una estrategia de ramificación que es "libre de retroceso", es decir, lo sigue como una heurística.

Si no se garantiza que el problema sea factible, un MIP podría desaparecer para siempre. Una heurística basada en lo anterior puede ser valiosa para encontrar una solución rápidamente con un número relativamente bajo de violaciones.

EMS
fuente
-2

En general, la respuesta es desconocida, ¡no imposible!

Concluimos que la versión de decisión del flujo de red de restricción XOR es NP-Complete. por lo tanto (es posible, podemos hacer eso) si y solo si P = NP.

aasa
fuente
3
Complete su respuesta con referencias y más detalles.
vonbrand
No se necesitan referencias, esta respuesta solo señala que si P = NP, todavía es posible. es decir, el problema es NP-Complete, pero si P = NP podemos resolverlo.
Albert Hendriks