$ontext eil51, 51 city problem using Svestka formulation Erwin Kalvelagen, Amsterdam Optimization Original TSP formulation from [4] References: [1] Gerhard Reinelt, Universitaet Heidelberg, TSPLIB95 [2] A.J. Orman & H.P. Williams, A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem [3] J.A. Svestka, A continuous variable representation of the TSP, Math Prog, v15, 1978, pp211-213 [4] Jon Lee and J.F. Raffensperger, Using AMPL for teaching the TSP, INFORMS Transactions on Education, 7(1):38-70, 2006 $offtext $eolcom // set i /i1*i51/; table xy(i,*) x y i1 37 52 i2 49 49 i3 52 64 i4 20 26 i5 40 30 i6 21 47 i7 17 63 i8 31 62 i9 52 33 i10 51 21 i11 42 41 i12 31 32 i13 5 25 i14 12 42 i15 36 16 i16 52 41 i17 27 23 i18 17 33 i19 13 13 i20 57 58 i21 62 42 i22 42 57 i23 16 57 i24 8 52 i25 7 38 i26 27 68 i27 30 48 i28 43 67 i29 58 48 i30 58 27 i31 37 69 i32 38 46 i33 46 10 i34 61 33 i35 62 63 i36 63 69 i37 32 22 i38 45 35 i39 59 15 i40 5 6 i41 10 17 i42 21 10 i43 5 64 i44 30 15 i45 39 10 i46 32 39 i47 25 32 i48 25 55 i49 48 28 i50 56 37 i51 30 40 ; alias (i,j); parameter c(i,j); set arcs(i,j); arcs(i,j)$(not sameas(i,j)) = yes; c(arcs(i,j)) = round(sqrt(sqr(xy(i,'x')-xy(j,'x'))+sqr(xy(i,'y')-xy(j,'y')))); scalar n 'number of nodes'; n = card(i); binary variables x(i,j); positive variables y(i,j); variable z; scalar f /0.01/; equations tourlength DemandY(i) FlowY(i) TotalX ArcGain(i,j) DemandX(i) FlowX(i) StartX StartY ; set i2(i); i2(i)$(ord(i)>=2) = yes; tourlength.. z =e= sum(arcs, c(arcs)*x(arcs)); DemandY(i2(i)).. sum(arcs(i,j), y(j,i)) =g= 1; FlowY(i2(i)).. sum(arcs(i,j), y(i,j)) - sum(arcs(i,j), y(j,i)) =e= f; TotalX.. sum(arcs, x(arcs)) =L= n; ArcGain(arcs).. y(arcs) =l= (1+n*f)*x(arcs); // These rows tighten the model. DemandX(i2(i)).. sum(arcs(i,j), x(j,i)) =e= 1; FlowX(i2(i)).. sum(arcs(i,j),x(i,j)) =e= sum(arcs(i,j),x(j,i)); StartX.. sum(i2(i), x('i1',i)) =e= 1; StartY.. sum(i2(i), y('i1',i)) =e= 1; option optcr=0; option iterlim=10000000; model tsp/all/; solve tsp minimizing z using mip; display x.l; parameter tour(i,*); loop((i,j)$(x.l(i,j)>0.5), tour(i,'x0') = xy(i,'x'); tour(i,'y0') = xy(i,'y'); tour(i,'x1') = xy(j,'x'); tour(i,'y1') = xy(j,'y'); ); display tour;