2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

a) In my understanding, without the energy constraint, the direction of energy flow is not constrained, e.g. every energy that flows in one direction can flow into the opposite direction. Which would make sense to result in an invertible (unimodular) matrix.

b) A s−t path is a $\lambda$ variable (see literature). The variable is put into every capayity constraint, in which it uses capacity. e.g.

With $\lambda_{1478}$ as a flow from battery 1 to 4 to 7 to 8.

\begin{align} \lambda_{1478}\ +\ \cdots \ <&= E_1\\ \lambda_{1478}\ +\ \cdots \ <&= E_4\\ \lambda_{1478}\ +\ \cdots \ <&= E_7 \end{align}

c)

http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2004/Report-008-2004.pdf

http://link.springer.com/chapter/10.1007%2F0-387-25486-2_1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.