Opened 13 years ago
Last modified 6 years ago
#216 assigned enhancement
Member in Circulation to transform the solution to a basic one
Reported by: | Alpar Juttner | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.5 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
Having a basic solution for the circulation problem is sometime quite useful, e.g. it can be used as a staring solution of the primal Network Simplex algorithm.
The interface should also provide the tree (or forest) of the basis.
Change History (10)
comment:1 follow-up: 3 Changed 13 years ago by
comment:2 Changed 13 years ago by
Owner: | changed from Alpar Juttner to Peter Kovacs |
---|---|
Status: | new → assigned |
comment:3 follow-up: 4 Changed 13 years ago by
Replying to kpeter:
Maybe we should implement a separate class that could transform any flow to a cycle-free one. It could be combined either with
Circulation
or any max. flow algorithm (Preflow
,EdmondsKarp
etc.).
As you rightly noticed below, the problem are not exactly the same for max. flow and for circulations.
e.g. it can be used as a staring solution of the primal Network Simplex algorithm.
Note, that a starting solution for
NetworkSimplex
needs different cycle-free property than other applications. I think in most cases a flow (or circulation) is called cycle-free, if the arcs with positive flow value don't form directed cycles.
Not really, the expression "cycle free" makes no sense for circulations, but only for flows (more exactly where the arc lower bounds are 0 everywhere).
Notice the important difference between the notion "cycle free" (in your answer) and "without free cycle" (in the ticket title). This later one is equivalent with the "basic solution" which is needed by the simplex like algorithms, and by many other problems, and it is also meaningful for the flow problems. A "cycle free" solution (for flows) is something more.
However NS needs a flow in which the arcs with such a flow value that can be modified in both directions (i.e. it is not zero and less than the capacity) don't form a cycle in undirected manner.
So, it has nothing to do with NS vs. other algorithms but the the circulations problems vs. flow problem. In the latter case we sometimes interested in a special basic solution (i.e. a "cycle free" one).
comment:4 Changed 13 years ago by
Replying to alpar:
As you rightly noticed below, the problem are not exactly the same for max. flow and for circulations.
I think there are two independent definitons of a "flow without cycles":
- A flow without directed cycles consisting of arcs with positive flow value (here the lower bounds should be zero on all arcs).
- A flow without undirected cycles consisting of "free arcs", i.e. arcs with flow value that is strictly larger than the lower bound and strictly less than the upper bound. So there are no cycles on which the flow value could be modified in both directions.
Here I call "flow" all kind of flows and circualtions.
Both concepts are suitable for either max. flows, feasible circulations, min. cost flows (with given supply-demand constraints) or min. cost max. flows (if all lower bounds are zero). Sometimes we need the first one, sometimes we need the second one.
Suppose you have a max. flow on a digraph (e.g. you get it by using Preflow). It is a natural request to have such a max. flow that doesn't contain unnecessary "flow cycles", so a max. flow that conforms to the first concept. On the other hand if you would like to transform your solution into a min. cost max. flow (e.g. with a network simplex method), than you need a max. flow that conforms to the second concept.
That's why I don't support introducing these transforming methods into one or more existing algorithms. I prefer having separate tools for that. These algorithms needn't know what kind of flow or circulation they have to make cycle free (according to one of the above concepts), since they don't modify the difference between the outgoing and incoming flow of each nodes.
Not really, the expression "cycle free" makes no sense for circulations, but only for flows (more exactly where the arc lower bounds are 0 everywhere).
That's a special case for circulations. Now a flow having non-zero lower bounds is called "flow" if it has costs and called "circulation" otherwise. In fact, these notions are equivalent. I don't want to make strict difference, since a lot of papers and books use "flow", and some works use "circulation". I accept if the algorithm class is called Circulation
, although I could imagine something with "flow", e.g. FeasibleFlow
, GeneralFlow
etc. Circulation
is better only because it is shorter and simpler. But I do want to be allowed to call "flow" the result of Circulation
. Since it is also a kind of flow.
Notice the important difference between the notion "cycle free" (in your answer) and "without free cycle" (in the ticket title).
It was not clear for me how you used these namings. I tried to make everything clear above.
A "cycle free" solution (for flows) is something more.
No, neither of them is stronger than the other. There are flows that conform to the 1st concept, but don't conform to the 2nd concept, and vice versa.
So, it has nothing to do with NS vs. other algorithms but the the circulations problems vs. flow problem.
Definitely not. That is an incorrect separation. See the reasons above.
comment:5 Changed 13 years ago by
As both of us described above, there are two similar but different definitions of particular importance.
- The "cycle free" property can only be applied to flows/circulations with zero lower bounds, it is discussed in #217.
- The "without free cycles" property is needed for the basic solutions of
NetworkSimplex
. But if we would like to use an initial solution for NS, then it probably worth to use the arc costs for the transformation to determine the better (cheaper) direction when a cycle is removed. However, we don't have costs inCirculation
, thus I find it better to have this transformation inside NS. Assuming this, would we also need a similar function inCirculation
without the usage of arc costs?
comment:6 Changed 13 years ago by
I suggest a class called CycleFreeFlow
or AcyclicFlow
for the first problem, which should be able to give a path decomposition, as well (see #217, #218). This class could be used in combination with any max. flow algorithm and even with Circulation
or min. cost flow algorithms if all lower bounds are zero (and the costs are non-negative).
I don't find the second problem so important (except for the usage in NS). However, we could also have a class for that, if we want. It could be called BasicCirculation
or something similar.
comment:7 Changed 12 years ago by
Milestone: | → LEMON 1.3 release |
---|
comment:8 Changed 12 years ago by
Summary: | Member in Circulation to transform the solution to a basic one (without free cycles) → Member in Circulation to transform the solution to a basic one |
---|
comment:9 Changed 9 years ago by
Milestone: | LEMON 1.3 release → LEMON 1.4 release |
---|
comment:10 Changed 6 years ago by
Milestone: | LEMON 1.4 release → LEMON 1.5 release |
---|
Replying to alpar:
Maybe we should implement a separate class that could transform any flow to a cycle-free one. It could be combined either with
Circulation
or any max. flow algorithm (Preflow
,EdmondsKarp
etc.).Note, that a starting solution for
NetworkSimplex
needs different cycle-free property than other applications. I think in most cases a flow (or circulation) is called cycle-free, if the arcs with positive flow value don't form directed cycles. However NS needs a flow in which the arcs with such a flow value that can be modified in both directions (i.e. it is not zero and less than the capacity) don't form a cycle in undirected manner.In fact, both requirements can be satisfied using almost the same algorithm. I have already implemented such a method inside a minimum cost flow algorithm, but I haven't pushed it to the LEMON repository, yet.