I have some network $$$G$$$, and for $$$k$$$ edges $$$e_1$$$, $$$e_2$$$... $$$e_k$$$, there is constraint that flow on these edges should be always equal to each other: $$$f_{e_1}=f_{e_2} = ...f_{e_k}$$$. Given this constraint I want to find max flow on $$$G$$$. $$$G$$$ is network with around 10k edges and I have around 1-5 minutes time limit. Any ideas, papers, problems?
This is an interesting problem and it has been studied before. The paper by Srinivasan and Thompson (1972) solves it : https://onlinelibrary.wiley.com/doi/epdf/10.1002/nav.3800190202
This is how to reduce the problem to the paper above. Start by removing the edges $$$e_1, \ldots, e_k$$$ from the graph, but remember both $$$c$$$ the minimum capacity of those edges, and $$$b(u)$$$ the difference between the number of edges with $$$u$$$ as head and those with $$$u$$$ as tail.
Also add an edge between tap and source of infinite capacity and cost -1 (all other edges are of cost -1). Then you can notice that we want to solve the following problem for all $$$x$$$ between 0 and $$$c$$$:
$$$\mathrm{minimize } \sum_{e} f_e\times w_e$$$
$$$\mathrm{subject}\quad \mathrm{to } \sum_{e\in\mathrm{out}(u)} f_e - \sum_{e\in\mathrm{in}(u)} f_e = x\times b(u)$$$
If you can solve that LP for all $$$x$$$ between 0 and $$$c$$$ then you win, the flow is simply the flow on edge from tap to source.
The book Network Flows : theory, algorithms and applications contains this problem as an exercice (11.51), I suggest reading both the exercice and either the corresponding chapter, or https://codeforces.com/blog/entry/94190 to better understand how to solve this.
Thanks for your comprehend answer!