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\} $$
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this communityI 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\} $$
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.
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)]