Caudal máximo min corte desde la dualidad

Question

He estado teniendo algunos problemas derivados de la max min de flujo de corte teorema de la dualidad, lo cual me dijeron que es posible. Para empezar, me necesita para lanzar el problema en la forma de "maximizar $\langle c, x\rangle$ sujeto a la restricción $Ax\le b$$x\ge0$. Esto debe ser hecho de tal manera que el dual de este LP, es decir, minimizar $\langle b, x\rangle$ sujeto a las restricciones $A^t y\ge c$, e $y \ge 0$, "es" el min cortar problema.

Por supuesto, no es literalmente el min cortar problema, un problema de la mentira dentro de un espacio Euclidiano. Pero no es siquiera que existe un bijection entre el conjunto de posibles puntos para este segundo (dual) problema y min de corte que se conserva el orden de los valores objetivos. De hecho, min cut es un problema de optimización sobre un número finito de puntos, es decir, $2^{|V|}$ de ellos. Un amigo me dijo que lo que puede ser la intención es que los vértices de la polytope que constituyen la región factible son en bijection con los cortes. Los valores óptimos debe ocurrir en los vértices. Incluso si es así, esto parece sólo como mucho de una equivalencia como diciendo "son equivalentes porque los valores óptimos son siempre los mismos."

Pero incluso esta debilidad de la "equivalencia" es uno que no puede ver. Elija una enumeración $e_1, \dots, e_{|E|}$ de los bordes en un gráfico de $V(G), E(G)$ y una enumeración de los vértices $v_1, \dots, v_{|V|}$. Max flujo se identifica con el LP puedo construir de abajo con el mapa de asociar a cada flujo de un vector en el espacio Euclidiano de dimensión $|E|$ voy a utilizar esta identificación libremente, sin más comentario.) $c(e)$ son las capacidades, $s, t$ el origen y receptor, respectivamente, $h(e)$ la cabeza y $t(e)$ la cola de un borde.

Para empezar se me de la fuerza "max flujo" en el formulario de arriba mediante la definición de un vector $c:=\sum_{e:t(e)=s}1_{e}-\sum_{e:h(e)=s}1_{e}$. Entonces me tome $A=(a_{ie})$ donde $e\in E$ $1\le i \le |E|$ tenemos $a_{ie}=\delta_{e_ie}$ $|E|<i\le |E|+|V|-2$ tenemos $a_{ie}=1$ si $e$ puntos de distancia de $v_{i-|E|}$, $-1$ si apunta hacia, y $0$ lo contrario. A continuación, ponemos el resto de la $a_{ie}=-a_{i-|V|+2\,e}$. Nos pusimos $b$ a las capacidades en el primer $E$ ranuras y, a continuación, $0$ después de eso.

Efectivamente, yo uso $|E|$ dimensiones para escribir las restricciones de capacidad, y, a continuación, $|V|-2$ dimensiones para escribir las restricciones de flujo en una desigualdad, y el resto para la otra desigualdad. No veo a dónde ir ahora. En particular, la razón creo que estoy atascado es múltiples, pero principalmente porque una vez me transponer $A$ I get $|E|$ limitaciones, y no tengo idea de por qué polytope incluso determina $2^{|V|}$ vértices.

Answer 1

Mientras que su problema de programación lineal es válido para la formulación de la máxima de flujo de problema, no es otra formulación que hace que sea más fácil identificar el doble como el min cortar problema.

Deje $(G,u,s,t)$ ser una red con capacidades de $u: E(G) \rightarrow \mathbf{R}^+$, fuente vértice $s$ y lavabo vértice $t$. Deje $P$ ser el conjunto de todos los simples $(s,t)$-rutas en $G$. Supongamos que tenemos una variable $x_p$ para cada una de las posibles $p \in P$, que representa la parte de la corriente se envía a lo largo de ese camino. A continuación, la programación lineal utilizando estas variables se convierte en

$$ \begin{array}{rcclr} \text{max} & \sum_{p \in P} x_p & & & \\ \text{subject to} & \sum_{p \ni e} x_p & \leq & u(e) & \forall e \in E \\ & x_p & \ge & 0 & \forall p \in P \end{array} $$

La primera de las desigualdades asegurar que la capacidad de cada borde no es violado, y la suma no involucra a todo el camino que contiene un cierto límite. El segundo conjunto de desigualdades sólo obliga a que el flujo de cada camino para ser no negativo. Esta formulación tiene un (posiblemente) número exponencial de las variables, pero el punto aquí es reducir el número de restricciones, de modo que el doble se convierte en más fácil. Utilizando el flujo de descomposición puede comprobar que existe un flujo factible para su LP si y sólo si existe un flujo factible con el mismo costo para mi LP, por lo que ambas formulaciones son equivalentes.

El doble de la del nuevo LP tiene una variable $y_e$ por cada borde en $E$, y tiene la forma

$$ \begin{array}{rcclr} \text{min} & \sum_{e \in E} u(e) y_e & & & \\ \text{subject to} & \sum_{e \in p} y_e & \ge & 1 & \forall p \in P \\ & y_e & \ge & 0 & \forall e \in E \end{array} $$

La interpretación aquí es que cada arista tiene un valor no negativo de peso y para cada $(s,t)$-ruta de la suma de sus bordes deben ser de al menos $1$. Esta es una relajación de la min cortar problema. De hecho, si usted toma cualquier $(s,t)$-cut $F \subseteq E$ y considere los vectores característicos $v^F \in \{0,1\}^{E}$ tal que $v^F_e = 1$ si y sólo si $e \in F$; a continuación, este vector es factible para el doble LP con valor igual al valor de la corte de $F$. Por lo que el óptimo de la LP es un límite inferior para el min cortar problema en la red.

El uso de los teoremas de dualidad de programación lineal podría probar el máximo flujo min corte teorema si usted puede probar que el óptimo en el problema dual es exactamente el min de corte de la red, pero esto necesita un poco más de trabajo. Puede consultar los detalles en esta conferencia.