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$


\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}

  • $\begingroup$ 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$. $\endgroup$ – ooo Jan 25 '20 at 14:30
  • $\begingroup$ 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. $\endgroup$ – ooo Jan 25 '20 at 14:38
  • $\begingroup$ I can't find how to bound $\text{time}_e$ so that it does not move to limit value. $\endgroup$ – ooo Jan 25 '20 at 17:39
  • $\begingroup$ 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? $\endgroup$ – Marco Lübbecke Jan 26 '20 at 9:30
  • $\begingroup$ OK, I will update the question. $\endgroup$ – ooo Jan 26 '20 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.