1
$\begingroup$

I am working on a multi-commodity flow problem where for a graph $G=(V, E)$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as follows.

Problem Formulation

$$ \min \sum_{(i,j) \in E} \sum_{f \in F} c_{ij}^fx^f_{ij}$$

$$ \sum_{j \in V}x^f_{ij} - \sum_{j \in V}x_{ji}^f = \begin{cases} d_f &, & i = s_f \\ -d_f&, & i = t_f\\ 0 &,& \text{otherwise} \end{cases} $$ $$ x_{ij}^f \ge \begin{cases} 0 & , & f \in S\\ d_f & , & f \in NS\\ \end{cases} \quad \forall (i, j) \in E$$ $$ \sum_{i,j \in E} x_{ij}^f \le u_{ij}$$

Where $d_f$ is the demand for flow $f$. $S$ is the set of flows that are permitted to be split, and $NS$ is the set of non-splittable flows. $u_{ij}$ is the capacity of edge $(i, j)$.

I am a novice in linear programming. On paper, using two simple graphs, this formulation seems to work fine.

I would appreciate it if someone could point out if there is any problem with this formulation.

$\endgroup$
4
  • $\begingroup$ I don't quite know what exactly you are looking for. It's a legitimate linear programming problem alright and as long as the costs $c_{ij}^f$ are positive, it's also guaranteed to have a solution because your solution variables are required to be positive. Are you asking whether the model is reasonable? We can't tell you anything about that because we don't know in detail what you are trying to model. $\endgroup$ Oct 5, 2018 at 3:00
  • $\begingroup$ Thank you @WolfgangBangerth. I wasn't sure if my problem formulation is a legitimate LP. Also, to force the non-splittable flows to follow one path only, without turning this problem into a MIP, I added this constraint: $$ x_{ij}^f \ge \begin{cases} 0 & , & f \in S\\ d_f & , & f \in NS\\ \end{cases} \quad \forall (i, j) \in E$$ So, I wanted to know whether this constraint does what I expect it to do or not. $\endgroup$
    – Corey
    Oct 5, 2018 at 7:31
  • $\begingroup$ We don't know -- we don't know what all of your variables are supposed to mean. Your problem sounds like it is bounded from below, but I can't say whether your constraints allow for at least one feasible point. $\endgroup$ Oct 5, 2018 at 21:25
  • $\begingroup$ On another forum, someone commented: "your program does not allow $x^f_{ij}$ to be 0 if $f \in NS$, which seems incorrect. You have to use binary variables for $f \in NS$ and $(i,j) \in E$ to ensure that $x^f_{ij}$ is either $0$ or $d_f$ ". It is not clear to me why the program should allow $x^f_{ij}$ to be 0 if $f \in NS$. Sadly he didn't elaborate on this point. Can someone please tell me what he meant by this? $\endgroup$
    – Corey
    Oct 6, 2018 at 9:38

1 Answer 1

1
$\begingroup$

With your current model you are forcing your non splittable flows to be equal to your demand on all arcs ( $ x^f_{ij} \geq d_f, \forall f \in NS$). Unless there is a single path from your source to your target this is going to make your problem infeasible, as the flow conservation constraints are going to conflict with this. I am afraid that for non splittable flows you do not have many alternatives to model whether or not a flow goes through an arc using a binary variable, effectively turning your problem into a MIP.

Edit 1: To model the problem as a MIP, for the non-splittable flows you need to replace the $x_{ij}^f$ linear variables by $y_{ij}^f$ binary variables representing if the complete flow goes through arc $ij$ or not. You should then rewrite your constraint and objective function by replacing for non splittable flows $x_{ij}^f$ by $y_{ij}^fd_f$

$\endgroup$
9
  • $\begingroup$ Thank you for your answer Renaud. To check If I understood you correctly, you mean I don't have much choice in formulating this problem, and I should formulate it as a MIP? If yes, would you please tell me how can I formulate it as a MIP because I am totally clueless. $\endgroup$
    – Corey
    Oct 11, 2018 at 22:55
  • $\begingroup$ Finally, I was able to implement this formulation in CPLEX, and then tested it on two simple graphs ([1] i.stack.imgur.com/4qv5k.png, and [2] i.stack.imgur.com/o0uEo.png). However, as @renaud-m expected, CPLEX cannot find any feasible solution (due to either link capacity or flow conservation constraints violation, for different scenarios). I would appreciate it, if someone could explain to me how I can resolve the problem with the formulation, in a simple language (English is not my first language). $\endgroup$
    – Corey
    Oct 12, 2018 at 14:01
  • $\begingroup$ Renaud, thank you for guiding me through this. I read a little bit on MIPs and as you suggested, I tried to reformulate the problem as MIP. I will be grateful if you or anyone else could point out the problems with this new formulation. $\endgroup$
    – Corey
    Oct 15, 2018 at 11:38
  • $\begingroup$ @Corey your formulation looks good. The notation is a bit odd as you are summing y variables even for splittable flows while those variables do not exist for such flows, but otherwise it looks correct to me. $\endgroup$
    – Renaud M.
    Oct 15, 2018 at 12:12
  • $\begingroup$ can you suggest a way to make the notations less odd? $\endgroup$
    – Corey
    Oct 15, 2018 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.