Maximum weighted network flow with lower and upper bounds

Revision en1, by Haruka, 2023-12-15 14:48:32

Recently I have read about the Edmonds-Karp algorithm and the solution to the flows with demands problem. Thus, I come up with the following problem but haven't found a solution yet:

Given a directed graph G(V, E) including a source s (no incoming edge) and a sink t (no outgoing edge). Each edge e in E consists of 3 attributes: l(e), u(e), w(e). Find a flow f from s to t such that l(e) <= f(e) <= u(e) for all edges e in E and the sum of w(e)f(e) is maximized?

Tags flow, graph, network flow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Haruka 2023-12-15 14:48:32 636 Initial revision (published)