How to formulate this in gurobi

Question

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\} $$

Answer 1

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.

Answer 2

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)]