MODEL:
! DUPLEX, OBJ= 674;
! Find minimum set of links so that there are two paths,
of at most two links, between every node pair;
! Keywords: telecommunications, network design, routing,
hub network, redundant network;
SETS:
NODE:;
ENDSETS DATA:
NODE = A B C D E F G H I J;
ENDDATA
SETS:
LINK( NODE, NODE) | &1 #LT# &2: COST, X;
LXN( LINK, NODE) | (&1 #NE# &3) #AND# ( &2 #NE# &3): C;
ENDSETS DATA:
COST = 66 46 87 21 19 39 51 38 35
95 48 29 53 72 83 28 48
38 39 51 19 34 42 73
44 19 33 82 49 35
57 95 83 24 55
28 45 32 53
53 84 24
99 11
36;
ENDDATA
!-----------------------------------------;
! Minimize the cost of links chosen;
MIN = @SUM( LINK: COST * X);
! Each node pair (I,J) must have at least two paths;
@FOR( LINK( I, J):
X( I, J) + @SUM( LXN( I, J, K): C( I, J, K)) >= 2;
@BIN( X( I, J));
);
! If the 2-link path C(I,J,K), between I and J, via K
is used, both component links must be on;
@FOR( LXN( I, J, K)| K #GT# J:
C( I, J, K) <= X( I, K);
C( I, J, K) <= X( J, K);
);
@FOR( LXN( I, J, K)| K #LT# I:
C( I, J, K) <= X( K, I);
C( I, J, K) <= X( K, J);
);
@FOR( LXN( I, J, K)| K #GT# I #AND# K #LT# J:
C( I, J, K) <= X( I, K);
C( I, J, K) <= X( K, J);
);
END
|