Opened 3 years ago
Closed 3 years ago
#28837 closed defect (fixed)
Flow polytope does not work as expected on MultiDigraphs
Reported by:  Jonas Frede  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  graph theory  Keywords:  flow polytopes, multidigraphs, digraphs, linear programming, combinatorial optimization 
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Jonas Frede 
Report Upstream:  N/A  Work issues:  
Branch:  5af4462 (Commits, GitHub, GitLab)  Commit:  5af44625a95f04be2b0eb0c85a4942804820ee6d 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Yet, while working with multidigraphs 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/1cube any more.
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.
This already happens in the following small example:
sage: G = DiGraph(multiedges=True) sage: G.add_edge(0,1) sage: G.add_edge(0,1) sage: G Multidigraph on 2 vertices sage: P = G.flow_polytope() sage: P A 1dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 line sage: P.vertices() (A vertex at (0, 1),) sage: P.lines() (A line in the direction (1, 1),)
P should be the polytope with vertices (0,1) and (1,0), without any lines.
Change History (15)
comment:1 Changed 3 years ago by
Keywords:  multidigraphs digraphs linear programming combinatorial optimization added 

comment:2 Changed 3 years ago by
Description:  modified (diff) 

comment:3 followup: 4 Changed 3 years ago by
comment:4 Changed 3 years ago by
Replying to dcoudert:
ineqs = [[0, 1, 1], [0, 1, 1]]
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).
To generate the nonnegativity constraints we do
ineqs = [[0] + [Integer(j == u) for j in edges] for u in edges]
where instead it should be
ineqs = [[0] + [Integer(j is u) for j in edges] for u in edges]
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 MultiDigraphs.
Maybe this happens in other functions too, where MultiDigraphs have not been taken into account.
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!
comment:5 followups: 6 7 Changed 3 years ago by
Authors:  → David Coudert 

Branch:  → public/graphs/28837_flow_polytope 
Commit:  → c39fbe31e100ed62f8b4ac0c750479d63d949d95 
Status:  new → needs_review 
We cannot use j is u
as
sage: edges = [(0, 1), (0, 1)] sage: [[Integer(j is u) for j in edges] for u in edges] [[1, 1], [1, 1]]
but we have a simpler and more efficient solution, as we only need a diagonal of 1's.
Is the following behavior we get with this patch also ok ?
sage: G = DiGraph([(0, 1, None)], multiedges=False) sage: P = G.flow_polytope(edges=[(0, 1, None), (0, 1, None)]) sage: P A 1dimensional 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() []
New commits:
c39fbe3  trac #28837: fix flow polytope for digraphs with multiedges

comment:6 Changed 3 years ago by
Replying to dcoudert:
We cannot use
j is u
assage: edges = [(0, 1), (0, 1)] sage: [[Integer(j is u) for j in edges] for u in edges] [[1, 1], [1, 1]]
Weird, this does not happen with my installation of sage (8.9 from 20190929, using python 2.7.17):
sage: edges = [(0, 1), (0, 1)] sage: [[Integer(j is u) for j in edges] for u in edges] [[1, 0], [0, 1]]
but we have a simpler and more efficient solution, as we only need a diagonal of 1's.
You're right, that's all we need. I refrained from thinking about range
because of the impending change to python 3, but its use is probably correct and suitable here, even more so after the change.
comment:7 Changed 3 years ago by
In the commit you attached, the docstring is changed accordingly:
If not specified, the list of all edges of
self
is used with the default ordering ofself.edges()
.
Just to make you aware of it, the ordering of edges
in flow_polytope
is not the default ordering of self.edges()
(at least not in my case), but instead an explicitly unordered list:
if edges is None: edges = self.edges(sort=False)
This for me gives another ordering than self.edges()
when called, which in my case is equal to
self.edges(sort=True)
This relates to #22349, where you have expertise. How to best write the docstring I don't know.
comment:8 Changed 3 years ago by
Commit:  c39fbe31e100ed62f8b4ac0c750479d63d949d95 → 5af44625a95f04be2b0eb0c85a4942804820ee6d 

Branch pushed to git repo; I updated commit sha1. New commits:
5af4462  trac #28837: fix doctest

comment:9 followup: 10 Changed 3 years ago by
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.
I don't have this [[1, 1], [1, 1]]
anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.
I pushed a small correction of the doctest.
comment:10 Changed 3 years ago by
Replying to dcoudert:
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.
Ah, thanks for the information. By default, the output of self.edges()
will always be the same as self.edges(sort=False)
as soon as this deprecation process is completed? Then the docstring of flow_polytope
is fine as is now, as far as I'm concerned.
I don't have this
[[1, 1], [1, 1]]
anymore. I have certainly done something weird this morning. Anyway, the solution I proposed with range should be way faster.
Great to see we're on the same page again, but I agree with you on the range
solution. Thanks for everything.
comment:11 Changed 3 years ago by
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.
comment:12 Changed 3 years ago by
Status:  needs_review → positive_review 

comment:14 Changed 3 years ago by
Reviewers:  → Jonas Frede 

Status:  needs_work → positive_review 
comment:15 Changed 3 years ago by
Branch:  public/graphs/28837_flow_polytope → 5af44625a95f04be2b0eb0c85a4942804820ee6d 

Resolution:  → fixed 
Status:  positive_review → closed 
Method
flow_polytope
builds a set of inequalities and a set of equalities and then gives them toPolyhedron
. Here we getso 2 inequalities are the same. I suspect that
Polyhedron
simplifies that, but I'm not sure.