# How to formulate this in gurobi

I have subtour elimination constraint but can't understand and formulate this in gurobipy. How to formulate this ?

$$\sum_{i \in S} \sum_{j \in S} x_{i j}^{v} \leq|S|-1 \quad v=1, \ldots, m ; S \subseteq V-\{0\}$$

• Can you be more specific about where you are stuck. Is it the part about iterating over all subsets $S$ of $V\backslash \lbrace 0 \rbrace?$
– prubin
Commented Aug 8, 2022 at 15:09
• Thanks for the response @prubin, yeah you are right, i'm stuck with the subset of S Commented Aug 8, 2022 at 15:22
• @overboxed, would you see this link from Gurobi tsp.py example? Commented Aug 9, 2022 at 9:58
• @A.Omidi Thank you, i will check it Commented Aug 9, 2022 at 13:20

I'm going to assume that $$\hat{V}=V\backslash \lbrace 0 \rbrace =\lbrace 1,\dots,m\rbrace$$ for some integer $$m.$$ If $$\hat{V}$$ is something else, you'll need to map the elements of $$\hat{V}$$ (in any arbitrary order) to $$1,\dots,m.$$

There are $$2^m$$ subsets of $$\hat{V},$$ including the empty set. Each subset $$S$$ is associated with a characteristic vector $$z\in \lbrace 0,1 \rbrace^m$$ where $$z_i=1$$ if and only if $$i\in S.$$ Each characteristic vector in turn can be assigned a unique integer index $$\sum_{i=1}^m 2^{z_i}.$$

So to iterate over the subsets, you can iterate over the integers $$1,\dots, 2^m.$$ For each integer in that range, express it as a binary vector and include in $$S$$ the integers in $$\lbrace 1,\dots,m\rbrace$$ corresponding to the locations of the 1 bits.

• Please excuse my ignorance, but what is really the meaninf of subset of S? I don't really quite understand from the point of view of this constraint, let alone the code. Commented Aug 9, 2022 at 1:55
• A subtour is a tour (Hamiltonian circuit, loop) that visits some subset $S$ of the set $V$ of all vertices but does not include the start / depot / origin node 0. To prevent a subtour using the nodes in $S$, you require that the number of arcs within $S$ that are crossed be less than the number of vertices in $S$. So if $S=\lbrace 3, 5, 8\rbrace,$ to prevent a subtour like $3\rightarrow 8 \rightarrow 5 \rightarrow 3$ you add a constraint saying that at most two of the arcs $(3,5), (5,3), (3,8), (8,3), (5,8), (8,5)$ are crossed.
– prubin
Commented Aug 9, 2022 at 2:48
• Thank you for your wonderful answer, sir. Commented Aug 9, 2022 at 13:11

If you are using Python, look into the itertools package. To create the powerset (minus the empty set), we can do:

from itertools import chain,combinations

n = 4
s = range(1,n+1)
list(chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1)))


which produces:

[(1,),
(2,),
(3,),
(4,),
(1, 2),
(1, 3),
(1, 4),
(2, 3),
(2, 4),
(3, 4),
(1, 2, 3),
(1, 2, 4),
(1, 3, 4),
(2, 3, 4),
(1, 2, 3, 4)]

• how to apply this over the constraint? Commented Aug 9, 2022 at 9:19
• That should be rather obvious, no? Commented Aug 9, 2022 at 9:33
• sorry for my ignorance, but i'm quite new in OR and python. Can you elaborate ? Commented Aug 9, 2022 at 9:35
• You can loop over this list. This is getting close to explaining what a '+' is. Commented Aug 9, 2022 at 9:38