! Clustering example in LINGO(clusters.lng);
! Keywords: cluster analysis, location, plant location;
! Partition a set of points into a specified number
of clusters, so that the points in each cluster
are close together according to a specified measure;
SETS:
point: cx, cy;
pxp(point, point)| &1 #le# &2: d, x;
ENDSETS DATA:
! Specify the points and their attributes;
point cx cy =
1 34 32
2 22 45
3 54 2
4 62 63
5 32 27
6 43 54;
! Number of clusters allowed;
clusters = 2;
ENDDATA
! Compute a distance measure(insert your own formula)
between all pairs of points;
@FOR(pxp(i,j):
d(i,j) = ((cx(i) - cx(j))^2 + (cy(i)-cy(j))^2)^.5;
);
! Definitions:
x(i,i) = 1 if i is a cluster center,
x(i,j) = 1, for i <> j, if either i or j
is a center and the other is
assigned to it;
! Minimize sum of distances to centers;
min = @SUM(pxp(i,j): d(i,j)*x(i,j));
! Each point must be assigned to a cluster
or be a cluster center;
@FOR( point(k):
@SUM( pxp(i,j)| i #eq# k #or# j #eq# k: x(i,j)) >= 1;
! No fractional centers are allowed, make them binary(0/1);
@BIN(x(k,k));
);
! Cannot have too many clusters;
@SUM( point(i): x(i,i)) <= clusters;
! If i and j are assigned to each other, one must be a center;
@FOR( pxp(i,j)| i #lt# j:
x(i,j) <= x(i,i) + x(j,j);
);
|