TSP Dantzig–Fulkerson–Johnson DFJ subtour elimination

88 views
Skip to first unread message

dmo...@gmail.com

unread,
Oct 18, 2023, 2:26:41 AM10/18/23
to AMPL Modeling Language
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: 

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

unread,
Oct 18, 2023, 1:32:05 PM10/18/23
to AMPL Modeling Language
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

unread,
Oct 18, 2023, 8:06:00 PM10/18/23
to AMPL Modeling Language
Thanks
Reply all
Reply to author
Forward
0 new messages