LEMON: Ticket #221: Primal Network Simplex algorithm with given starting solution
https://lemon.cs.elte.hu/trac/lemon/ticket/221
<p>
If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.
</p>
en-usLEMONhttps://lemon.cs.elte.hu/trac/lemon/chrome/site/lemon-logo.gif
https://lemon.cs.elte.hu/trac/lemon/ticket/221
Trac 1.2.3Peter KovacsMon, 16 Feb 2009 02:06:30 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:1
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:1
<p>
Replying to <a class="assigned ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221" title="#221: enhancement: Primal Network Simplex algorithm with given starting solution (assigned)">alpar</a>:
</p>
<blockquote class="citation">
<p>
If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.
</p>
</blockquote>
<p>
Or only a few additional arcs should be introduced (to connect the components of the cycle-free starting solution).
</p>
TicketPeter KovacsMon, 16 Feb 2009 02:06:38 GMTowner, status changed
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:2
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>Alpar Juttner</em> to <em>Peter Kovacs</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>assigned</em>
</li>
</ul>
TicketAlpar JuttnerMon, 16 Feb 2009 06:41:22 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:3
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:3
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:1" title="Comment 1">kpeter</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="assigned ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221" title="#221: enhancement: Primal Network Simplex algorithm with given starting solution (assigned)">alpar</a>:
</p>
<blockquote class="citation">
<p>
If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.
</p>
</blockquote>
<p>
Or only a few additional arcs should be introduced (to connect the components of the cycle-free starting solution).
</p>
</blockquote>
<p>
Or even better: optimize the disconnected blocks separately.
</p>
TicketPeter KovacsMon, 16 Feb 2009 10:05:37 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:4
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:4
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:3" title="Comment 3">alpar</a>:
</p>
<blockquote class="citation">
<p>
Or even better: optimize the disconnected blocks separately.
</p>
</blockquote>
<p>
Not really. Consider the following digraph.
</p>
<p>
Nodes: {1,2,3,4}<br />
Arcs: {(1,3), (1,4), (2,3), (2,4)}<br />
Costs: c(1,3) = c(2,4) = 20, c(1,4) = c(2,3) = 10<br />
with unifrom 1 capacities and 1 supply at nodes 1 and 2, 1 demand at nodes 3 and 4.
</p>
<p>
If the starting solution consist of arcs (1,3) and (2,4) with 1 flow value on both arcs, then optimizing these parts separately won't result in a minimum cost flow.
</p>
<p>
The only case when the problem could be decomposed easily is when the underlying graph is not weakly connected. Then weakly connceted components can be optimized separately.
</p>
<p>
NS needs a spanning tree that contains all the free arcs. After eliminating all the free cycles from the starting solution, we have a forest consisting of the free arcs. Suppose the digraph is weakly connected. Then we have to connect these trees into one spanning tree. It could be done with selecting some of the non-free arcs, but it is more difficult and possibly less efficient than adding one extra root node and a few arcs connecting each tree of free arcs to this root node.
</p>
<p>
(I call an arc "free" if its flow value is greater than the lower bound and less than the upper bound. A free cycle is an <strong>undirected</strong> cycle consisting of free arcs.)
</p>
TicketAlpar JuttnerMon, 16 Feb 2009 10:43:40 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:5
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:5
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:4" title="Comment 4">kpeter</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:3" title="Comment 3">alpar</a>:
</p>
<blockquote class="citation">
<p>
Or even better: optimize the disconnected blocks separately.
</p>
</blockquote>
<p>
Not really.
</p>
</blockquote>
<p>
I still keep on believing that.
</p>
<blockquote class="citation">
<p>
Consider the following digraph.
</p>
<p>
Nodes: {1,2,3,4}<br />
Arcs: {(1,3), (1,4), (2,3), (2,4)}<br />
Costs: c(1,3) = c(2,4) = 20, c(1,4) = c(2,3) = 10<br />
with unifrom 1 capacities and 1 supply at nodes 1 and 2, 1 demand at nodes 3 and 4.
</p>
</blockquote>
<p>
This example is connected, thus the basic solutions correspond to spanning trees.
</p>
<p>
</p>
<blockquote class="citation">
<p>
If the starting solution consist of arcs (1,3) and (2,4) with 1 flow value on both arcs, then optimizing these parts separately won't result in a minimum cost flow.
</p>
</blockquote>
<p>
This example is connected. You can of course decompose only if the graph is not connected.
</p>
<blockquote class="citation">
<p>
The only case when the problem could be decomposed easily is when the underlying graph is not weakly connected. Then weakly connceted components can be optimized separately.
</p>
<p>
NS needs a spanning tree that contains all the free arcs.
</p>
</blockquote>
<p>
Let us call it "basis".
</p>
<blockquote class="citation">
<p>
After eliminating all the free cycles from the starting solution, we have a forest consisting of the free arcs. Suppose the digraph is weakly connected. Then we have to connect these trees into one spanning tree. It could be done with selecting some of the non-free arcs, but it is more difficult and possibly less efficient than adding one extra root node and a few arcs connecting each tree of free arcs to this root node.
</p>
</blockquote>
<p>
It is certainly no less efficient as you have to do it only once. Depending on how you implement the eliminations of free cycles, the full tree of the basis is
</p>
<ul><li>either already in your hand at the end of the process (in case you used a BFS/DFS for detecting the cycles)
</li><li>or it can be obtained very efficiently by doing some additional steps (in case you applied a Kruskal type approach).
</li></ul><p>
Note, that <a class="assigned ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/216" title="#216: enhancement: Member in Circulation to transform the solution to a basic one (assigned)">#216</a> already suggests that the algorithm eliminating the free cycles should also provide the basic tree.
</p>
TicketPeter KovacsMon, 16 Feb 2009 11:38:09 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:6
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:6
<p>
Replying to <a class="ticket" href="https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:5" title="Comment 5">alpar</a>:
</p>
<blockquote class="citation">
<p>
This example is connected, thus the basic solutions correspond to spanning trees.
</p>
</blockquote>
<p>
Yes. The only question is how you extend the forest of free arcs to result in a tree. I just want to show you that the components that is induced by the trees of the forest usually cannot be optimized separately.
</p>
<blockquote class="citation">
<p>
It is certainly no less efficient as you have to do it only once. Depending on how you implement the eliminations of free cycles, the full tree of the basis is
</p>
<ul><li>either already in your hand at the end of the process (in case you used a BFS/DFS for detecting the cycles)
</li></ul></blockquote>
<p>
First you have to consider the subgraph of free arcs and after a DFS is finished but not all nodes have been visited, you have to select a non-free arc that is incident to a visited node. So you have to search the nodes again or you have to store at each node the first incident non-free arc.
You are right, it is not a big deal, but maybe it is not better than introducing a new arc for each tree. Maybe you get a spanning tree with less depth with new arcs, so the pivots could be faster.
</p>
<p>
I think both solutions should be tested.
</p>
TicketAlpar JuttnerTue, 17 Feb 2009 07:10:00 GMT
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:7
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:7
<blockquote class="citation">
<p>
First you have to consider the subgraph of free arcs and after a DFS is finished but not all nodes have been visited, you have to select a non-free arc that is incident to a visited node. So you have to search the nodes again or you have to store at each node the first incident non-free arc.
</p>
</blockquote>
<p>
There are better ways to do it.
</p>
TicketPeter KovacsThu, 11 Feb 2010 06:57:35 GMTmilestone set
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:8
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:8
<ul>
<li><strong>milestone</strong>
set to <em>LEMON 1.3 release</em>
</li>
</ul>
TicketAlpar JuttnerFri, 01 Mar 2013 19:00:09 GMTmilestone changed
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:9
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>LEMON 1.3 release</em> to <em>LEMON 1.4 release</em>
</li>
</ul>
TicketAlpar JuttnerFri, 15 Jul 2016 11:29:23 GMTmilestone changed
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:10
https://lemon.cs.elte.hu/trac/lemon/ticket/221#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>LEMON 1.4 release</em> to <em>LEMON 1.5 release</em>
</li>
</ul>
Ticket