Subtour Elimination

[arhn...@gmail.com]

Hello everyone.

So i have a question about subtour elimination if anyone can help. 

In a course i'm doing , here the "way" of subtour elimination as described there. 

For all elements of S, which is a subset of Nc, And for all k belonging into K. The total sum of Xijk <=  |S| - 1 for (i,j) belonging to A. i,j in S, and i not equal to j.

Where, Nc is the set of Customers, K is the set of vehicles, A is the set of Arcs. 

It is also mentioned "Let S ⊆ Nc , S has to be traversed by less than |S| − 1 arcs"

My question is, how to code this in AMPL? As far as i could understand i got to the point of writing 

subject to SubElem{S within Nc, k in K} : sum{(i,j) in A, i in S, j in S, i<>j} x[i,j,k] <= abs[S] - 1; 

which turns out to be wrong, and without the subtour Elimination i get a solution for one of the vehicles of 

:   0   1   2   3   4   5   6   7   8   9    :=

0   .   0   0   0   1   0   0   0   0   0

1   0   .   0   0   0   0   0   0   0   0

2   0   0   .   1   0   0   0   0   0   0

3   0   0   1   .   0   0   0   0   0   0

4   1   0   0   0   .   0   0   0   0   0

5   0   0   0   0   0   .   1   0   0   0

6   0   0   0   0   0   1   .   0   0   0

7   0   0   0   0   0   0   0   .   0   0

8   0   0   0   0   0   0   0   0   .   0

9   0   0   0   0   0   0   0   0   0   .

I don't understand how this works? as far as i can read it says that the vehicle goes from 0 to 4 then from 4 to 0. Then it suddenly goes from 5 to  6 and from 6 to 5.... Am i reading this wrong? or is there something wrong with the Code? or is it because there is no subtour constraints?

Thank you!

[Robert Fourer]

You cannot index a constraint over "S within Nc" where S and Nc are sets. See the following FAQ entry about indexing over all subsets of a set:

http://ampl.com/faqs/how-can-i-get-ampl-to-index-over-the-power-set-consisting-of-all-subsets-of-a-set/

Without proper subtour elimination constraints, you are likely to get impractical subtours like the ones you see in your solution.

Bob Fourer
am...@googlegroups.com

=======