Latest update

# why the formulation for this minimization problem for multi-commodity flow problem is infeasible?

2018-10-12 17:07:45

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. I have implemented it using CPLEX then tested it on two simple graphs (1,2). However, CPLEX cannot find any feasible solution (due to either link capacity or flow conservation constraints violation, in different scenarios).

This is my first attempt at formulating a problem. I would appreciate it if someone could tell me what is the problem with this formulation or how can I resolve the problem.

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 &,& otherwise \end{cases}$$

$$x_{ij}^f \ge \begin{cases} d_f & , & f \in NS\\ 0 & , & otherwise\\ \end{cases} \quad \forall (i, j) \in E$$

$$\sum_{i,j \in E} x_{ij}^f \le u_{ij}$$

 x