A tough question me and a friend are facing:
G=(V,E) undirected graph.
s∈V a source vertex.
each v∈V has a value dv>=0.
each e∈E has weight (capacity) ce>=0.
Pv is a Path:s---->v from the source to vertex v.
an LP is formulated as follows:
where:
Zpv is a variable defined for each path Pv in G.
Ys is a variable defined for each subset S of vertices in G.
S is a non-trivial subset of V.
What is the meaning of the above LP? What is its Dual?