1
$\begingroup$

I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a real-valued capacity (the maximum amount of flow that an edge can accommodate). Given a source and sink node, algorithms exist which will find the minimum cost flow with tolerable complexity. (I'm mainly interested in integer flow in networks with unit capacity edges, FWIW.) So far so good.

A generalisation of the problem is multi-commodity flow, analogous to having more than one type of substance to be pushed through the network. The costs are different for each commodity, but the capacity is common: the commodities must all fit down the same "pipe". (It can be expressed as above, by converting the flow values and cost values from reals to vectors-of-reals.) Unfortunately "The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two" (Even et al 1975).

I'm looking at a specific specialisation where I have two commodities (X and Y) and the costs are antisymmetric: for every edge, the cost for commodity X is the negative of that for commodity Y. I seek a minimum cost flow algorithm for this case. Maybe it's NP-complete, but I am hoping that the neat antisymmetry of the costs means there is a strategy available.

Simple example:

s12t flow example with 3

Capcities of all edges are 1. The minimum cost in this case is when one unit of "positive" flow travels s-V1-t and one unit of "negative" flow travels s-V2-t, giving a total cost of -4. But:

s12t flow example with 5

In this case, we achieve minimum cost by sending one unit of "positive" flow s-V1-V2-t, giving a total cost of -5.

--

One way to redescribe this problem is to turn it into a single-commodity problem with an abs nonlinearity. In the standard integer flow problem we seek the flow that minimises

$$ \sum_{\text{paths}}{\left( \sum_{\text{arcs in path}}{x_{\text{arc}}a_{\text{arc}}} \right)} $$

where $x$ is flow value and $a$ the cost. We could describe a problem where we seek the minimiser of

$$ \sum_{\text{paths}}{-\text{abs}{\left( \sum_{\text{arcs in path}}{x_{\text{arc}}a_{\text{arc}}} \right)}} $$

and then if we can solve that, we can inspect the solution to work out which flow paths belong to X and Y. However the nonlinearity added in there is thorny.

--

So my question is, can you think of any way to convert this problem to something for which algorithms are known (e.g. a single-commodity problem)? I'd also be grateful for any literature that can help me with this.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.