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$
4
  • $\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, 2020 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$
    – ooo
    Mar 10, 2020 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, 2020 at 8:34
  • $\begingroup$ I have edited my question now I hope now I am clear. $\endgroup$
    – ooo
    Mar 10, 2020 at 10:12

2 Answers 2

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.

$\endgroup$
9
  • $\begingroup$ can you provide link to your answer, since I am not aware of your approach. $\endgroup$
    – ooo
    Mar 11, 2020 at 3:40
  • $\begingroup$ I was thinking is to add this MTZ like constraints as a Lazy constraint will it help? $\endgroup$
    – ooo
    Mar 11, 2020 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$ Mar 11, 2020 at 14:39
  • $\begingroup$ I am using the linearized version of that equation using the BigM method. $\endgroup$
    – ooo
    Mar 11, 2020 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$
    – ooo
    Mar 11, 2020 at 17:22
1
$\begingroup$

I'm not really sure what you're trying to accomplish. If you want to eliminate subtours upfront, you can add the constraints right away and then there are no sub-tours (as you observed). Like already mentioned by Daniel Junglas, the problem turns from MILP to MIQCP if the constraints were added in this form. If you are linearizing them, then there are more than $|S|$ constraints, which still explains the slow down. The problem with MTZ-like constraints is, that (to the best of my knowledge) you cannot add a fraction of those, it's either all or nothing, so it doesn't really make sense to me, to add those later on as a lazy constraint.

Considering the fractional solutions: I don't know how your linearized equations exactly look like, but as far as for the MTZ: the relaxations produce very poor bounds so this is also something to be aware of.

Also bear in mind, that your formulation (as well as the MTZ) only work on ATSP and if you got a symmetrical TSP and are formulating it still as ATSP you are introducing a lot of symmetries, which is never good.

What exactly are you trying to accomplish and is it worth it? As far as i know, solving an integer model and adding "standard" SECs as lazy constraints in the callback already gets you pretty far with the current solvers. Could you elaborate more on your goals?

$\endgroup$

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.