"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) in the network." I see this statement everywhere but could not find the proof. Is there any reference proving the result? I want to use the proof to understand the polyhedral structure of the stochastic shortest path problem. In case of the stochastic shortest path problem, does an extreme point represent subgraph instead of just a path?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I believe this result (with proof) is contained in the text book "Network Flows" by Ahuja, Magnati and Orlin.
In particular, chapter 11 is on the Network Simplex algorithm and Theorems 11.2 and 11.3 are about optimal solutions in the form of spanning trees. The proofs use the structure of the dual solutions, and also use previous results, so it's not easy to reproduce here.
Knowing that solutions with MST structure exist, it should be possible to show that other solutions can be built as combinations of these (and cycles).
