En cuanto al problema de circulación general:
Estoy de acuerdo con @Helen; aunque no sea tan intuitivo concebir un uso práctico de un límite inferior, es una restricción que debe cumplir. No creo que puedas descartar esta restricción, incluso cuando ese flujo sea cero.
El caso de flujo = 0 se apega al problema de flujo máximo más intuitivo (como lo señala @KillianDS). En ese caso, si el flujo entre un par de nodos es cero, entonces pueden no afectan a la "conservación de la suma de flujo": 
Cuando no hay límite inferior se da a continuación (flujos suponiendo son no negativo) un cero no puede fluir influir en el resultado, porque
- no puede introducir una violación a las restricciones
- no puede influir en la suma (ya que añade un término cero).
Un ejemplo práctico de un flujo mínimo podría existir debido a alguna restricción externa (un problema asociado requiere que al menos X agua atraviese una tubería determinada, como lo señala @Helen). Las restricciones de límite inferior también podrían surgir de un problema dual equivalente, que minimiza el flujo de tal manera que ciertos bordes tienen un límite inferior (y encuentra un equivalente óptimo a un problema de maximización con un límite superior).
Para su problema específico:
Parece que usted está tratando de obtener la mayor cantidad de eventos realizados en un conjunto fijo de intervalos de tiempo (en los que no hay dos eventos pueden superponerse en un intervalo de tiempo).
Considere los conjuntos de intervalos de tiempo que pueden ser asignados a un determinado evento:
E1 - {09:10}
E2 - {09:00}
E3 - {9 : 20, 9:30, 9:40, 9:50}
E3 - {9:00, 9:10, 9:20, 9:30}
Así que usted quiere maximizar el número de tareas asignadas (es decir, eventos incidentales a los bordes que se activan) st los conjuntos resultantes son disjuntos por parejas (es decir, ninguno de los solados de tiempo asignados se superponen).
Creo que esto es NP-Hard porque si pudieras resolver esto, podrías usarlo para resolver el maximal set packing problem (es decir, el empaquetado de conjunto máximo se reduce a esto). Su problema puede resolverse con programación lineal entera, pero en la práctica estos problemas también se pueden resolver muy bien con métodos codiciosos/branch y bound.
Por ejemplo, en su problema de ejemplo. evento E1 "conflictos" con E3 y E2 entra en conflicto con E3. Si se asigna E1 (solo hay una opción), solo hay una posible asignación restante de E3 (la última asignación). Si esta asignación se toma para E3, solo hay una asignación restante para E2. Además, los subgrafos disjuntos (conjuntos de eventos que no pueden entrar en conflicto por los recursos) se pueden resolver por separado.
Si fuera yo, comenzaría con una solución codiciosa muy simple (asignar tareas con menos "ranuras" posibles primero), y luego usar eso como semilla para una sucursal y un solucionador obligado (si la solución codiciosa encontró 4 asignaciones de tareas, luego vinculadas si el subárbol recursivo de asignaciones no puede exceder 3). Incluso podría exprimir algo de rendimiento extra al crear el gráfico de intersecciones por pares entre los conjuntos y solo informar a los conjuntos adyacentes cuando se realiza una asignación. También puede actualizar su mejor número de asignaciones a medida que continúa la sucursal y el límite (creo que esto es normal), por lo que si tiene suerte al principio, converge rápidamente.
He utilizado esta misma idea para encontrar el conjunto más pequeño de proteínas que explicaría un conjunto de péptidos identificados (piezas de proteínas), y me pareció más que suficiente para problemas prácticos. Es un problema muy similar.
Si necesita una hemorragia rendimiento de borde: Cuando reformulada, la programación lineal entera puede hacer casi cualquier variante de este problema que se desea. Por supuesto, en muy malos casos puede ser lento (en la práctica, probablemente te funcione, especialmente si tu gráfica no está muy densamente conectada). Si no lo hace, las relajaciones regulares de programación lineal se aproximan a la solución del ILP y generalmente son bastante buenas para este tipo de problema.
Espero que esto ayude.
fyi: el flujo máximo es un problema de circulación especial donde el límite inferior es cero. Ellos no son lo mismo. – KillianDS
Se ha eliminado la etiqueta. ¡Gracias! –
Los límites inferiores podrían significar que el usuario necesita que exista al menos un flujo X en una tubería para que sea útil para ellos. Por ejemplo, si estaban tratando de impulsar algo del flujo? Piensa en molinos de agua o bombillas o algo así. (Así es como funciona en mi cabeza de todos modos.) – Helen