how to express the following constraint for linear programming

135 Views Asked by At

I would like to express the following constraints mathematically:

For a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} \gt 0$ should be less than $W^f$.

I apologize I am not able to express myself correctly, English is not my first language, So I will give an example.

In this example scenario only edges $(1, 2)$ and $(2, 5)$ have $x^f_{ij} \gt 0$ therefore the sum of weight of these two edges should be considered, i.e., $w_{12} + w_{25} \le W^f$

Solution, Edit 1 $$ \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} $$

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

$$0 \le x^f_{i,j} \le My^f_{i,j}, \,\, y^f_{i,j} \in \{0, 1\} \quad \forall (i,j) \in E, f \in F$$

1

There are 1 best solutions below

2
On BEST ANSWER

You need to multiply the weights by a binary variable $y_{ij}^f$ that takes value $1$ only when $x_{ij}^f > 0$. A big-M constraint should do the trick : $$ \sum_{(i,j)} w_{ij}y_{ij}^f \le W^f \\ x_{ij}^f \le M y_{ij}^f \\ y_{ij}^f \in \{0,1\} $$