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:

  1. 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\]

  2. 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's gravatar image

alexmath
2126
accept rate: 0%

edited 07 Apr '15, 09:51

fbahr's gravatar image

fbahr ♦
4.6k716

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

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.

link

answered 07 Apr '15, 05:56

Ehsan's gravatar image

Ehsan ♦
4.8k31122
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

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;
link

answered 07 Apr '15, 18:56

erwin's gravatar image

erwin
40113
accept rate: 10%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 06 Apr '15, 17:40

Seen: 1,600 times

Last updated: 07 Apr '15, 18:56

OR-Exchange! Your site for questions, answers, and announcements about operations research.