max flow with lower bounds (capacities)

[jens-]

hello

If I use the push_relabel_max_flow.hpp with only 
upper capacities everything works fine, but now I 
need to include lower capacities.
How can I do this and how can I compute the new flow 
values afterwards?

yours
jens

[maestrodd]

Logged In: YES 
user_id=520483

Hi Jens,

please try to elaborate a little more on what you are doing
and what you want to do.

Cheers,
Stephan

[jens-]

Logged In: YES 
user_id=1615116

Hi Stephan,

to be more precise: 
I had given a graph with upper capacities and wanted to 
get the maxflow value. therefore I used the 
boost::adjacency_list, created the residual graph and set 
its residual_capacity and capacity properties as expected 
by the algorithm. This is the input for the 
push_relabel_max_flow.hpp and then I got the flow values 
by capacity - residualcapacity. Works fine!

Now I have to include lower capacities and I would like to 
know if it's possible to use these somehow directly in the 
implemented algorithm. 
Up to now I use a transformation, which adds dummy edges 
to the residual graph so that afterwards the lower 
capacities are eliminated. But this makes the graph bigger 
(more edges). Is there a possibility to use the 
push_relabel_max_flow.hpp without adding edges, just by 
using the property map?

yours
Jens

[jens-]

Logged In: YES 
user_id=1615116

A paper in which the transformation from a max flow 
problem with lower capacities (bounds) to one with lower 
capacity (bound) zero is described in:

http://etd.uwaterloo.ca/etd/cquimber2006.pdf

If one finds a solution without adding edges, as done in 
the paper, please tell me!

[jens-]

Logged In: YES 
user_id=1615116

mistake in Link, correction:
http://etd.uwaterloo.ca/etd/cquimper2006.pdf

[jens-]

Logged In: YES 
user_id=1615116

1. capacity == bound

2. Inttroducing lower bounds:
As described in 
R.K. Ahuja, T.L. Magnanti and J.B. Orlin 
"Network flows: Theory, Algorithms, and Applications "

there are implementations of the max flow algorithm that 
work with only residual capacities! (see chapter 6, 
p.191ff)
So it is easy to introduce lower bounds on the edges and 
to solve the max flow problem more efficiently than by 
using dummy edges as done by Berge.
My question: Is there a possibility to have such an 
implementation in the boost library. For future works this 
semms really interesting to me.

[Marshall Clow]

Assigned to "doug_gregor" instead of nonexistent user "dgregor"