Subtour Elimination constraint
AnsweredKindly 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

Hi Mamta,
Did you check our example for the Traveling Salesman Problem? This should give some hints on how to implement the subtour elimination constraint.
Cheers,
Matthias0 
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
Please sign in to leave a comment.
Comments
2 comments