Re: [Help-glpk] [Fwd: A query and a request for help

[Heinrich Schuchardt]

Hello Sanaullah,

for a limited number of towns (100) and possible centers (50) the
assignment problems is quickly solved by GLPK.

The model below creates the appended SVG graphic. You could view it with
Firefox.

If you have given sets of towns and centers you could use the tables
command to load the data from a CSV file or a data base.

> as i have left with very short time for my thesis finalization,
Please, be aware that this mail will be published in the GLPK help list
archive which is indexed by search machines (e.g. Baidu).


# Output file
param f, symbolic := "ct.svg";

# Towns
param nt := 100;
set T := {1 .. nt};
param xt{T} := Uniform01();
param yt{T} := Uniform01();
param pt{T} := ceil(1000 * Uniform01());

# Centers
param nc := 50;
set C := {1 .. nc};
param xc{C} := Uniform01();
param yc{C} := Uniform01();

var x{C}, binary;
var y{C,T}, binary;

minimize obj : sum{c in C, t in T} y[c,t] * pt[t]
               * sqrt((xc[c] - xt[t])^2 + (yc[c] - yt[t])^2);

s.t. sumx : sum{c in C} x[c] = 7;
s.t. cxy{c in C, t in T} : y[c,t] <= x[c];
s.t. sumy{t in T} : sum{c in C} y[c,t] = 1;

solve;

for {c in C : x[c] > .5} {
  printf "Center %5.4f %5.4f\n", xc[c], yc[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 "<?xml version=""1.0"" standalone=""no""?>\n" > f;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> f;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"";>\n" >> f;
printf "<svg width=""100\%"" height=""100\%"" version=""1.0"" \n" >> f;
printf "xmlns=""http://www.w3.org/2000/svg"";>\n" >> f;

# background
printf "<rect x=""0"" y=""0"" width=""600"" height=""600""" &
       " stroke=""none"" fill=""white""/>\n">> f;

# border
printf "<rect x=""50"" y=""50"" width=""500"" height=""500""" &
       " stroke=""black"" stroke-width="".5"" fill=""white""/>\n">> f;

# circles for not chosen centers
for {c in C : x[c] <= .5}
  printf "<circle cx=""%f"" cy=""%f"" r=""2"" stroke=""grey"" " &
         "stroke-width="".5"" fill=""white""/>\n",
         50 + xc[c] * 500, 50 + yc[c] * 500 >> f;

# circles for towns
for {t in T}
  printf "<circle cx=""%f"" cy=""%f"" r=""%f"" stroke=""black"" " &
         "stroke-width=""1"" fill=""green""/>\n",
         50 + xt[t] * 500, 50 + yt[t] * 500, .5 * sqrt(pt[t]) >> f;

# lines from towns to assigned centers
for {t in T, c in C : y[c,t] > .5}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:.5""/>\n",
         50 + xc[c] * 500, 50 + yc[c] * 500,
         50 + xt[t] * 500, 50 + yt[t] * 500 >> f;

# circles for chosen centers
for {c in C : x[c] > .5}
  printf "<circle cx=""%f"" cy=""%f"" r=""2"" stroke=""black"" " &
         "stroke-width=""1"" fill=""red""/>\n",
         50 + xc[c] * 500, 50 + yc[c] * 500 >> f;

printf "</svg>\n" >> f;

end;



Best regards

Heinrich Schuchardt




On 10.04.2015 09:12, sanaullah swati wrote:
> Dear Heinrich Schuchardt
> 
> sir i have done the clustering in ArcGIS .no issue with the clustering.
> the actual problem is that  the clustering is subject to the OBJECTIVE
> FUNCTION which is to be kept MINIMIZE . for minimization of the
> objective fucntion using MLIP i requested for help.
> as i have left with very short time for my thesis finalization, please.
> 
> kindly see the objective function here
> 
> Inline image 1
> The above objective function of the optimal redistricting model is to
> minimize the total population weighted distance to each district center
> summed across all the districts. 
> 
> further, 
> 
> *           Where,  bic* behaves as a binary value operator;
> 
> *            i.e, *
> 
> *    If*
> 
>        i) the unit   is assigned to center* c* then bic=1
> 
>        ii) Otherwise ………………………....bic=0
> 
> and c refers to the new district center. total number of districts i
> wana generate are 7 hence there will be 7 centers around which the basic
> units (cencus tracts) will cluster to form new district under some pop
> constraint.
> 
> 
> THE MAIN PROBLEM IS ONLY THE MINIMIZATION OF OBJECTIVE FUNCTION  HOW IT
> WILL BE DONE I AM TOTALLY  AT FIX IN THIS REGARD.
> 
> IF YOU WOULD PLEASE SOLVE THIS?
> 
> 
> On Fri, Apr 10, 2015 at 6:02 AM, Heinrich Schuchardt <address@hidden
> <mailto:address@hidden>> wrote:
> 
>     @Michael
>     Andrew had to forward Sanaullah's mail manually because he was not
>     subscribed to the GLPK list. Hence your mail most probably will not
>     have reached him.
> 
>     @Sanaullah
>     Please, see https://lists.gnu.org/mailman/listinfo/help-glpk
> 
>     Best regards
> 
>     Heinrich Schuchardt
> 
> 
> 
>     Michael Hennebry <address@hidden
>     <mailto:address@hidden>>schrieb:
> 
>         From: sanaullah swati <address@hidden
>         <mailto:address@hidden>>
> 
>         > sir i have this objective function for creating districts by
>         clustering
>         > of census data (gis data)
>         > Inline image 1
> 
>         Not seeing it.
> 
>         > The above objective function of the optimal redistricting
>         model is to
>         > minimize the totalpopulation weighted distance to each
>         district center
>         > summed across all the districts.
> 
>         What you seem to want would be difficult to impossible with a
>         finite MILP.
>         Replacing distance with L1 distance or some other suitable
>         approximation to distance would render it just diffucult.
> 
>         What you seem to be trying to do is called clustering.
>         
> http://en.wikipedia.org/wiki/Cluster_analysis#Centroid-based_clustering
>         One large MILP is not usually how they are solved.
> 
>         --
>         Michael address@hidden
>         <mailto:address@hidden>
>         "SCSI is NOT magic. There are *fundamental technical
>         reasons* why it is necessary to sacrifice a young
>         goat to your SCSI chain now and then." -- John Woods
> 
>         _______________________________________________
>         Help-glpk mailing list
>         address@hidden <mailto:address@hidden>
>         https://lists.gnu.org/mailman/listinfo/help-glpk
> 
> 
> 
> 
> -- 
> SANAULLAH,
> Assistant Director
> Survey of Pakistan
> Ministry of Defence, Rawalpindi,, 
> Cell#03005316640.
> 
>

ct.svg
Description: image/svg