/* * Author: Heinrich Schuchardt
* * This model solves a clustering problem: * * Out of 50 towns select 3 to be cluster centers and assign the other * towns to the clusters such that the sum of the population weighted * euclidian distances between towns and centers is minimized. * * The solution is saved as a scalable vector graphic file with a * pseudo-random file name. */ # Read random numbers set I; param r{I}; table ti IN "CSV" "rnd.csv": I <- [i], r; # Output file param fn, symbolic := "00000" & 100000 * r[1]; param f, symbolic := "ct" & substr(fn, length(fn) - 4) & ".svg"; # Centers param nc := 3; set C := {1 .. nc}; # Towns param nt := 50; set T := {1 .. nt}; param xt{t in T} := r[1 + t]; param yt{t in T} := r[1 + nt + t]; param pt{t in T} := ceil(1000 * r[1 + 2 * nt + t]); # Image size param scale := 1000; # Colors # saturation [0, 255] param sat := 192; param hue{c in C} := 6 * (c - 1) / nc; param red{c in C} := if hue[c] <= 1 or hue[c] >= 5 then 255 else (if hue[c] >=2 and hue[c] <= 4 then 255 - sat else (if hue[c] <=2 then 255 - sat + sat * (2-hue[c]) else 255 - sat + sat * (hue[c]-4) )); param green{c in C} := if hue[c] >= 1 and hue[c] <= 3 then 255 else (if hue[c] >= 4 then 255 - sat else (if hue[c] <=1 then 255 - sat + sat * hue[c] else 255 - sat + sat * (4-hue[c]) )); param blue{c in C} := if hue[c] >= 3 and hue[c] <= 5 then 255 else (if hue[c] <=2 then 255 - sat else (if hue[c] <=3 then 255 - sat + sat * (hue[c]-2) else 255 - sat + sat * (6-hue[c]) )); var x{T}; var y{T,T}, binary; minimize obj : sum{c in T, t in T} y[c,t] * pt[t] * sqrt((xt[c] - xt[t])^2 + (yt[c] - yt[t])^2); s.t. sumx : sum{c in T} x[c] = nc; s.t. cxy{c in T, t in T} : y[c,t] <= x[c]; s.t. sumy{t in T} : sum{c in T} y[c,t] = 1; solve; for {c in T : x[c] > .5} { printf "Center %5.4f %5.4f\n", xt[c], yt[c]; for {t in T : y[c,t] > .5} { printf " Town %5.4f %5.4f (%5.0f)\n", xt[t], yt[t], pt[t]; } } # Output the solution as scalable vector graphic # header printf "\n" > f; printf "> f; printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> f; printf "\n" >> f; printf {t in T} "%d -> %d\n", t, pt[t]; end;