Formulazione con piani di taglio; vengono fornite istanze con caratteristiche diverse;
solo tagli di tipo "subtour" possono venire aggiunti,
altrimenti bisgogna fare un branch and bound manuale.
SETS:
nodi/n1,n2,n3,n4,n5,n6,n7,n8,n9,n10/;
archi(nodi,nodi)|&1#LT#&2:x,c;
! s1(nodi)/n1,n2,n3,n7,n6/;
!s2(nodi)/n1,n2, n7,n6/;
ENDSETS
DATA:
! one subtour inequality;
!c = 4 7 3 20 9 10 8 2 11
5 6 15 5 4 11 7 14
7 10 6 6 9 3 10
7 9 13 10 9 4
10 13 9 11 7
3 14 15 20
7 6 6
5 13
2;
! clique tree;
!c = 4 7 3 20 9 10 8 2 11
5 6 15 5 4 11 7 14
7 10 6 6 9 3 10
6 9 13 10 9 4
10 13 9 11 7
3 14 15 20
7 6 6
5 13
2;
! clique tree;
!c = 4 7 5 20 9 10 15 10 11
5 6 15 5 4 11 7 14
7 10 6 6 9 3 10
6 9 13 10 9 4
10 13 9 11 7
6 14 15 20
7 6 6
5 13
2;
!two subtour and one clique tree;
c = 4 7 10 20 9 10 15 10 11
5 7 15 5 4 11 7 14
7 10 6 6 9 12 10
6 9 13 10 9 4
12 13 9 11 7
6 14 15 20
10 7 8
5 13
2;
ENDDATA
min= @SUM(archi:c*x);
@FOR(nodi(i):@SUM(archi(i,j):x(i,j))+@SUM(archi(j,i):x(j,i)) = 2 );
!@SUM(s1(i): @SUM(s1(j) |i#LT#j : x(i,j) ) ) < @SIZE(s1) -1 ;
!@SUM(s2(i): @SUM(s2(j) |i#LT#j : x(i,j) ) ) < @SIZE(s2) -1 ;
@FOR(archi:@BND(0,x,1));
!@GIN(x(2,7));
Formulazione con piani di taglio per un TSP fra città italiane
solo tagli di tipo "subtour" possono venire aggiunti,
vengono suggeriti due possibili tagli (ne servono altri).
SETS:
citta/AN,AO,AQ,BA,BO,CB,FI,GE,MI,NA,PA,PG,PZ,RC,RM,TO,TN,TS,UD,VE/;
!s1(citta)/TS,UD,VE/;
!s2(citta)/AO,MI,GE,TO/;
archi(citta,citta)|&1#LT#&2:x,c;
ENDSETS
DATA:
c =
610 195 465 215 325 320 510 425 390 1110 165 460 875 285 545 440 445 415 305
795 1065 395 925 470 245 180 955 1675 625 1100 1440 745 110 400 585 550 445
400 400 190 375 600 610 245 965 175 390 730 110 730 625 630 600 490
670 220 720 945 880 260 690 610 145 455 450 1000 895 900 870 760
530 105 295 210 590 1310 260 735 1075 380 330 225 295 260 155
490 720 740 135 825 385 200 590 225 860 755 760 725 620
225 300 490 1205 155 630 970 280 395 315 395 365 255
140 715 1430 380 860 1195 505 170 370 540 505 400
785 1505 455 930 1270 575 140 245 410 380 270
735 380 155 500 220 885 800 880 850 740
1100 680 235 935 1600 1520 1600 1570 1460
525 865 170 550 470 480 450 340
445 360 1030 945 895 865 755
700 1365 1285 1365 1335 1225
675 590 670 640 530
355 540 510 400
285 225 195
75 155
125;
ENDDATA
min= @SUM(archi:c*x);
@FOR(citta(i):@SUM(citta(j)|i#LT#j:x(i,j))+@SUM(citta(j)|i#GT#j:x(j,i)) = 2 );
@FOR(archi:@BND(0,x,1));
!@SUM(archi(i,j):@IN(s1,i)*@IN(s1,j)*x(I,j)) < @SIZE(s1) -1;
!@SUM(archi(i,j):@IN(s2,i)*@IN(s2,j)*x(I,j)) < @SIZE(s2) -1;
Formulazione con tre indici
SETS:
nodes/1..10/;
times/1..10/;
arcs0(nodes,nodes)|&1#LT#&2:cost;
arcs(nodes,nodes)|&1#NE#&2:c;
trips(arcs,times):x;
ENDSETS
DATA:
cost= 4 2 3 20 4 10 8 2 11
5 6 15 8 7 11 7 14
7 10 6 6 4 3 10
6 9 13 2 9 2
10 5 9 5 7
2 14 15 20
7 6 6
5 13
2;
nn=10;
ENDDATA
@FOR(arcs0(i,j): c(i,j)=cost(i,j);c(j,i)=cost(i,j));
min= @SUM(arcs(i,j):c(i,j)*@SUM(times(k):x(i,j,k)));
@FOR(nodes(i):@SUM(nodes(j)|i#NE#j:@SUM(times(k):x(i,j,k)))=1);
@FOR(times(k):@SUM(arcs(i,j):x(i,j,k)) < 1);
@SUM(nodes(j)|j#GT#1:x(1,j,1))=1;
@SUM(nodes(j)|j#GT#1:x(j,1,nn))=1;
@FOR(nodes(i)|(i#GT#1):
@FOR(times(k)|k#LT#nn:@SUM(nodes(j)|i#NE#j:x(j,i,k))=@SUM(nodes(j)|i#NE#j:x(i,j,k+1))));
@FOR(trips:@GIN(x));
Formulazione con tre indici per le città italiane
SETS:
nodes/AN,AO,AQ,BA,BO,CB,FI,GE,MI,NA,PA,PG,PZ,RC,RM,TO,TN,TS,UD,VE/;
times/1..20/;
arccost(nodes,nodes)|&1#LT#&2:cost;
arcs(nodes,nodes)|&1#NE#&2:c;
trips(arcs,times):x;
ENDSETS
DATA:
cost=
610 195 465 215 325 320 510 425 390 1110 165 460 875 285 545 440 445 415 305
795 1065 395 925 470 245 180 955 1675 625 1100 1440 745 110 400 585 550 445
400 400 190 375 600 610 245 965 175 390 730 110 730 625 630 600 490
670 220 720 945 880 260 690 610 145 455 450 1000 895 900 870 760
530 105 295 210 590 1310 260 735 1075 380 330 225 295 260 155
490 720 740 135 825 385 200 590 225 860 755 760 725 620
225 300 490 1205 155 630 970 280 395 315 395 365 255
140 715 1430 380 860 1195 505 170 370 540 505 400
785 1505 455 930 1270 575 140 245 410 380 270
735 380 155 500 220 885 800 880 850 740
1100 680 235 935 1600 1520 1600 1570 1460
525 865 170 550 470 480 450 340
445 360 1030 945 895 865 755
700 1365 1285 1365 1335 1225
675 590 670 640 530
355 540 510 400
285 225 195
75 155
125;
nn=20;
ENDDATA
@FOR(arccost(i,j): c(i,j) =cost(i,j) ; c(j,i) = cost(i,j));
min= @SUM(arcs(i,j):c(i,j)*@SUM(times(k):x(i,j,k)));
@FOR(nodes(i):@SUM(nodes(j)|i#NE#j:@SUM(times(k):x(i,j,k)))=1);
@FOR(times(k):@SUM(arcs(i,j):x(i,j,k)) < 1);
@SUM(nodes(j)|j#GT#1:x(1,j,1))=1;
@SUM(nodes(j)|j#GT#1:x(j,1,nn))=1;
@FOR(nodes(i)|(i#GT#1):
@FOR(times(k)|k#LT#nn:@SUM(nodes(j)|i#NE#j:x(j,i,k))=@SUM(nodes(j)|i#NE#j:x(i,j,k+1))));
@FOR(trips:@GIN(x));