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

回答済み

Jacob Jin

2022年01月25日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:45

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jacob Jin

  2022年01月25日 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

  2022年01月28日 10:25 編集済み

  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

投稿コメントは受け付けていません。