[AMPL 24834] TSP Dantzig–Fulkerson–Johnson DFJ subtour elimination

Google Group Mirror
1

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,

2

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.

3

Thanks