Is the TSP example's code in Gurobi documentation wrong???

Answered

Jacob Jin

• January 25, 2022 16:41

This is the code in the tsp example:

if len(tour) < n:
            # add subtour elimination constr. for every pair of cities in tour
            model.cbLazy(gp.quicksum(model._vars[i, j]
                                     for i, j in combinations(tour, 2))

The tour list gives the sub-tour with the minimum nodes. For example, 1->3->2->1, or 1->4->6->4->1. We want to add lazy constraint to eliminate subtour. If len(tour) = 3, the code above is correct, However, when the len(tour)=2 or >3, the combinations function gives the wrong combination. 

 

For example, if tour=[1, 4, 5, 7], the lazy constraint should be:

x_14 + x_45 + x_57 + x_71 <= 3

Instead of 

x_14 + x_15 + x_17 + x_45 + x_47 + x_57 <= 3

What's wrong with my understanding?

 

0

• 

  Jacob Jin

  • January 25, 2022 16:42

  

  

  

  if len(tour) < n:          
      model.cbLazy(gp.quicksum(model._vars[i, j] for i, j in combinations(tour, 2))

  0
• 

  Jaromił Najman

  Gurobi Staff

  • January 28, 2022 10:25
  • Edited

  Hi Jacob,

  The subtour elimination constraint reads

  \[\begin{align}
  \sum_{e \in E(S)}x_e \leq |S| - 1 \,\,\forall S \subset V, S \neq \emptyset, S \neq V
  \end{align}\]
  This means that for a given subset of nodes \(S\) of \(V\), the sum over all edges between any of the nodes in \(S\) shall be less or equal to the cardinality of \(S\) minus 1. Thus, the lazy constraint constructed in the tsp example is indeed correct.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.