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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.