It seems to me that a multi-commodity flow problem should be treated differently when the commodity demand constraint is an equivalence and not a lower-bound. Consider a unit demand. Apparently, in such a case, the problem seems easier (and not really a flow problem).

I am not considering the constraint which relates edges with commodities.

My question is whether this intuition is misleading or not. Is the problem still NP-hard?

EDIT: Here's the formulation. For a given graph $G = (V,E)$ with associated capacity function $c : E \rightarrow \mathbb{N}$. Let $K_1, K_2, \dots, K_n$ be a set of commodities, such that $K_i = \{s_i, t_i\}$ -- i.e. a couple of source and sink nodes in $V$ --.

The objective function is a sum over all the flows $f_{e,i} \in \mathbb{N}$.

The first constraint is the flow conservation: $$\sum_{e \in \delta^{-}(v)}f_{e,i} - \sum_{e \in \delta^{+}(v)} f_{e,i} = 0,\ \forall i \in \{1,\dots, n\}\text{ and }\forall v \in V\smallsetminus K_i.$$

The commodity demand constraint is given by: $$\sum_{e \in \delta^{-}(s_i)}f_{e,i} - \sum_{e \in \delta^{+}(s_i)} f_{e,i} = -1,\ \forall i \in \{1,\dots, n\}.$$ $$\sum_{e \in \delta^{-}(t_i)}f_{e,i} - \sum_{e \in \delta^{+}(t_i)} f_{e,i} = +1,\ \forall i \in \{1,\dots, n\}.$$

The final constraint is on the capacity bound

$$\sum_{i = 1}^n{f_{e,i}} \leq c(e),\ \forall e \in E$$

  • $\begingroup$ Can u post the full model $\endgroup$ Jul 29, 2021 at 16:31
  • $\begingroup$ What makes you think the problem is easier ? Is it a fact or an intuition? $\endgroup$
    – Kuifje
    Jul 30, 2021 at 18:59
  • $\begingroup$ The fact that, because of the constraints, the flow function is forced to be an $f_{e,i} \in \{0,1\}$. $\endgroup$ Jul 31, 2021 at 18:20
  • 3
    $\begingroup$ Your problem is not precisely defined, in particular your notations. With the information you gave, your problem is simply the integer version of the maximum multi-commodity flow problem. Such a problem is NP-hard even with two commodities and unit capacities. Simply check the Wikipedia page for references: en.m.wikipedia.org/wiki/Multi-commodity_flow_problem $\endgroup$ Aug 1, 2021 at 6:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.