$title GTR with Subtour Elimination $onText Source: www.gams.com/latest/gamslib_ml/libhtml/index.html#gamslib TSP Solution with Subtour Elimination (TSP42,SEQ=213) This model solves a Symmetric TSP using a simple algorithm that adds cuts to exclude subtours found in the previous solution. The data set is dantzig42 from TSPLIB. .. Dantzig, G B, Fulkerson, and Johnson, Solution of a Large-Scale Traveling-Salesman Problem. Operations Research 2 (1954), 393-410. .. Keywords: mixed integer linear programming, traveling salesman problem, iterative subtour elimination, cut generation $offText $eolCom // option optCr = 0, limRow = 0, limCol = 0, solPrint = off; Set i 'cities' / G01, G02, G03, G04, G05, G06, G07, G08, G09, G10, G11, G12, G13, G14, G15, G16, G17, G18, G19, G20, G21, G22, G23, G24, G25, G26, G27, G28, G29, G30, G31, G32, G33, G34, G35, G36, G37, G38, G39, G40, G41, G42, G43, G44, G45, G46, G47, G48, G49, G50, G51/; Alias (i,j,k); Table d(i,j) G01 G02 G03 G04 G05 G06 G07 G08 G09 G10 G11 G12 G13 G02 15.711 G03 11.296 13.242 G04 07.008 08.711 09.622 G05 07.243 09.121 07.101 02.522 G06 20.583 15.279 09.552 16.896 14.693 G07 11.502 12.805 00.524 09.491 06.970 09.221 G08 09.512 11.846 02.198 07.439 04.921 11.075 02.166 G09 17.670 10.112 08.231 12.755 10.913 05.167 07.731 08.759 G10 18.020 02.766 15.980 11.030 11.736 17.278 15.535 14.612 12.159 G11 13.047 07.331 06.185 07.770 06.016 09.425 05.696 05.409 04.985 09.981 G12 19.038 17.595 07.812 16.915 14.452 04.562 07.719 09.879 08.148 19.962 10.627 G13 15.441 02.895 10.977 08.739 08.319 12.392 10.501 09.895 07.227 05.261 04.827 14.752 G14 17.364 12.598 06.681 13.526 11.323 03.373 06.270 07.912 03.005 14.858 06.168 05.183 09.715 G15 10.467 13.318 00.857 09.122 06.615 10.406 01.240 01.724 08.930 16.074 06.472 08.601 11.184 G16 19.880 04.173 16.564 12.876 13.232 16.475 16.083 15.463 11.538 02.413 10.390 19.609 05.594 G17 23.424 14.921 13.047 18.701 16.840 04.349 12.629 14.148 05.949 16.336 10.933 08.874 12.248 G18 09.399 10.507 03.356 06.346 03.835 11.314 03.160 01.379 08.373 13.273 04.409 10.651 08.657 G19 18.750 03.659 16.876 11.781 12.571 18.020 16.430 15.505 12.926 00.896 10.868 20.787 06.125 G20 21.775 06.789 16.204 14.973 14.660 13.843 15.687 15.623 09.483 06.294 10.217 17.574 06.344 G21 00.901 15.012 10.441 06.345 06.402 19.694 10.635 08.628 16.770 17.375 12.162 18.204 14.647 G22 17.134 03.750 11.897 10.480 09.963 11.914 11.396 11.068 06.811 05.365 05.735 14.758 01.747 G23 17.618 05.615 11.078 11.309 10.375 10.054 10.559 10.588 05.025 07.253 05.194 13.105 03.095 G24 12.711 03.014 11.534 05.705 06.357 15.481 11.165 09.822 10.467 05.414 06.410 17.037 03.969 G25 20.102 07.507 12.845 13.839 12.863 09.771 12.321 12.659 05.463 08.470 07.397 13.490 05.436 G26 14.004 05.622 08.049 08.020 06.776 10.231 07.562 07.161 05.272 08.196 01.865 12.039 02.981 G27 13.849 10.928 03.823 10.163 07.859 06.873 03.315 04.498 04.424 13.511 03.649 07.091 08.265 G28 13.113 15.226 02.366 11.980 09.460 08.689 02.604 04.542 08.743 17.921 07.957 05.985 12.778 G29 21.245 09.538 12.999 15.302 14.068 08.342 12.483 13.162 04.939 10.545 08.246 12.422 07.279 G30 13.838 01.891 12.177 06.832 07.398 15.414 11.780 10.581 10.310 04.338 06.685 17.262 03.366 G31 12.905 16.845 03.628 12.803 10.330 10.218 04.042 05.508 10.640 19.571 09.672 06.881 14.498 G32 10.576 05.972 07.920 04.266 03.410 13.197 07.579 06.156 08.676 08.700 03.784 14.012 04.910 G33 23.733 15.158 13.344 19.002 17.146 04.568 12.928 14.454 06.252 16.541 11.235 09.069 12.501 G34 15.690 10.880 05.651 11.547 09.397 05.355 05.164 06.421 02.620 13.273 04.170 06.716 08.041 G35 25.710 15.411 15.809 20.455 18.838 07.470 15.360 16.695 08.045 16.332 12.824 11.987 13.048 G36 09.987 14.440 01.980 09.579 07.143 11.359 02.470 02.609 10.201 17.204 07.742 09.101 12.401 G37 07.719 15.288 04.487 08.941 06.839 13.980 04.908 03.961 12.514 18.035 09.343 11.629 13.634 G38 11.716 14.345 01.115 10.581 08.068 09.593 01.546 03.152 08.865 17.078 07.235 07.328 12.046 G39 14.219 02.037 11.213 07.323 07.343 13.857 10.781 09.814 08.735 04.799 05.393 15.848 01.837 G40 12.110 15.139 01.922 11.311 08.807 09.664 02.334 03.909 09.350 17.868 07.995 07.029 12.814 G41 23.060 09.844 15.436 16.759 15.821 10.711 14.915 15.440 07.496 10.161 10.286 14.927 08.197 G42 24.768 14.125 15.161 19.352 17.811 07.420 14.693 15.907 07.169 15.033 11.798 11.982 11.794 G43 04.744 13.781 06.556 06.181 04.686 15.938 06.781 04.884 13.439 16.419 09.260 14.298 12.703 G44 24.736 15.057 14.673 19.657 17.952 06.252 14.232 15.625 07.075 16.173 11.954 10.778 12.564 G45 08.659 07.088 10.141 01.662 03.306 16.556 09.929 08.037 12.100 09.369 07.188 17.024 07.351 G46 22.110 08.560 14.988 15.684 14.868 11.126 14.464 14.820 07.364 08.866 09.539 15.149 07.033 G47 09.052 11.901 02.563 07.142 04.638 11.536 02.584 00.461 09.169 14.666 05.660 10.303 10.040 G48 16.416 01.139 13.127 09.459 09.610 14.473 12.666 11.891 09.317 02.980 07.046 17.006 02.282 G49 21.878 11.472 12.675 16.386 14.869 06.492 12.183 13.209 04.470 12.684 08.866 10.837 08.983 G50 16.018 15.262 04.737 13.849 11.370 05.556 04.616 06.771 06.867 17.785 08.027 03.110 12.524 G51 18.582 17.330 07.361 16.501 14.032 04.714 07.274 09.436 08.012 19.725 10.305 00.457 14.500 + G14 G15 G16 G17 G18 G19 G20 G21 G22 G23 G24 G25 G26 G15 07.504 G16 14.429 16.778 G17 06.366 13.866 14.980 G18 08.015 03.054 14.191 14.032 G19 15.664 16.971 02.397 16.932 14.165 G20 12.487 16.615 04.091 11.588 14.544 06.470 G21 16.468 09.618 19.185 22.523 08.498 18.123 20.988 G22 09.596 12.206 04.911 11.202 09.916 06.116 04.727 16.328 G23 07.922 11.504 06.517 09.306 09.594 07.970 05.129 16.773 01.920 G24 12.422 11.442 07.172 15.956 08.443 06.227 09.576 12.027 05.593 07.045 G25 08.448 13.375 07.034 07.950 11.789 09.012 04.098 19.249 03.853 02.530 09.396 G26 07.214 08.315 08.526 11.007 06.042 09.074 08.503 13.146 03.909 03.681 05.251 06.107 G27 03.542 04.506 13.659 09.655 04.475 14.385 12.733 12.951 08.787 07.637 10.005 09.149 05.319 G28 06.467 02.916 18.300 12.649 05.717 18.812 17.515 12.301 13.490 12.418 13.727 13.866 09.799 G29 07.683 13.627 09.027 05.979 12.474 11.071 05.670 20.370 05.824 04.202 11.243 02.081 07.329 G30 12.480 12.151 06.044 15.581 09.210 05.176 08.546 13.151 04.825 06.450 01.128 08.675 05.269 G31 08.276 03.789 20.056 14.324 06.839 20.466 19.388 12.161 15.291 14.278 15.155 15.767 11.533 G32 09.901 07.788 09.963 14.582 04.778 09.574 11.252 09.763 06.567 07.130 03.666 09.653 03.755 G33 06.663 14.164 15.154 00.309 14.340 17.127 11.716 22.832 11.433 09.543 16.225 08.132 11.294 G34 02.014 06.385 13.081 07.755 06.291 14.110 11.623 14.789 08.175 06.707 10.491 07.788 05.354 G35 09.199 16.598 14.605 03.121 16.407 16.791 10.768 24.811 11.683 09.955 16.967 07.938 12.484 G36 08.618 01.317 17.988 14.982 03.983 18.099 17.914 09.183 13.472 12.809 12.423 14.692 09.570 G37 11.167 03.668 19.119 17.531 05.003 18.914 19.534 06.994 14.920 14.534 12.892 16.619 11.039 G38 06.990 01.469 17.624 13.325 04.408 17.974 17.152 10.891 12.917 12.024 12.648 13.692 09.100 G39 10.980 11.282 05.916 13.995 08.480 05.694 07.663 13.470 03.457 04.929 02.144 07.253 03.810 G40 07.276 02.193 18.385 13.543 05.196 18.763 17.831 11.309 13.651 12.707 13.456 14.305 09.859 G41 10.258 16.027 08.203 07.711 14.643 10.499 04.240 22.206 06.496 05.469 12.084 02.958 09.062 G42 08.679 15.925 13.318 03.232 15.537 15.495 09.514 23.872 10.403 08.700 15.729 06.643 11.350 G43 12.796 05.724 17.853 18.999 05.073 17.257 18.956 03.907 14.230 14.283 11.043 16.627 10.607 G44 08.033 15.472 14.584 01.905 15.391 16.687 10.903 23.835 11.308 09.500 16.425 07.706 11.753 G45 13.224 09.759 11.242 17.998 06.786 10.119 13.476 08.007 09.098 10.097 04.074 12.613 07.072 G46 10.271 15.528 06.954 08.529 13.939 09.222 03.110 21.268 05.304 04.498 10.868 02.162 08.168 G47 08.369 01.981 15.585 14.594 01.398 15.558 15.856 08.168 11.264 10.852 09.783 12.967 07.369 G48 11.930 13.276 03.657 13.915 10.592 03.846 05.745 15.686 02.713 04.621 03.866 06.395 05.233 G49 06.599 13.391 11.246 03.746 12.737 13.245 07.872 20.985 07.723 05.911 12.870 04.234 08.385 G50 04.026 05.552 17.734 09.699 07.553 18.645 16.253 15.170 12.823 11.391 14.368 12.312 09.640 G51 05.021 08.148 19.421 09.054 10.224 20.557 17.470 17.749 14.553 12.930 16.711 13.398 11.753 + G27 G28 G29 G30 G31 G32 G33 G34 G35 G36 G37 G38 G39 G28 04.783 G29 09.185 13.676 G30 10.331 14.298 10.601 G31 06.658 01.905 15.576 15.805 G32 06.930 10.169 11.047 04.480 11.525 G33 09.961 12.926 06.138 15.840 14.592 14.877 G34 01.931 06.154 07.528 10.615 08.058 07.888 08.063 G35 12.217 15.612 05.876 16.405 17.339 16.216 02.918 10.286 G36 05.782 03.132 14.932 13.190 03.270 08.758 15.276 07.629 17.774 G37 08.108 05.648 17.074 13.806 05.190 09.343 17.829 10.019 20.262 02.627 G38 04.561 01.462 13.723 13.291 02.513 09.028 13.615 06.248 16.186 01.812 04.430 G39 09.029 13.224 09.116 01.592 14.822 04.049 14.256 09.159 14.877 12.405 13.298 12.318 G40 05.156 01.050 14.251 14.097 01.709 09.835 13.826 06.733 16.465 02.126 04.601 00.808 13.115 G41 11.646 16.213 02.577 11.256 18.116 12.599 07.789 10.059 06.543 17.340 19.387 16.204 09.952 G42 11.474 15.144 04.587 15.145 16.926 15.097 03.141 09.553 01.300 17.138 19.571 15.614 13.628 G43 09.347 08.400 17.473 12.083 08.367 07.903 19.306 11.248 21.459 05.293 03.356 06.984 11.939 G44 11.133 14.420 05.627 15.930 16.135 15.448 01.720 09.204 01.222 16.631 19.139 15.022 14.373 G45 10.051 12.503 14.196 05.200 13.528 03.425 18.292 11.213 19.551 10.400 10.113 11.175 05.814 G46 11.262 15.941 02.785 10.011 17.845 11.582 08.643 09.816 07.687 16.846 18.780 15.817 08.749 G47 04.940 04.869 13.519 10.579 05.712 06.122 14.900 06.859 17.124 02.659 03.683 03.444 09.875 G48 10.539 15.002 08.440 02.804 16.688 06.309 14.145 10.305 14.316 14.451 15.485 14.212 02.269 G49 08.888 12.967 02.234 12.348 14.825 12.131 03.909 07.026 04.124 14.651 16.985 13.247 10.800 G50 04.379 03.223 11.694 14.710 04.663 11.150 09.959 04.684 12.753 06.195 08.796 04.384 13.395 G51 06.739 05.529 12.393 16.958 06.450 13.647 09.259 06.458 12.173 08.645 11.174 06.871 15.560 + G40 G41 G42 G43 G44 G45 G46 G47 G48 G49 G50 G41 16.757 G42 15.948 05.311 G43 07.418 19.541 20.606 G44 15.284 06.770 01.602 20.422 G45 11.945 15.489 18.402 07.616 18.821 G46 16.414 01.304 06.419 18.742 07.793 14.367 G47 04.170 15.771 16.325 04.427 16.060 07.817 15.126 G48 14.993 08.705 13.026 14.206 13.990 07.880 07.422 11.990 G49 13.672 04.252 02.966 17.808 03.590 15.443 04.870 13.610 10.414 G50 04.255 14.271 12.428 11.274 11.539 14.032 14.226 07.198 14.806 10.588 G51 06.574 14.917 12.122 13.843 10.958 16.631 15.100 09.858 16.762 10.871 02.674; Set lt(i,j) 'lower triangular'; lt(i,j)$(ord(i) > ord(j)) = yes; Free Variable z; Binary Variable x(i,j); Equation twomatch(i), obj; obj.. z =e= sum(lt(i,j), d(i,j)*x(i,j)); twomatch(k).. sum(lt(i,k), x(i,k)) + sum(lt(k,j),x(k,j)) =e= 2; Model match / obj, twomatch /; solve match minimizing z using mip; * display x.l; * dynamic number of cuts Set cycle / cycle1*cycle50 / t 'tours' / t1*t100 / cutindex(cycle,t) 'dynamic set for addressing cuts'; Equation cut(cycle,t) 'actual cuts'; Parameter cutcoeff(cycle,t,i,j) 'coefficients in cuts' cutlength(cycle,t) 'rhs for cuts'; cut(cutindex).. sum((i,j), cutcoeff(cutindex,i,j)*x(i,j)) =l= cutlength(cutindex) - 1; Model tsp / obj, twomatch, cut /; * used to find and display tours Set s(i,j) 'current solution' tour(t,i,j) 'subtours' tt(t) 'current subtour' first(i,j) 'first (i,j) in S' reach(i,j) "(i,j)'s connected to tour(tt)"; Scalar proceed done / 0 /; Parameter results; // for reporting results('relaxed','obj') = z.l; results('relaxed','total equs') = match.numEqu; Parameter solutions(*,i,j); solutions('relaxed',i,j) = x.l(i,j); loop(cycle, * initialization tour(t,i,j) = no; s(i,j) = no; first(i,j) = no; reach(i,j) = no; done = 0; tt(t) = no; tt(t)$(ord(t) = 1) = 1; // initialize tt(1) = yes s(i,j) = yes$(x.l(i,j) > 0.5); // initialize to current solution while(not done, * pick any (i,j) from remaining solutions first(i,j) = no; loop((i,j)$(card(first) = 0), first(i,j) = s(i,j);); * display first; * this is he beginning of a new subtour tour(tt,first) = yes; s(first) = no; proceed = 1; while(proceed, * find (i,j)'s connected to tour(tt) * note that the loop over tt is just syntax: tt contains one element reach(i,j) = no; loop((tt,k), reach(s(i,j))$tour(tt,k,j) = yes; reach(s(i,j))$tour(tt,i,k) = yes; reach(s(i,j))$tour(tt,k,i) = yes; reach(s(i,j))$tour(tt,j,k) = yes; ); * display tour, s, reach; * if reach = empty then we can stop the while loop if(card(reach) = 0, proceed = 0;); * add them to the current subtour * note that the loop over tt is just syntax: tt contains one element loop(tt, tour(tt,reach) = yes;); s(reach) = no; ); * display tour; * if no remaining solutions, we are done if(card(s) = 0, done = 1;); * new subtour tt(t) = tt(t-1); // t := t + 1 ); cutindex(cycle,t)$(sum(tour(t,i,j),1) > 0.5) = yes; * check option tour:0:1:1; * display tour; loop(cutindex(cycle,t), abort$(sum(tour(t,i,j),1) < 2.5) "subtour with 1 or 2 points"; ); if(sum(cutindex(cycle,t),1) > 1.5, cutcoeff(cycle,tour(t,i,j))$cutindex(cycle,t) = 1; cutlength(cutindex(cycle,t)) = sum(tour(t,i,j),1); option cutindex:0:1:1, cutcoeff:0:1:1; * display cutindex, cutcoeff, cutlength; solve tsp minimizing z using mip; * display x.l; results(cycle,'obj') = z.l; results(cycle,'cuts added') = sum(cutindex(cycle,t), 1); results(cycle,'total equs') = tsp.numEqu; * display results; solutions(cycle,i,j) = x.l(i,j); else display "Optimal solution found!"; done = 1; solutions('optimal',i,j) = x.l(i,j); ); ); option x:0:0:1; display x.l, results;