Linear Programming - dual graph theory

Question

I have this following question. It is a question I got from past tests in a course called advanced algorithms. It is not a homework question I just want to understand the solution.

The question goes as follows: We are given a graph $G=(V,E)$ with a source node $s\in V$ and a value $d_v\geq 0$ for every $v\in V$, and with weight=capacity $c_e\geq 0$ for every edge $e\in E$. In this question when referring to a subset of V the meaning is a set $S \subseteq V$ s.t. $S \neq \emptyset,V$, and $P_v$ is a path in $G$ from the source node $s$ to $v$.

In the dual Problem there is a variable $y_S$ for each subset of nodes/vertices and a variable $z_{P_v}$ for each path $P_v$ in the Graph. The objective of the dual problem is to maximize the following expression:

$\sum\limits_{S \subseteq V} y_S + \sum\limits_{paths\\P_v} d_vz_{P_v}$

The constrains of the dual problem is that for every edge $e\in E$ must hold the following inequality:

$\sum\limits_{S \subseteq V\\s.t. e\in \partial_e(S)} y_S + c_e(\sum\limits_{paths\\e\in P_v} z_{P_v})\leq c_e$

The question has 3 sections:

1. Write the primal program. (solved this section).

2. what is the meaning of the whole/integral version of the primal problem?

3. explain how to solve the fraction version of the primal problem efficiently?

Things i tried but im not sure of:

1. Because there is a definition of capacity in this question i thought it might be min cut max flow or someting similar but im not sure its relevant.
2. Because of the way edge expansion is defined ($\partial_e(S)$) and how the primal program looks like I think the constraints might enforce connectivity on the solution but im not sure about this either.

Answer 1

a) Our primal problem is the following:

Let $p_{v_1},..., p_{v_l}$ be all of paths for the graph.

And let $S_{1},..., S_{k}$ be all of our subsets ( $k=2^{m-1}$ where m is the number of edges in the graph)

Then our primal program is:

target function : min$ \sum_{j=1}^{m} c_{e_j}x_{e_j}\ $

for $1 \le i \le k $ for every $ y_{i}$ -> $\sum_{e_j \in E(S_i,V-S_i)}x_{e_j}\ \ge 1$

for $k+1 \le i \le k+l $, for every $ z_{p_{v_i}}$ -> $\sum_{e_j \in P_{v_i}}c_{e_j}x_{e_j}\ \ge d_{v_i}$

b) I think that the combinatorial is finding out a Graph G which is connected and the weight of each the path is bigger that every $d_{v_i}$ for $P_{v_i}$.

c) Here it has to do with using the elpsoid method, and choosing a seperation oracle that suits the problem. I think a seperation oracle should be Floyd Warshal but I am unable to prove this, can someone help?