# How to propagate time using linear inequalities?

I have an adjacency matrix $$G_{i,j}$$ that tells the distance between $$i$$ to $$j$$ (between 0 to 1) if there is no edge between $$i$$ to $$j$$ I am putting a large integer $$100$$.

This is my previous question related to it.

I am trying to linearize the following equation:

$$s$$ is the starting point, $$e$$ is the ending point.

$$\text{time}_j = \sum_i b_{i,j}\times \text{time}_i + G_{i, j}$$

My linearization is:

\begin{align}\text{time}_s&= 3.0\\\text{time}_j&\geq\text{time}_i + G_{i, j} - M \times(1 - b_{i, j})\\\text{time}_j&\leq\text{time}_i + G_{i, j}\\\text{time}_j&\geq 0\\\text{time}_j&\leq M \times b_{i, j}\end{align}

Value of $$M$$ is also $$100$$. Solver can't find the solution for this. If I remove the last 3 equations from linearization it finds the solution but for some node value of $$\text{time}_j$$ reaches to limit value $$M$$.

After the answer of @prubin: \begin{align} \text{time}_s&= 3.0\\ \text{time}_j&\geq\text{time}_i + G_{i, j} - M \times(1 - b_{i, j})\\ \text{time}_j&\leq\text{time}_i + G_{i, j} + M \times(1 - b_{i, j})\\ \text{time}_j&\geq 0\\ \end{align}

The value of $$time_j$$ is depending on $$time_i$$ and $$b_{i,j}$$ I can only decide whether value of $$time_j$$ is $$0$$ or dependent on $$time_i$$ when I have seen value of all $$i$$ in $$b_{i,j}$$ i.e, $$time_j$$ = 0 if $$\sum _i b_{i,j} = 0$$ otherwise it is $$time_j = time_i + G_{i, j}$$ if $$\sum_i b_{i,j} = 1$$ now the important thing to note here is that same $$i$$ should be used in $$time_i$$ for which $$b_{i,j} = 1$$

Now with the above two equations, I iterate through all values of $$i$$ and if it is $$b_{i,j} = 0$$ range of $$time_j$$ is $$[-M, +M]$$ whenever I find the $$b_{i,j} = 1$$ value of $$time_j = time_i + G_{i, j}$$ which is correct.

The problem is that when I don't find any $$i$$ for which $$b_{i,j} = 1$$ i.e., $$\sum_i b_{i,j} = 0$$ in that case the value range of $$time_j$$ is still $$[-M, +M]$$ but due to third equation it becomes $$[0, +M]$$.

My question is how that can be brought to the range $$[0,0]$$ if $$\sum_i b_{i,j} = 0$$

Update:

\begin{align} \text{time}_s&= 3.0\\ \text{time}_j&\geq\text{time}_i + G_{i, j} - M \times(1 - b_{i, j})\\ \text{time}_j&\leq\text{time}_i + G_{i, j} + M \times(1 - b_{i, j})\\ \text{time}_j&\geq 0\\ \text{time}_j&\leq M \times \sum_i b_{i,j}\\ \end{align}

• The problem that I have noticed so far is that the value of $\text{time}_j$ goes to the limit value M only for the last node i.e., $e$.
– ooo
Jan 25, 2020 at 14:30
• I modified my objective function and added the last node $\text{time}_e$ to it, now I am getting the proper results but processing time is increased, but my question is still that why the above relaxation not working.
– ooo
Jan 25, 2020 at 14:38
• I can't find how to bound $\text{time}_e$ so that it does not move to limit value.
– ooo
Jan 25, 2020 at 17:39
• For further reference of others, it would be helpful if you found a more "descriptive" title of your question: what is it that you actually want to ask? Jan 26, 2020 at 9:30
• OK, I will update the question.
– ooo
Jan 26, 2020 at 10:27

The constraint $$\mathrm{time}_j \le \mathrm{time}_i + G_{i,j}$$ is incorrect. It bounds $$\mathrm{time}_j$$ regardless of whether node $$j$$ follows node $$i$$ or not. Add the same "big M" term that you subtracted in the previous constraint.

• But how can I use equals to zero case, as I am generating these conditions through loops for $i$ and $j$.
– ooo
Jan 27, 2020 at 18:21
• What do you mean by "equals to zero case"?
– prubin
Jan 27, 2020 at 23:18
• I have added a detail explanation in the question above. basically I am talking about the case when $\sum_i b_{i,j} = 0$
– ooo
Jan 28, 2020 at 7:58
• I have added linearization according to me at the end as an update , can you verify it.
– ooo
Jan 28, 2020 at 8:16
• It looks okay to me.
– prubin
Jan 29, 2020 at 19:20