How to introduce flat cost of flow over a node using mixed integer programming. In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program.
\begin{array}{ll}
\text{minimize}   & \sum_{ij} C_{ij} X_{ij} \\
\text{subject to} & \sum_j X_{ij} =\ell_i, ~ i=1,2,\dots,m \\
                  & X_{ij} \geq 0, ~ i=1,2,\dots,m,~j=1,2,\dots,n
\end{array}
Which is basically using the conservation of flow as the constraint.
What I need to be able to do is add a flat "fee" for sending any amount of flow over an arc. I am developing a mixed integer program to model this. I introduced binary variables $y_{ij}$ which give the descision to go over the arc from $i$ to $j$, but after that I am stuck as to how to formulate the problem, does anyone have any ideas on how to modify the boundary conditions so that $y_{ij} = 1$ iff $X_{ij}>0$?
 A: If you're OK with using a Big M type method (although I'm told Big M is considered a bad word in mixed integer programming :)), here's a linear constraint to capture $y_{ij} = 1$ if $X_{ij} > 0$. Use $X_{ij} \leq M_{ij} y_{ij}$. Note that if $X_{ij} > 0$ then $y_{ij}$ is forced to 1. But if $X_{ij} = 0$ then $y_{ij}$ can take values 0 or 1. However, since you will add a cost $\bar{C}_{ij} y_{ij}$ to the objective function, $y_{ij}$ will naturally take the value of 0 in the case where $X_{ij} = 0$ to ensure optimality.
The parameter $M_{ij}$ should be chosen as low as possible. One candidate for the parameter is the sum of the absolute values of the demands. But you might be able to come up with better values depending on your problem data. I think if all your data is integral, then choosing the right value for $M$ is probably not critical.
A: First I would add the constraint, that the quantity, which is transported is equal to the demand:
\begin{array}{ll}
\sum_i X_{ij} =d_j, ~ j=1,2,\dots,n 
\end{array}
For the condition, that $y_{i,j} =1$ if $X_{ij} >0$, there would be the following constrain helpful:
\begin{array}{ll}
y_{ij} \cdot X_{ij} = X_{ij} ~ i=1,2,\dots,m,~j=1,2,\dots,n
\end{array}
Now you can use the variable $y_{ij}$ for the objective function. And you can add sum of all fees.
