How to write milp equation for this problem?

Question

Consider the classic network flow problem where the constraint is that the outflow from a vertex is equal to the sum of the inflows to it. Consider having a more specific constraint where the flow can be split between edges.

I have two questions:

1. How can I use a decision variable to identify that node j is receiving items from multiple edges?

2. How to create another equation to determine the cost (2 unit of time per item) of joining x number of items from different edges in the sink node?

Answer 1

This is a tricky modeling question. Let's go by parts.

Consider having a more specific constraint where the flow can be split between edges

I here assume that you have a classic flow constraint modeled as a real variable set y_ij. Therefore, the flow can be split between two or more arcs.

How can I use a decision variable to identify that node j is receiving items from multiple edges?

You need to create an additional binary variable z_ij to represent your flow. You must also create the following constraint:

Next, you will need another additional integer variable set, let's say p_i and an additional constraint

Then, p_i will store the number of ingoing arcs in a node j which are used to send flow. Since you will try to minimize the cost of joining arcs (I think), you need to use the <=.

How to create another equation to determine the cost(2 unit of time per item) of joining x number of items from different edges in the sink node?

For this, you can use the value of p_i and multiply by the predefined cost of joining the flow.