Answers to: one last constraint for the tsp problem in MIPhttp://www.or-exchange.com/questions/11874/one-last-constraint-for-the-tsp-problem-in-mip<p>Hi, I am practicing some more GAMS code, and I found a 6 and a 5 city problem.</p>
<p>Now, I am doing the five city problem.</p>
<p>I modeled the solution as follows. Let \(X_{ij}\) be a binary variable that is set to value \(1\) when city \(j\) is visited directly from city \(i\), and \(C_{ij}\) to represent the respective cost/distance.</p>
<p>The objective is to:</p>
<p>\[\text{minimize} \sum C_{ij}X_{ij}\]</p>
<p>subjected to the following constraints: </p>
<p>\[
\sum_{j} X_{ij} = 1 \quad\forall ~i\\
\sum_{i} X_{ij} = 1 \quad\forall ~j
\]</p>
<p>Of course, the cost \(C_{jj}\) should be made abnormally big to avoid one length sub tours.</p>
<p>Now to eliminate the sub tours i got two ideas:</p>
<ol>
<li>
<p>Since I only have 5 cities, I think it is sufficient to eliminate 1-length sub tours and 2-length sub tours; i.e., also add: \[X_{ij} + X_{ji} \le 1\]</p>
</li>
<li>
<p>Or to apply this other one: \[p_i - p_j \le 5*(1-X_{ij}) - 1\] with \(p_i\) being the position of the currently visited city \(i\).</p>
</li>
</ol>
<p>I prefer the first constraint since I think I understand it more.</p>
<p>I have a GAMS implementation, but it is giving me errors.</p>
<p>Any suggestions as to how I can apply the first sub tour elimination constraint in GAMS without getting errors?</p>
<p>Below is gams code. Thanks.</p>
<pre><code>set i city /1,2,3,4,5/
j cost /c1,c2,c3,c4,c5/;
table cost(i,j)
c1 c2 c3 c4 c5
1 10000 67 97 69 78
2 42 10000 77 66 85
3 34 29 10000 13 34
4 11 92 17 10000 38
5 12 90 87 21 10000;
variables x(i,j), z, t(i);
binary variable x;
equations
obj
const1(i)
const2(j)
const3(i,j);
obj.. z =e= sum((i,j),x(i,j)*cost(i,j));
const1(i).. sum(j$(ord(j) ne ord(i)),x(i,j)) =e= 1;
const2(j).. sum(i$(ord(i) ne ord(j)),x(i,j)) =e= 1;
const3(i,j).. x(i,j) + x(j,i) =l= 1;
model TSP /all/;
solve TSP using MIP minimizing z;
display x.l;
</code></pre>enTue, 07 Apr 2015 18:56:55 -0400Answer by erwinhttp://www.or-exchange.com/questions/11874/one-last-constraint-for-the-tsp-problem-in-mip/11902<p>Start with:</p>
<pre><code>set i city /c1*c5/;
alias (i,j);
table cost(i,j)
c1 c2 c3 c4 c5
c1 67 97 69 78
c2 42 77 66 85
c3 34 29 13 34
c4 11 92 17 38
c5 12 90 87 21
;
set ij(i,j) 'off diagonal elements';
ij(i,j)$(ord(i)<>ord(j)) = yes;
display ij;
</code></pre>
<p>Then you can write the assignment part of the model as:</p>
<pre><code>equations
obj 'objective'
assign1(i) 'assignment constraints'
assign2(j) 'assignment constraints'
;
obj.. z =e= sum(ij,x(ij)*cost(ij));
assign1(i).. sum(ij(i,j),x(i,j)) =e= 1;
assign2(j).. sum(ij(i,j),x(i,j)) =e= 1;
</code></pre>erwinTue, 07 Apr 2015 18:56:55 -0400http://www.or-exchange.com/questions/11874/one-last-constraint-for-the-tsp-problem-in-mip/11902Answer by Ehsanhttp://www.or-exchange.com/questions/11874/one-last-constraint-for-the-tsp-problem-in-mip/11884<p>Instead of defining two separate sets for the indices \(i\) and \(j\), you should define just one set (i.e., define the first one, say set city for index \(i\), and then define the next index using the alias keyword). Your way of defining sets would result in error regarding the \(X_{ij}\) variable as you need to use both \(X_{ij}\) and \(X_{ji}\) in your subtour elimination constraints.</p>
<p>PS. The next time you want to ask question on any forum, remember to give more information. Most people don't even bother reading vague questions. Instead of saying that "everything is ruined" or "the program gives errors", say what is the exact error or message provided by the program.</p>EhsanTue, 07 Apr 2015 05:56:36 -0400http://www.or-exchange.com/questions/11874/one-last-constraint-for-the-tsp-problem-in-mip/11884