I have the following Integer Linear Programming model:
$\text{min} Z = 6x_{1,3} + 5x_{1,4} + 2x_{1,2} + 3x_{2,3} + 5x_{2,4} + 2x_{3,5} + 4x_{4,5} + 100(y_{1,3} + y_{1,4} + y_{1,2} + y_{2,3} + y_{2,4} + y_{3,5} + y_{4,5})$
The constraints are :
$y_{i,j} = \begin{cases}1 \text{ if } x_{i,j} > 0 \\ 0 \text{ if } x_{i,j} = 0 \end{cases}$
$x_{1,3} + x_{1,4} + x_{1,2} \leq 20$
$x_{1,3} \leq 10$
$x_{1,4} \leq 20$
$x_{1,2} \leq 20$
$x_{2,3} + x_{2,4} \leq 30$
$x_{2,3} \leq 25$
$x_{2,4} \leq 30$
$x_{3,5} \leq 30$
$x_{4,5} \leq 30$
Now I'm tasked with relaxing the above model and to describe it as a minimal cost flow problem.
What I'm trying to do is to first come up with a minimal cost flow problem without taking into account the binary variables of the previous model.
This is what I get:
$\text{min} Z = 6x_{1,3} + 5x_{1,4} + 2x_{1,2} + 3x_{2,3} + 5x_{2,4} + 2x_{3,5} + 4x_{4,5} $
With the following constraints :
$ x_{1,3} + x_{1,4} + x_{1,2} = 20 $
$ x_{2,3} + x_{2,4} - x_{1,3} = 10 $
$ x_{3,5} - (x_{1,3} + x_{2,3}) = 0$
$ x_{3,5} - (x_{1,4} + x_{2,4}) = 0$
$ -(x_{3,5} + x_{4,5}) = -30$
How can I take into account the binary variables of the first model in this minimal cost flow problem?
To link the $x$ and $y$ variables, let $M_{i,j}$ be a constant upper bound on $x_{i,j}$ and introduce linear big-M constraints $$x_{i,j} \le M_{i,j} y_{i,j}$$ that enforce $x_{i,j} > 0 \implies y_{i,j} = 1$. For example $M_{1,3} = 10$.