TSP Dantzig–Fulkerson–Johnson DFJ subtour elimination

[dmo...@gmail.com]

Hi AMPL team, 

I'm trying to implement the DFJ subtour elimination for the TSP (page 4 https://web2.qatar.cmu.edu/~gdicaro/15382/additional/tsp-formulations.pdf) in AMPL.

The constraint is: 

https://i.imgur.com/nzhJI5M.png

How can I define the S subset V?, I mean, how can I define all subsets S. For example, if V is {1..4}, S can be:

{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4},

{1, 2, 3}, {1, 2, 4},  {1, 3, 4}, {2, 3, 4}

This is the power set except for all subsets with one element and the final complete set {1,2,3,4}.

Thank you in advance

Regards,

[AMPL Google Group]

See How can I get AMPL to index over the “power set” consisting of all subsets of a set? in our Frequently Asked Questions. In the answer to this question, the TSP subtour elimination constraints are given as an example.

--
Robert Fourer

We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.

{#HS:2393346309-120062#}

[dmo...@gmail.com]

Thanks