We have graph $(V,A)$, $V$ is teh set of nodes, $A$ is the set of arcs. There is a source node $s \in V$ and a sink $t \in V$. Each node $i$ has a battery with capacity $E_i$. Sending flow on arc $(i,j)$ requires energy from the battery at node $i$, which amounts $e_{ij}$ per unit flow. The objective is to find the maximal flow $s$ to $t$, where the flow is required to be integral.
My formulation for this problem (is it ok?): \begin{align*} max & \sum_{(s,i) \in A} f_{si} \\ s.t. & \sum_{(i,j) \in A} f_{ij} - \sum_{(j,i) \in A} f_{ji} = 0, \quad \forall i \in N\setminus \{ s,t \} \\ & \sum_{(i,j) \in A} f_{ij} \cdot e_{ij} \leq E_i, \quad \forall i \in N\setminus \{ t \} \\ & \sum_{(s,i) \in A} f_{si} \in \{ 0,1,\dots,\lfloor E_s \rfloor \} \end{align*}
I would like to show also the following
(a) If we omit energy constraints, the constraint matrix is totally unimodular, that is every square non-singular submatrix is unimodular (its determinant is $-1,0$ or $1$)
(b) Network flow can be decomposed into a number of $s-t$ paths. Give an integer linear programming formulation for this problem based on paths.
(c) Describe how the relaxation of linear program can be solved by column generation. Include a formulation of the pricing problem, describe how to solve the problem.
I have problems with all three points.
In (a), based on my formulation (which could be wrong), i can't see how the constraint matrix is totally unimodular. It suffices to show that the matrix is composed only by the entries $-1,0$ and $1$ and that in each column there is at most one non-zero element but i can't see it.
In (b) i would denote $S$ as the set of all $s-t$ paths and write objective function as \begin{align*} max & \sum_{s-t \in S} f_{s-t} \end{align*} but then i have problems with constraints.
In (c) i don't know how to start. I searched on the web for some introductory literature on column generation but could't find any.
Can someone help me?
