id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
28837,Flow polytope does not work as expected on Multi-Digraphs,Jonas Frede,,"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:
{{{#!python
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.",defect,closed,major,sage-9.0,graph theory,fixed,"flow polytopes, multi-digraphs, digraphs, linear programming, combinatorial optimization",,,David Coudert,Jonas Frede,N/A,,5af44625a95f04be2b0eb0c85a4942804820ee6d,5af44625a95f04be2b0eb0c85a4942804820ee6d,,