I'm trying to find a solution to a problem:

I'm given a connected network $G=(V,E,c)$, where c is an edge capacity.
I also have pairs of terminal nodes $s_i\in V$ and $t_i\in V$, a flow value $f_i\in \mathbb{N}$ and a capacity coefficient $\alpha_i\in [0,1]$, where $i\in 1,\dots,k$.

The problem is to find a path $P_i$ between $s_i$ and $t_i$ $\ \forall i\in 1,\dots,k$, such that for every edge $e$ the sum of all flow values do not exceed capacity constraints for every other path containing that edge:

$$\sum_{\{i\ |\ e\in P_i\}} {f_i}\leq c(e)\alpha_j\ \ \ \forall e\in E\ \ \forall j:\ e\in P_j$$

  • What to do with these parametrized constrains?
  • Is there any existing problem that looks like this?
  • Does it have a solution?

If I change this problem into an optimization problem, by demanding that paths $P_i$ must be shortest paths, how does it change the problem and the algorithm?


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.