MODEL: ! (MnspTreeF);
!Given a set of cities or nodes and the distance between each pair,
find the shortest total distance of links on the network to connect
all the nodes that must be visited. There may be additional nodes
that may be optionally visited.
There will be exactly one path between any two "must be visited" nodes.
This includes the classic minimal spanning tree (MST) problem;
! Keywords: Connected Network, Minimal spanning tree, Network design, Spanning tree,
Steiner tree, Tree;
SETS:
CITY : FLOWIN, FLOWOUT, VISIT;
LINK( CITY, CITY):
DIST, ! The distance matrix;
FLO, ! Flow from I to J;
Z; ! Z( I, J) = 1 if we use link I, J;
ENDSETS
! Case 1;
!Case01 CITY=
NYK ATL CHI CIN HOU LAX MON;
!Case01 DEPOTI = 1; !Case01
VISIT= 1 1 1 1 1 1 1; ! Set to 1 if must be visited! Distance matrix, it need not be symmetric;
!Case01
DIST=
!Case01 0 864 845 664 1706 2844 396 !from NYK;
!Case01 864 0 702 454 842 2396 1196 !Case01 845 702 0 324 1093 2136 764 !from Chicago;
!Case01 664 454 324 0 1137 2180 798 !Case01 1706 842 1093 1137 0 1616 1857 !from Houston;
!Case01 2844 2396 2136 2180 1616 0 2900 !Case01 396 1196 764 798 1857 2900 0; !from Montreal
! Case 2 Obj = 33;
!Case02; CITY =
A B C D E F G H I J K;
!Case02;
VISIT= 1 1 1 1 1 0 0 0 0 0 0; ! Set to 1 if must be visited;
!Case02; DEPOTI = 1!Case02;
DIST = 0 14 999 999 999 4 999 999 999 999 999
14 0 999 999 999 999 999 3 999 999 999
999 999 0 9 999 999 999 999 2 999 999
999 999 9 0 999 999 999 999 999 3 6
999 999 999 999 0 999 999 5 999 999 3
4 999 999 999 999 0 999 999 3 999 999
999 999 999 999 999 999 0 2 999 3 999
999 3 999 999 5 999 2 0 999 999 999
999 999 2 999 999 3 999 999 0 8 999
999 999 999 3 999 999 3 999 8 0 999
999 999 999 6 3 999 999 999 999 999 0;
! Case of MLB old NL, Obj= 4969;
!CaseMLBNL CITY=
NYK ATL CHI CIN HOU LAX MON PHL PIT STL SND SNF;
!CaseMLBNL DEPOTI = 1; ! Set VISIT to 1 if must be visited;
!CaseMLBNL
VISIT= 1 1 1 1 1 1 1 1 1 1 1 1;
! Distance matrix, it need not be symmetric;
!CaseMLBNL
DIST=
!CaseMLBNL 0 864 845 664 1706 2844 396 92 386 1002 2892 3032 !from NYK;
!CaseMLBNL 864 0 702 454 842 2396 1196 772 714 554 2363 2679 !CaseMLBNL 845 702 0 324 1093 2136 764 764 459 294 2184 2187 !from Chicago;
!CaseMLBNL 664 454 324 0 1137 2180 798 572 284 338 2228 2463 !CaseMLBNL 1706 842 1093 1137 0 1616 1857 1614 1421 799 1521 2021 !from Houston;
!CaseMLBNL 2844 2396 2136 2180 1616 0 2900 2752 2464 1842 95 405 !CaseMLBNL 396 1196 764 798 1857 2900 0 424 514 1058 2948 2951 !from Montreal;
!CaseMLBNL 92 772 764 572 1614 2752 424 0 305 910 2800 2951 !CaseMLBNL 386 714 459 284 1421 2464 514 305 0 622 2512 2646 !from Pittsburgh;
!CaseMLBNL 1002 554 294 338 799 1842 1058 910 622 0 1890 2125 !CaseMLBNL 2892 2363 2184 2228 1521 95 2948 2800 2512 1890 0 500 !from SanDiego;
!CaseMLBNL 3032 2679 2187 2463 2021 405 2951 2951 2646 2125 500 0;
! Case Alden ;
!CaseAlden CITY=
Chi Den Frsn Hous KC LA Oakl Anah Peor Phnx Prtl Rvrs Sacr SLC Sntn SBrn SDgo SFrn SJos Seat Spkn Tucs Wich LngB;
!CaseAlden DEPOTI = 1; ! This case has Obj= 5357;
! Set VISIT to 1 if must be visited;
!CaseAlden VISIT = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ;
! This case has Obj= 4895;
!CaseAlden !CaseAlden DIST =
!CaseAlden 0 996 2162 1067 499 2054 2134 2050 151 1713 2083 2005 2049 1390 1187 1996 2064 2142 2160 2013 1735 1688 696 2060! Chicago;
!CaseAlden 996 0 1167 1019 596 1059 1227 1055 904 792 1238 1010 1142 504 939 1001 1108 1235 1242 1307 1089 835 509 1075!CaseAlden 2162 1167 0 1747 1723 214 168 250 2070 598 745 268 162 814 1572 265 339 176 151 917 991 714 1534 270! Fresno;
!CaseAlden 1067 1019 1747 0 710 1538 1904 1528 948 1149 2205 1484 1909 1438 197 1533 1482 1912 1873 2274 2102 1067 608 1548!CaseAlden 499 596 1723 710 0 1589 1827 1579 354 1214 1809 1535 1742 1086 759 1482 1565 1835 1842 1839 1561 1189 197 1599! K. City;
!CaseAlden 2054 1059 214 1538 1589 0 371 36 1943 389 959 54 376 715 1363 59 125 379 340 1131 1205 505 1400 22!CaseAlden 2134 1227 168 1904 1827 371 0 407 2043 755 628 425 85 744 1729 422 496 8 42 800 874 871 1687 396! Oakland;
!CaseAlden 2050 1055 250 1528 1579 36 407 0 1933 379 995 45 412 711 1353 55 99 415 376 1167 1241 491 1390 30!CaseAlden 151 904 2070 948 354 1943 2043 1933 0 1568 2022 1889 1958 1299 1066 1887 1919 2051 2069 1991 1713 1543 551 1953! Peoria;
!CaseAlden 1713 792 598 1149 1214 389 755 379 1568 0 1266 335 760 648 974 333 355 763 724 1437 1335 118 1025 399!CaseAlden 2083 1238 745 2205 1809 959 628 995 2022 1266 0 1001 583 767 2086 992 1084 636 665 172 348 1382 1739 1015! Portland;
!CaseAlden 2005 1010 268 1484 1535 54 425 45 1889 335 1001 0 430 666 1309 10 98 433 394 1173 1202 451 1346 65!CaseAlden 2049 1142 162 1909 1742 376 85 412 1958 760 583 430 0 659 1734 427 501 93 118 755 829 876 1602 401! Sacrmnto;
!CaseAlden 1390 504 814 1438 1086 715 744 711 1299 648 767 666 659 0 1319 657 764 752 770 836 712 764 1003 731!CaseAlden 1187 939 1572 197 759 1363 1729 1353 1066 974 2086 1309 1734 1319 0 1307 1307 1737 1698 2155 2022 892 625 1373! SAnt;
!CaseAlden 1996 1001 265 1482 1533 59 422 55 1887 333 992 10 427 657 1307 0 1108 430 391 1164 1193 449 1344 75!CaseAlden 2064 1108 339 1482 1565 125 496 99 1919 355 1084 98 501 764 1307 108 0 504 465 1256 1300 415 1376 119! SDgo;
!CaseAlden 2142 1235 176 1912 1835 379 8 415 2051 763 636 433 93 752 1737 430 504 0 44 808 882 879 1695 404!CaseAlden 2160 1242 151 1873 1842 340 42 376 2069 724 665 394 118 770 1698 391 465 44 0 837 911 840 1669 365! SJos;
!CaseAlden 2013 1307 917 2274 1839 1131 800 1167 1991 1437 172 1173 755 836 2155 1164 1256 808 837 0 278 1553 1808 1156!CaseAlden 1735 1089 991 2102 1561 1205 874 1241 1713 1335 348 1202 829 712 2022 1193 1300 882 911 278 0 1451 1544 1230! Spkn;
!CaseAlden 1688 835 714 1067 1189 505 871 491 1543 118 1382 451 876 764 892 449 415 879 840 1553 1451 0 1000 515!CaseAlden 696 509 1534 608 197 1400 1687 1390 551 1025 1739 1346 1602 1003 625 1344 1376 1695 1669 1808 1544 1000 0 1410! Wich;
!CaseAlden 2060 1075 270 1548 1599 22 396 30 1953 399 1015 65 401 731 1373 75 119 404 365 1156 1230 515 1410 0;ENDDATA
!----------------------------------------------;
! Variables:
Z( i, j) = 1 if the link from i to j is used.
FLO( i, j) = flow from i to j = number of cities that
are linked to depot city via the link from i to j;
!The objective is to minimize total distance of links chosen;
MIN = @SUM( LINK( I, J): DIST( I, J) * Z( I, J));
! Each non-depot "must visit" city receives one unit of supply from depot;
SUPPLY = @SUM( CITY( j) | j #NE# DEPOTI #AND# VISIT( J) #GT# 0: 1 );
FLOWOUT( DEPOTI) = SUPPLY; ! Must ship right amount out of depot;
SUPPLY = @SUM( CITY( J) | J #NE# DEPOTI: FLO( DEPOTI, j));
FLOWIN( DEPOTI) = 0; ! No flow returns to depot;
FLOWIN( DEPOTI) = @SUM( CITY( I) | I #NE# DEPOTI: FLO( I, DEPOTI));
!For city K ;
@FOR( CITY( K)| K #NE# DEPOTI:
! Flow balance at K;
FLOWIN( K) = VISIT( K) + FLOWOUT( K);
FLOWIN( K) = @SUM( CITY( I) | I #NE# K: FLO( I, K));
FLOWOUT( K) = @SUM( CITY( J) | J #NE# DEPOTI #AND# J #NE# K: FLO( K, J));
! If city K must be visited it must be entered;
@SUM( CITY( I) | I #NE# K: Z( I, K)) >= VISIT( K);
);
@FOR( LINK( I, J) | I #NE# J:
!If there is a flow from I to J, then Z( I, J) = 1;
FLO( I, J) <= VISIT( J) * Z( I, J) + FLOWOUT( j);
FLO( I, J) <= SUPPLY * Z( I, J) ;
);
!Make the Z's 0/1;
@FOR( LINK: @BIN( Z); );
! Some optional cuts that may reduce solve time;
! No Subtour/loop of size 2 cuts;
@FOR( CITY( i) :
Z( i, i) = 0; ! City cannot visit itself;
@FOR( CITY( j) | j #GT# i:
Z( i, j) + Z( j, i) <= 1
)
);
! No subtours/loops of size 3 cuts;
@FOR( CITY( i) :
@FOR( CITY( j) | j #GT# i :
@FOR( CITY( k) | k #GT# j :
Z( i, j) + Z( j, i) + Z( i, k) + Z( k, i) + Z( j, k) + Z( k, j) <= 2
)
)
);
END
|
