Sage: Ticket #28837: Flow polytope does not work as expected on Multi-Digraphs
https://trac.sagemath.org/ticket/28837
<p>
Flow polytopes of directed graphs are the convex hulls of nonnegative flow values for the arcs of said digraph such that the flow is conserved on internal vertices, and there is a unit of flow leaving the sources and entering the sinks.
</p>
<p>
Yet, while working with multi-digraphs where there are multiple arcs in the same (!) direction for some vertex pairs, the nonnegativity conditions may be violated and the flow polytope will not be a subset of the 0/1-cube any more.
</p>
<p>
A possible suggested temporary fix could be to intersect the resulting polytope with the needed halfspaces given by the nonnegativity constraints and the upper bounds of 1 for every variable, although that would not fix the underlying problem.
</p>
<p>
This already happens in the following small example:
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> G <span class="o">=</span> DiGraph<span class="p">(</span>multiedges<span class="o">=</span><span class="bp">True</span><span class="p">)</span>
sage<span class="p">:</span> G<span class="o">.</span>add_edge<span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
sage<span class="p">:</span> G<span class="o">.</span>add_edge<span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
sage<span class="p">:</span> G
Multi<span class="o">-</span>digraph on <span class="mi">2</span> vertices
sage<span class="p">:</span> P <span class="o">=</span> G<span class="o">.</span>flow_polytope<span class="p">()</span>
sage<span class="p">:</span> P
A <span class="mi">1</span><span class="o">-</span>dimensional polyhedron <span class="ow">in</span> QQ<span class="o">^</span><span class="mi">2</span> defined <span class="k">as</span> the convex hull of <span class="mi">1</span> vertex <span class="ow">and</span> <span class="mi">1</span> line
sage<span class="p">:</span> P<span class="o">.</span>vertices<span class="p">()</span>
<span class="p">(</span>A vertex at <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">),)</span>
sage<span class="p">:</span> P<span class="o">.</span>lines<span class="p">()</span>
<span class="p">(</span>A line <span class="ow">in</span> the direction <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">),)</span>
</pre></div></div><p>
P should be the polytope with vertices (0,1) and (1,0), without any lines.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/28837
Trac 1.2Jonas FredeTue, 03 Dec 2019 14:11:02 GMTkeywords changed
https://trac.sagemath.org/ticket/28837#comment:1
https://trac.sagemath.org/ticket/28837#comment:1
<ul>
<li><strong>keywords</strong>
<em>multi-digraphs</em> <em>digraphs</em> <em>linear</em> <em>programming</em> <em>combinatorial</em> <em>optimization</em> added
</li>
</ul>
TicketJonas FredeWed, 04 Dec 2019 13:05:49 GMTdescription changed
https://trac.sagemath.org/ticket/28837#comment:2
https://trac.sagemath.org/ticket/28837#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/28837?action=diff&version=2">diff</a>)
</li>
</ul>
TicketDavid CoudertFri, 13 Dec 2019 17:18:19 GMT
https://trac.sagemath.org/ticket/28837#comment:3
https://trac.sagemath.org/ticket/28837#comment:3
<p>
Method <code>flow_polytope</code> builds a set of inequalities and a set of equalities and then gives them to <code>Polyhedron</code>.
Here we get
</p>
<pre class="wiki">ineqs = [[0, 1, 1], [0, 1, 1]]
eqs = [[1, -1, -1], [-1, 1, 1]]
</pre><p>
so 2 inequalities are the same. I suspect that <code>Polyhedron</code> simplifies that, but I'm not sure.
</p>
TicketJonas FredeSun, 15 Dec 2019 06:49:53 GMT
https://trac.sagemath.org/ticket/28837#comment:4
https://trac.sagemath.org/ticket/28837#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/28837#comment:3" title="Comment 3">dcoudert</a>:
</p>
<blockquote class="citation">
<pre class="wiki">ineqs = [[0, 1, 1], [0, 1, 1]]
</pre></blockquote>
<p>
Ah, so the building of inequalities is wrong, as they should be the nonnegativity constraints for every arc (exactly one entry should be 1, the others should be 0).
</p>
<p>
To generate the nonnegativity constraints we do
</p>
<pre class="wiki">ineqs = [[0] + [Integer(j == u) for j in edges]
for u in edges]
</pre><p>
where instead it should be
</p>
<pre class="wiki">ineqs = [[0] + [Integer(j is u) for j in edges]
for u in edges]
</pre><p>
to account for the variables referencing the same object instead of just being equal, which breaks exactly in the case of multiple arcs having the same head, tail and label, or in other words, when dealing with Multi-Digraphs.
</p>
<p>
Maybe this happens in other functions too, where Multi-Digraphs have not been taken into account.
</p>
<p>
Either I get around to push this fix after reading how to do it on the homepage, but feel free to do it before me, I would be very thankful!
</p>
TicketDavid CoudertSun, 15 Dec 2019 09:07:54 GMTstatus changed; commit, branch, author set
https://trac.sagemath.org/ticket/28837#comment:5
https://trac.sagemath.org/ticket/28837#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>c39fbe31e100ed62f8b4ac0c750479d63d949d95</em>
</li>
<li><strong>branch</strong>
set to <em>public/graphs/28837_flow_polytope</em>
</li>
<li><strong>author</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
We cannot use <code>j is u</code> as
</p>
<pre class="wiki">sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 1], [1, 1]]
</pre><p>
but we have a simpler and more efficient solution, as we only need a diagonal of 1's.
</p>
<p>
Is the following behavior we get with this patch also ok ?
</p>
<pre class="wiki">sage: G = DiGraph([(0, 1, None)], multiedges=False)
sage: P = G.flow_polytope(edges=[(0, 1, None), (0, 1, None)])
sage: P
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.vertices()
(A vertex at (1, 0), A vertex at (0, 1))
sage: P.lines()
[]
</pre><hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=c39fbe31e100ed62f8b4ac0c750479d63d949d95"><span class="icon"></span>c39fbe3</a></td><td><code>trac #28837: fix flow polytope for digraphs with multiedges</code>
</td></tr></table>
TicketJonas FredeSun, 15 Dec 2019 14:03:01 GMT
https://trac.sagemath.org/ticket/28837#comment:6
https://trac.sagemath.org/ticket/28837#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/28837#comment:5" title="Comment 5">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
We cannot use <code>j is u</code> as
</p>
<pre class="wiki">sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 1], [1, 1]]
</pre></blockquote>
<p>
Weird, this does <strong>not</strong> happen with my installation of sage (8.9 from 2019-09-29, using python 2.7.17):
</p>
<pre class="wiki">sage: edges = [(0, 1), (0, 1)]
sage: [[Integer(j is u) for j in edges] for u in edges]
[[1, 0], [0, 1]]
</pre><blockquote class="citation">
<p>
but we have a simpler and more efficient solution, as we only need a diagonal of 1's.
</p>
</blockquote>
<p>
You're right, that's all we need. I refrained from thinking about <code>range</code> because of the impending change to python 3, but its use is probably correct and suitable here, even more so after the change.
</p>
TicketJonas FredeSun, 15 Dec 2019 14:04:54 GMT
https://trac.sagemath.org/ticket/28837#comment:7
https://trac.sagemath.org/ticket/28837#comment:7
<p>
In the commit you attached, the docstring is changed accordingly:
</p>
<blockquote class="citation">
<p>
If not specified, the list of all edges of <code>self</code> is used with the default ordering of <code>self.edges()</code>.
</p>
</blockquote>
<p>
Just to make you aware of it, the ordering of <code>edges</code> in <code>flow_polytope</code> is not the default ordering of <code>self.edges()</code> (at least not in my case), but instead an explicitly unordered list:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">if</span> edges <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
edges <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>edges<span class="p">(</span>sort<span class="o">=</span><span class="bp">False</span><span class="p">)</span>
</pre></div></div><p>
This for me gives another ordering than <code>self.edges()</code> when called, which in my case is equal to
</p>
<div class="wiki-code"><div class="code"><pre><span class="bp">self</span><span class="o">.</span>edges<span class="p">(</span>sort<span class="o">=</span><span class="bp">True</span><span class="p">)</span>
</pre></div></div><p>
This relates to #<a class="closed ticket" href="https://trac.sagemath.org/ticket/22349" title="#22349: enhancement: Deprecate sorting of Graph vertices and edges by default (closed: fixed)">22349</a>, where you have expertise. How to best write the docstring I don't know.
</p>
TicketgitSun, 15 Dec 2019 17:11:40 GMTcommit changed
https://trac.sagemath.org/ticket/28837#comment:8
https://trac.sagemath.org/ticket/28837#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>c39fbe31e100ed62f8b4ac0c750479d63d949d95</em> to <em>5af44625a95f04be2b0eb0c85a4942804820ee6d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=5af44625a95f04be2b0eb0c85a4942804820ee6d"><span class="icon"></span>5af4462</a></td><td><code>trac #28837: fix doctest</code>
</td></tr></table>
TicketDavid CoudertSun, 15 Dec 2019 17:13:54 GMT
https://trac.sagemath.org/ticket/28837#comment:9
https://trac.sagemath.org/ticket/28837#comment:9
<p>
Well, we are currently finalizing the transition to Python 3. I'm working with version 9.0.beta9 and it is compiled with Python 3. Plus, our goal is to deprecate sorting edges by default. Most algorithms in the graph module are now working independently of the edge ordering.
So I would prefer to avoid sorting, unless it creates a doctest error, which should not be the case here.
</p>
<p>
I don't have this <code>[[1, 1], [1, 1]]</code> anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.
</p>
<p>
I pushed a small correction of the doctest.
</p>
TicketJonas FredeSun, 15 Dec 2019 18:36:54 GMT
https://trac.sagemath.org/ticket/28837#comment:10
https://trac.sagemath.org/ticket/28837#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/28837#comment:9" title="Comment 9">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
Well, we are currently finalizing the transition to Python 3. I'm working with version 9.0.beta9 and it is compiled with Python 3. Plus, our goal is to deprecate sorting edges by default. Most algorithms in the graph module are now working independently of the edge ordering.
So I would prefer to avoid sorting, unless it creates a doctest error, which should not be the case here.
</p>
</blockquote>
<p>
Ah, thanks for the information. By default, the output of <code>self.edges()</code> will always be the same as <code>self.edges(sort=False)</code> as soon as this deprecation process is completed? Then the docstring of <code>flow_polytope</code> is fine as is now, as far as I'm concerned.
</p>
<blockquote class="citation">
<p>
I don't have this <code>[[1, 1], [1, 1]]</code> anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.
</p>
</blockquote>
<p>
Great to see we're on the same page again, but I agree with you on the <code>range</code> solution. Thanks for everything.
</p>
TicketDavid CoudertMon, 16 Dec 2019 17:19:49 GMT
https://trac.sagemath.org/ticket/28837#comment:11
https://trac.sagemath.org/ticket/28837#comment:11
<p>
If you agree with this patch, you can set it to positive review (after review and test).
If you are not confident with that, we can certainly ask for help.
</p>
TicketJonas FredeMon, 16 Dec 2019 20:05:13 GMTstatus changed
https://trac.sagemath.org/ticket/28837#comment:12
https://trac.sagemath.org/ticket/28837#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketVolker BraunMon, 16 Dec 2019 23:26:25 GMTstatus changed
https://trac.sagemath.org/ticket/28837#comment:13
https://trac.sagemath.org/ticket/28837#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Reviewer name is missing
</p>
TicketJonas FredeWed, 18 Dec 2019 12:59:28 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/28837#comment:14
https://trac.sagemath.org/ticket/28837#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jonas Frede</em>
</li>
</ul>
TicketVolker BraunWed, 25 Dec 2019 19:09:28 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/28837#comment:15
https://trac.sagemath.org/ticket/28837#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/graphs/28837_flow_polytope</em> to <em>5af44625a95f04be2b0eb0c85a4942804820ee6d</em>
</li>
</ul>
Ticket