4
$\begingroup$

Referring to the question here.

Given a set $S$, which we need to travel following TSP rules.

I was wondering if this sub tour elimination method is good enough or not?

Let $b_{i,j}$ denote edge from $i$ to $j$ is taken or not and $d_{i,j} > 0$ denotes distance from $i$ to $j$.

\begin{align}\min&\quad\sum_{i,j \in S} d_{i,j} \cdot b_{i,j}\\\text{s.t.}&\quad\sum_{j \in S} b_{j,i} - \sum_{k \in S} b_{i,k} = 0\\&\quad\sum_{j \in S} b_{j,i} = 1\end{align}

Let $s_0$ be the start node. Now use a continuous variable $DS_i$ to store the distance at node $i$, with $DS_{s_0} = 0$.

$$ \forall j \in S \setminus \{s_0\} \quad DS_{j} = \sum_{i} b_{i,j} \cdot (DS_{i} + d_{i,j}) $$

The last constraint eliminates the sub-tour in the path and is similar to MTZ formulation as per the answer given.

In order to speed up the solver, I created a call back where I am trying to eliminate the sub tour, but the problem is due to the last constraint (MTZ equivalent) call back is not getting any sub tour to detect as it is already solved by the last constraint (MTZ equivalent), so the speed is slow.

Here is the log at callback with the last constraint ON:

The total number of nodes = 9.

--> lazy constraint callback called: #1
[0, 4, 1, 6, 2, 5, 8, 7, 3, 0]
--> lazy constraint callback called: #2
[0, 6, 3, 4, 8, 7, 5, 2, 1, 0]
--> lazy constraint callback called: #3
[0, 3, 6, 4, 7, 8, 5, 2, 1, 0]

Here is the log at callback with the last constraint OFF:

The total number of nodes = 9.

--> lazy constraint callback called: #1
[0, 1, 2, 0]
Add violated subtour
--> lazy constraint callback called: #2
[0, 2, 1, 0]
Add violated subtour
--> lazy constraint callback called: #3
[0, 1, 2, 5, 8, 7, 4, 3, 6, 0]
$\endgroup$
  • $\begingroup$ There are some related posts in ORSE. For instance this or this. Also, if you are interested to use the lazy callback to eliminate sub-tours you will find good examples on solvers host, like Gurobi. $\endgroup$ – A.Omidi Mar 10 at 6:50
  • $\begingroup$ My current implementation has DFJ in a lazy callback way, but I am not sure if I add my MTZ equivalent constraint as normal constraint, performance will be equal to MTZ as now callbacks have no sub tours. $\endgroup$ – anoop Mar 10 at 7:09
  • $\begingroup$ Would you try using others sub-tour elimination as described in attached file on the above link? $\endgroup$ – A.Omidi Mar 10 at 8:34
  • $\begingroup$ I have edited my question now I hope now I am clear. $\endgroup$ – anoop Mar 10 at 10:12
5
$\begingroup$

As you only separate SEC's when you find integer feasible solutions, and since your MTZ like constraints eliminate all integer solutions corresponding to subtours, you obviously cannot gain anything from the lazy constraint callback approach. What you however can do, is to separate SEC's from fractional solutions. This require some more work compared to the integer feasible case, but it might be worth it.

| improve this answer | |
$\endgroup$
  • $\begingroup$ can you provide link to your answer, since I am not aware of your approach. $\endgroup$ – anoop Mar 11 at 3:40
  • $\begingroup$ I was thinking is to add this MTZ like constraints as a Lazy constraint will it help? $\endgroup$ – anoop Mar 11 at 3:57
  • 1
    $\begingroup$ From a lazy constraint callback you can add only linear constraints. The constraint you proposed is quadratic since it involves products of binaries. So you cannot inject those constraints from a callback. Moreover, given that you only have |S| constraints of this type, I don't a point in separating them in a callback. You can just add them up front. The slowdown you observe may come from the fact that by adding that constraint you changed your problem from a MILP to a MIQCP. $\endgroup$ – Daniel Junglas Mar 11 at 14:39
  • $\begingroup$ I am using the linearized version of that equation using the BigM method. $\endgroup$ – anoop Mar 11 at 17:20
  • $\begingroup$ If I add them upfront, then as @Sune said callback would have no sub tour. What I am thinking is that, is there any way in which first I complete the callback and remove sub tour and then apply my MTZ like a constraint to get distance propagated in the graph. $\endgroup$ – anoop Mar 11 at 17:22

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.