Subtour Elimination constraint

Answered

Mamta Sahare

February 15, 2021 07:25

• 
• 
• 

Kindly suggest
how to write the below constraint in python or jupyter notebook using addConstrs() command

\[\sum_{i\in S} \sum_{j\in S} x_{ij} \leq \lceil S \rceil -1 \quad\forall\quad S\subseteq N_s, \lceil S \rceil \geq 2\]

Specifically how to add- for all S⊆N in the conditional statement.

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:59 Edited

  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 why not try our AI Gurobot?.
• 

  Matthias Miltenberger

  • Gurobi Staff

  February 15, 2021 17:04

  Hi Mamta,

  Did you check our example for the Traveling Salesman Problem? This should give some hints on how to implement the sub-tour elimination constraint.

  Cheers,
  Matthias

  0
• 

  Ismail Gokay Dogan

  April 13, 2022 12:13

  • 
  • 

  Hi Mamta,

  I don't know have you ever solved the problem or not but, I assume you have following sets:

  N: Customers

  N_s: Customers which belong to a depot or carrier (whatever) "s"

  You can calculate all subsets of N_s as following:

  def powerset(s):

      x = len(s)

      masks = [1 << i for i in range(x)]

      for i in range(1, 1 << x):

          yield [ss for mask, ss in zip(masks, s) if i & mask]

   

  subsets = {}

  for s in Depots:

      subsets[s] = powerset(N_s(I dont know how you store N_s))

   

  Then you can manually add variables:

  for s in N_s[s](I dont know how you store N_s):

     for sset in subsets[s]:

          m.addConstr(quicksum(x[i,j] for i in sset for j in sset if i!=j) <= len(sset) -1)

   

   

  0

Post is closed for comments.