3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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?$ $\endgroup$
    – prubin
    Commented Aug 8, 2022 at 15:09
  • $\begingroup$ Thanks for the response @prubin, yeah you are right, i'm stuck with the subset of S $\endgroup$
    – overboxed
    Commented Aug 8, 2022 at 15:22
  • $\begingroup$ @overboxed, would you see this link from Gurobi tsp.py example? $\endgroup$
    – A.Omidi
    Commented Aug 9, 2022 at 9:58
  • $\begingroup$ @A.Omidi Thank you, i will check it $\endgroup$
    – overboxed
    Commented Aug 9, 2022 at 13:20

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – overboxed
    Commented Aug 9, 2022 at 1:55
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Commented Aug 9, 2022 at 2:48
  • $\begingroup$ Thank you for your wonderful answer, sir. $\endgroup$
    – overboxed
    Commented Aug 9, 2022 at 13:11
3
$\begingroup$

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)]
$\endgroup$
4
  • $\begingroup$ how to apply this over the constraint? $\endgroup$
    – overboxed
    Commented Aug 9, 2022 at 9:19
  • $\begingroup$ That should be rather obvious, no? $\endgroup$ Commented Aug 9, 2022 at 9:33
  • $\begingroup$ sorry for my ignorance, but i'm quite new in OR and python. Can you elaborate ? $\endgroup$
    – overboxed
    Commented Aug 9, 2022 at 9:35
  • $\begingroup$ You can loop over this list. This is getting close to explaining what a '+' is. $\endgroup$ Commented Aug 9, 2022 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.