# one last constraint for the tsp problem in MIP

 0 Hi, I am practicing some more GAMS code, and I found a 6 and a 5 city problem. Now, I am doing the five city problem. 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. The objective is to: $\text{minimize} \sum C_{ij}X_{ij}$ subjected to the following constraints: $\sum_{j} X_{ij} = 1 \quad\forall ~i\\ \sum_{i} X_{ij} = 1 \quad\forall ~j$ Of course, the cost $$C_{jj}$$ should be made abnormally big to avoid one length sub tours. Now to eliminate the sub tours i got two ideas: 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$ 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$$. I prefer the first constraint since I think I understand it more. I have a GAMS implementation, but it is giving me errors. Any suggestions as to how I can apply the first sub tour elimination constraint in GAMS without getting errors? Below is gams code. Thanks. 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; asked 06 Apr '15, 17:40 alexmath 21●2●6 accept rate: 0% fbahr ♦ 4.6k●7●16 It does not make much sense to have x both in "variables" and "binary variable". Furthermore, you should improve your question style: More structure, less spelling mistakes. (07 Apr '15, 03:42) JF Meier Got it. The thing is though, without the sub tour eliminating constraint it works fine. But adding that just ruins everything. Any suggestions on how to fix it? (07 Apr '15, 03:52) alexmath Maybe you correct and structure your question, and also explain what you mean by "ruins everything". (07 Apr '15, 04:33) JF Meier By "ruins everything" I mean, starts giving errors. Ok, I will structure the question after a few hours. (07 Apr '15, 04:37) alexmath well, i hope thats better now :). is something still unclear? (07 Apr '15, 05:34) alexmath It is still messed up with typing errors and formatting errors. If you expect reasonable answers, you need to write clear and correct, in full sentences and with correct mathematical notation. (07 Apr '15, 07:39) JF Meier thanks @fbahr, now i know how to use some latex commands too. @JF Meier. Which part do "you" find unclear/messy? (07 Apr '15, 08:48) alexmath Why was this down voted? i wish to know the reason so that next time i dont repeat the same mistake. Thanks (07 Apr '15, 11:34) alexmath The third version of your question now comes near to "acceptable", but still, the errors and their appearance are not clearly stated. If you want positive votes on your question, it should be clear, precise and without grammar/spelling errors from the beginning. (07 Apr '15, 15:14) JF Meier Oh, ok. Got it. (07 Apr '15, 16:01) alexmath showing 5 of 10 show 5 more comments

 1 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. 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. answered 07 Apr '15, 05:56 Ehsan ♦ 4.8k●3●11●22 accept rate: 16% Thanks @Ehsan. i think i am defining the alias wrongly. i did it this way: SET i /1,2,3,4,5/; Alias (i, j); then in the table replaced all d1, d2,d3,d4,d5 with just 1,2,3,4,5 i got the following errors: - unknown symbol - uncontrolled set entered as constant (07 Apr '15, 06:29) alexmath @alexmath: On which line, is this error shown? (07 Apr '15, 10:40) Ehsan ♦ @Ehsan thanks a lot sir, asking me that made me see the error and, luckily, i was able to correct it. now it is working perfectly using the solution you suggested. No sub tours. it was on the line with the final constraint, one index was missing :))). (07 Apr '15, 11:31) alexmath @alexmath: You're welcome. On a related note, GAMS model library has multiple examples of tackling TSP with different implementations of subtour elimination constraints. You should definitely check them. (07 Apr '15, 11:44) Ehsan ♦ @Ehsan, i would definitely love to. how can i access them? am new to gams, i have done most programming in java and python. And there is only a few documentations on gams. By the way, why was my post down voted? do you have any idea? i wouldn't want to repeat the same mistakes. (07 Apr '15, 11:47) alexmath 1 GAMS Model Library is located under the File menu. Regarding the voting down, I think somebody might have been voted it down due to its initial bad formatting and improper and vague wording of question. Generally, questions like this never get any answer at all. I suggest that you ignore the voting down, but keep in mind what you learned today and use it while asking the next question. Also, make sure that doesn't prevent you from asking any valid and interesting question. (07 Apr '15, 11:57) Ehsan ♦ You only say constructive stuff. thanks really :). i will keep that in mind. and with that, i guess i have to accept your answer now. after all it was the answer :) (07 Apr '15, 15:21) alexmath showing 5 of 7 show 2 more comments
 1 Start with: 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; Then you can write the assignment part of the model as: 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; answered 07 Apr '15, 18:56 erwin 401●1●3 accept rate: 10%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×71
×51
×37