2
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ Thank you, that helped me a lot -- much clearer now! I don't know the answer off the top of my head, but out of curiousity, is there a reason why the standard algorithms for minimum cost flow are not suitable/desirable in your setting? $\endgroup$ – D.W.♦ May 24 '14 at 1:11
  • 1
    $\begingroup$ I just thought that maybe for this specific case, a simpler and easier to understand method exists. All methods I've read, such as network simplex, needs a lot of prerequisites and almost all of them apply some assumptions which aren't satisfied in this problem. Do you know a simpler one? I would appreciate. $\endgroup$ – mrmowji May 24 '14 at 1:28
2
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ What if we look at the minimum cost flow as a minimum cost path (shortest path)? I mean, with the last constraint it may make sense. $\endgroup$ – mrmowji May 24 '14 at 1:41
  • 1
    $\begingroup$ A flow isn't a path; for instance, a flow might be a union of multiple paths. Therefore, in general, you cannot look at a flow as a path, and in general, the minimum cost flow is not necessarily a path. (Though a path is a special case of a flow.) $\endgroup$ – D.W.♦ May 24 '14 at 1:45
  • $\begingroup$ I see, we can't do this. Because we can't force the path to goes through a cycle only once, but with flow, we can. Am I right? $\endgroup$ – mrmowji May 24 '14 at 1:45
  • 1
    $\begingroup$ @Mowji, yup, that is indeed an issue that complicates the relationship between flows and paths. If your graph has a negative-cost cycle, a shortest path algorithm will end up trying to traverse that cycle as many times as it can (infinitely many times), but a flow isn't allowed to do that. $\endgroup$ – D.W.♦ May 24 '14 at 1:53
  • $\begingroup$ Thank you very much. I'll try your answer but meanwhile I'll look for a desired one. Thanks again. $\endgroup$ – mrmowji May 24 '14 at 2:00

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.