The Graph

I've been looking into a flow optimization problem (please follow the above link to view the directed acyclic graph with the source and multiple sinks) We have a single source 1 and multiple sinks $R_1$, $R_2$,.. $R_{n_R}$. The graph is $G=[N,L]$ where $N$ is the set of Nodes and $L$ is the set of links. The problem description is as follows:

  1. Each sink has a demand $d_k$ which must be satisfied, else there will be penalty associated with it. If we denote incoming flow to link by $v_k$, we need to $minimize \sum_{k=1}^{n_R}(\lambda_k^-(\Delta_k^-) + \lambda_k^+(\Delta_k^+))$ - i.e. summed over all sinks - where $\lambda^-$ and $\lambda^+$ are integer penalty multipliers associated with shortage and surplus respectively and $\Delta_k^- = max\{0,d_k-v_k\}$ and $\Delta_k^+ = max\{0,v_k-d_k\}$
  2. Let us denote the flow on a link by $f_a$. Each link has a cost to transport unit flow which is denoted by $c_a(f_a)$ i.e. cost of transporting unit flow is a function of the flow. Therefore total cost to transport $f_a$ units of flow is $\hat{c}_a(f_a) = f_a \times c_a(f_a)$. Eg: if cost to transport unit flow $c_a(f_a) = 2f_a + 3$, the cost to transport $f_a$ units of flow is $\hat{c}_a(f_a) = 2f_a^2+3f_a$. We need to minimize this cost over all links $minimize \sum_{a\in L}\hat{c}_a(f_a)$
  3. On each link $\{u,v\}$, only a fraction $\alpha$ of the flow reaches $v$. Let us denote this by $f_a'$. Hence $f_a' = \alpha_af_a \forall a \in L$ where $0<\alpha<1, \alpha \in \mathbb{R}$
  4. Flow conservation constraints for each node in $N$. $\sum_{a\in\{Incoming Links\}}\alpha_af_a = \sum_{a\in\{Outgoing Links\}}f_a$. Also, the incoming flow to each sink $R_k$ is $\sum_{a\in\{IncomingLinksToR_k\}}\alpha_af_a$

To summarize, we have to $minimize (1.) + (2.)$ subject to (3.) and (4.) We could of course express the problem in terms of path flows instead of link flows. My questions are as follows:

  1. Which standard problem is this closest to? Min-Cost Flow/Fractional Multi-Commodity Flow/Maximum Concurrent Flow,etc. It would greatly help if these kind of problems have already been analyzed in depth.
  2. If they've been analyzed, do we have an algorithmic approach or do we have to resort to linear programming/quadratic programming (general approaches)
  3. Is this problem, in some sense, easier than the Multi-Commodity Flow problem? Over there we have to maximize flow while trying to satisfy the demand of each pair and constrained by capacities. Here we have no capacities. But the objective function also includes cost for link flows now.
  4. We could formulate the dual from the path flow form of the primal or the link flow form. Would the dual of the path flow primal lead to something more interpretable (than the link flow formulation dual), in general, in these kind of cases?
  5. What sort of cut function could we expect from the dual? Is it some sort of a sparsest cut/min cut, etc.
  • $\begingroup$ Interesting question. Just out of curiosity, what's the motivation behind it? $\endgroup$ – wonko Nov 9 '17 at 20:56
  • $\begingroup$ I was looking into the duality between flows and cuts. Somehow, I haven't been able find much literature (or any for that matter) on cuts, where the dual has cost for the flows which is part of the objective function. Hence, I thought I would look at a concrete example and see what I could come up with. I'm trying to get a hold on flow optimization, hence. $\endgroup$ – rasalghul Nov 10 '17 at 4:53

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.