! Clustering.                          (ClusterDisk.lng)
Partition items into clusters so that items in the
same cluster are close together according to some distance metric;
! Keywords: Cluster analysis, File allocation;
SETS:
  ITEM: ITMSIZ;
  CLUSTER: CSIZE;
  IXI( ITEM, ITEM) | &1 #GT# &2: D, Y;
  IXC( ITEM, CLUSTER) : Z;
ENDSETS
! Clustering problem.
Assign files of various sizes to three different
disks so that files that tend to be used by the
same program are assigned to different disks
so the interference is minimized;
DATA:
 CLUSTER = 1..3;
 CSIZE = 885; ! Maximum cluster size;
 ITEM = A..J;
 ITMSIZ = 110 238 425 338 55 391 267 105 256 64;

! Distance matrix;
D = 								
43								
120	10							
57	111	188						
96	78	46	88					
83	58	421	60	63				
77	198	207	109	73	74			
31	50	43	47	51	21	88		
38	69	55	21	36	391	47	96	
212	91	84	53	71	40	37	35	221;
ENDDATA

! Variables:
   X(i,k) = 1 if item i is assigned to cluster k,
   Y(i,j) = 1 if items i and j are in the same cluster
;

! Minimize the distance among items in same cluster;
 MIN = @SUM( IXI(i,j): D(i,j)*Y(i,j));

! Each item i must be in some cluster k;
  @FOR( ITEM(i):
    @SUM( CLUSTER(k): Z(i,k)) = 1;
      );

! Cannot exceed capacity of each cluster k;
  @FOR( CLUSTER(k):
    @SUM( ITEM(i): ITMSIZ(i)*Z(i,k)) <= CSIZE(k);
      );

! Measure interaction. Force Y(i,j) = 1 if i and j in same cluster;
  @FOR( IXI(i,j):
    @FOR( CLUSTER(k):
      Y(i,j) >= Z(i,k) + Z(j,k) - 1;
        );
      );

 ! Z(i,k) can be only 0 or 1;
 @FOR( IXC(i,k):
   @BIN( Z(i,k));
     );

! Optionally, Kill some symmetry;
! We may arbitrarily order the clusters so
  If item i is in cluster k, then some lower numbered item
   must be in cluster k-1;
 @FOR( IXC(i,k) | k #GT# 1:
   Z(i,k) <= @SUM( ITEM( j) | j #LT# i: Z(j,k-1))
      );