6
$\begingroup$

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}

$\endgroup$
  • $\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$ – anoop Jan 25 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$ – anoop Jan 25 at 14:38
  • $\begingroup$ I can't find how to bound $\text{time}_e$ so that it does not move to limit value. $\endgroup$ – anoop Jan 25 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 at 9:30
  • $\begingroup$ OK, I will update the question. $\endgroup$ – anoop Jan 26 at 10:27
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But how can I use equals to zero case, as I am generating these conditions through loops for $i$ and $j$. $\endgroup$ – anoop Jan 27 at 18:21
  • $\begingroup$ What do you mean by "equals to zero case"? $\endgroup$ – prubin Jan 27 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$ – anoop Jan 28 at 7:58
  • $\begingroup$ I have added linearization according to me at the end as an update , can you verify it. $\endgroup$ – anoop Jan 28 at 8:16
  • $\begingroup$ It looks okay to me. $\endgroup$ – prubin Jan 29 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.