Is the TSP example's code in Gurobi documentation wrong???
AnsweredThis 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 subtour 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?

if len(tour) < n:
model.cbLazy(gp.quicksum(model._vars[i, j] for i, j in combinations(tour, 2))0 
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.
Comments
2 comments