2
$\begingroup$

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?

P.S.
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?

$\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.