Groupe d’études et de recherche en analyse des décisions

G-2005-26

Computing Disjoint Paths on Polytopes

et

The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph consisting of the set of vertices and arcs of a polytope P directed by a linear objective function in general position. Studying these paths has the potential to provide new insight into a long standing problem, that of designing a polynomial-time simplex method, or proving none exists. To study these paths it would be useful to have a tool to compute them. Without explicitly computing the digraph we develop an algorithm to compute a maximum cardinality set of source to sink paths in a polytope, even in the presence of degeneracy. The algorithm uses a combination of networks flows, the simplex method, and reverse search. An implementation is available. Experimental results show that the algorithm excels when the input has little or no degeneracy, and is especially memory-efficient when the polytope has many vertices. For example, we computed 10 disjoint paths on the polar of the cyclic polytope of dimension 10 with 50 facets storing only 199,000 vertices while the polytope has 1,357,510 vertices. The median path length was 32 vertices. Further preliminary results show that the lengths of the disjoint paths are typically short.

, 23 pages