I have a flow graph with lower and upper bounds and my task is to find any feasible solution as fast as possible. I found many algorithms and approaches to maximum/minimum flow and so on (also many times uses feasible solution as start point) but nothing specific for any feasible solution. Is there any algorithm/approach that is specific for it and fast?
So I finally got time to sum this up. The solution I used is to take the initial graph and transform it in these steps.
(Weights are in this order: lower bound, current flow, upper bound.)
1. Connect t to s by edge of (0, 0, infinity).
2. To each node of the initial graph add balance value equal to: (sum of lower bound of incoming edges - sum of lower bound of outgoing edges).
3. Set upper bound of every edge to (upper bound - lower bound). Set lower bound and current flow of each edge to 0.
4. Now make new s (s') and new t (t') which will be our new start and end (DO NOT DELETE s and t already in the graph, they just became normal nodes).
5. Create edge from s' to every vertex with positive balance with (0, 0, vertex.balance) bounds.
6. Create edge from every vertex with negative balance to t' with (0, 0, abs(vertex.balance)).
7. Run Ford-Fulkerson (or other maximum flow algorithm of your choice) on the new graph.
8. For every edge of initial graph sum value of the edge with the initial old lower bound before transformation and you have your initial flows for every edge of the initial graph.
This problem is actually a bit harder than to maximize flow when feasible flow is provided.