Opened 4 months ago

Closed 3 months ago

#28837 closed defect (fixed)

Flow polytope does not work as expected on Multi-Digraphs

Reported by: gh-jonasfrede Owned by:
Priority: major Milestone: sage-9.0
Component: graph theory Keywords: flow polytopes, multi-digraphs, digraphs, linear programming, combinatorial optimization
Cc: Merged in:
Authors: David Coudert Reviewers: Jonas Frede
Report Upstream: N/A Work issues:
Branch: 5af4462 (Commits) Commit: 5af44625a95f04be2b0eb0c85a4942804820ee6d
Dependencies: Stopgaps:

Description (last modified by gh-jonasfrede)

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 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.

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
Multi-digraph on 2 vertices
sage: P = G.flow_polytope()
sage: P
A 1-dimensional 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 4 months ago by gh-jonasfrede

  • Keywords multi-digraphs digraphs linear programming combinatorial optimization added

comment:2 Changed 4 months ago by gh-jonasfrede

  • Description modified (diff)

comment:3 follow-up: Changed 4 months ago by dcoudert

Method flow_polytope builds a set of inequalities and a set of equalities and then gives them to Polyhedron. Here we get

ineqs = [[0, 1, 1], [0, 1, 1]]
eqs = [[1, -1, -1], [-1, 1, 1]]

so 2 inequalities are the same. I suspect that Polyhedron simplifies that, but I'm not sure.

comment:4 in reply to: ↑ 3 Changed 4 months ago by gh-jonasfrede

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 Multi-Digraphs.

Maybe this happens in other functions too, where Multi-Digraphs 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 follow-ups: Changed 4 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/graphs/28837_flow_polytope
  • Commit set to c39fbe31e100ed62f8b4ac0c750479d63d949d95
  • Status changed from new to 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 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()
[]

New commits:

c39fbe3trac #28837: fix flow polytope for digraphs with multiedges

comment:6 in reply to: ↑ 5 Changed 4 months ago by gh-jonasfrede

Replying to dcoudert:

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]]

Weird, this does not happen with my installation of sage (8.9 from 2019-09-29, 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 in reply to: ↑ 5 Changed 4 months ago by gh-jonasfrede

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 of self.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 4 months ago by git

  • Commit changed from c39fbe31e100ed62f8b4ac0c750479d63d949d95 to 5af44625a95f04be2b0eb0c85a4942804820ee6d

Branch pushed to git repo; I updated commit sha1. New commits:

5af4462trac #28837: fix doctest

comment:9 follow-up: Changed 4 months ago by 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.

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 in reply to: ↑ 9 Changed 4 months ago by gh-jonasfrede

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 4 months ago by dcoudert

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 4 months ago by gh-jonasfrede

  • Status changed from needs_review to positive_review

comment:13 Changed 4 months ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name is missing

comment:14 Changed 4 months ago by gh-jonasfrede

  • Reviewers set to Jonas Frede
  • Status changed from needs_work to positive_review

comment:15 Changed 3 months ago by vbraun

  • Branch changed from public/graphs/28837_flow_polytope to 5af44625a95f04be2b0eb0c85a4942804820ee6d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.