Lindo Systems

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