How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

Question

I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| = m$. $c$ is the cost vector; $c_{ij}$ is the cost of edge $(i,j)$. Costs can be negative and $G$ may have cycles (negative or positive). The target is a minimum cost flow from source vertex $1$ to sink vertex $n$ which must satisfy some constraints. So let $x$ be the solution vector; if $x_{ij}=1$ then the edge $(i,j)$ is a part of minimum cost flow. Here is my optimization problem:

$$min \sum_{(i,j)\in E}c_{ij}x_{ij}$$

Subject to these constraints:

$$\begin{array}{ll} \sum_{i\in V}x_{ij}&=&\sum_{i\in V}x_{ji}~~~~~~\forall j\in V (j\neq1,n)\\ \sum_{j\in V}x_{1j}&=&1\\ \sum_{i\in V}x_{in}&=&1\\ x_{ij}&\in&\{0,1\}~~~~~~\forall i,j\in V\end{array}$$

First constraint makes us sure that in the final solution vector, total number of edges outgoing from vertex $i$ and total number of edges incoming to that vertex are equal.

Only one edge can go out from vertex $1$, based on second constraint and only one edge can come to vertex $n$, based on third constraint.

Finally, last constraint tells us that the maximum flow allowed for each edge is $1$.

This is the problem of sending a flow of value one from vertex $1$ to vertex $n$ subject to the constraints with a capacity limit of $1$ on each edge and the vector $b$ set to $0$.

I asked this question because I think a flow in this case can be viewed as a path, in which we can goes around it's cycles (if any cycle exists on the path) only once and it can't meet vertices $1$ and $n$ more than once. So, can we solve this problem using a modified version of Bellman-Ford or any other dynamic programming algorithm? Time order isn't the matter to me. I just don't want to use algorithms designed for the general form of minimum cost flow problem.

Answer 1

Minimum cost path

If you're looking for a minimum cost path, you can find that directly with Bellman-Ford. Just let the weight on each edge $(i,j)$ be the cost $c_{ij}$, and ask Bellman-Ford to find for you the shortest path from the source to the sink; this will be exactly the minimum cost path (assuming there are no negative cycles in the graph).

Minimum cost flow

If you're looking for a minimum cost flow, one natural approach is to try using the Ford-Fulkerson method. In each iteration of Ford-Fulkerson, you must find an augmenting path in the residual network. In your particular case, you might try computing a minimum-cost augmenting path from the source to the sink. Now what algorithm do you know that can compute a minimum-cost augmenting path in a digraph (potentially with cycles and potentially with negative-weight edges)? That should be enough of a hint to give you something you can try. Since it's your exercise problem, I'll let you work out the details and see if you can prove whether it works or not.

Alternatively, if conceptual simplicity is the goal, linear programming (LP) is one approach that is conceptually very simple and might apply to your porblem, and it has a polynomial running time. LP immediately gives a solution to your problem (though possibly not with integer $x_{ij}$'s), and it's a well-known theorem that you can solve LP in polynomial time. Of course, LP might be a "bigger hammer" than you want to throw at this. Also, I don't know if LP will give you an integral flow, which you seem to want. There's a standard theorem that says that, for the linear program associated with a maximum flow problem, there is always an integral solution to the LP that is optimal (you can't do better with non-integral flows). I don't know if that carries over to the minimum-cost flow setting as well.