1
$\begingroup$

Consider a node $s$. Let's assume that there are three outgoing arcs from node $s$ namely $(s,i)$,$(s,j)$ and $(s,k)$. Corresponding to each of these arcs, there is a flow proportion value $t_{sj}\in (0,1]$. It means that the amount of flow along the arc $(s,j)$ should be $t_{sj} *f_{ps}$ in which $f_{ps}$ is flow over the single arc going to node $s$. Now in my LP I have the following constraints regarding node $s$:

  1. $f_{ps} = f_{si}+f_{sj}+f_{sk}$
  2. $ f_{si} = t_{si} *f_{ps}$
  3. $ f_{sj} = t_{sj} *f_{ps}$
  4. $ f_{sk} = t_{sk} *f_{ps}$

In a special case, just assume that $\sum_j {t_{sj}}=1$. For example assume that $t_{sj}$ are probability values.

Now, my question is that how I can getting rid of these proportional equality constraints, i.e. constraints 2-4 in our given example. I am looking for a way to modify the structure of the network in such a way to include these constraints implicitly.

$\endgroup$
2
  • $\begingroup$ Are $t_{sj}$ and $f_{ps}$ (for all relevant values of $s, j, p$) both decision variables? If so, your problem looks similar to what are called "pooling problems". A recent reference can be found here. These problems are nonconvex, and there is no known way to reformulate these programs so that they can be solved efficiently (that is, in polynomial time). $\endgroup$ – Geoff Oxberry Jun 21 '12 at 16:29
  • $\begingroup$ t_{sj} is a constant but f_{ps} is a variable. This is the case for all t and f notations. $\endgroup$ – Star Jun 21 '12 at 16:37

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.