Jump to content

GLPK/Scalable Vector Graphics

Add links
From Wikibooks, open books for an open world

Scalable vector graphics (SVG) is an XML file format to describe two dimensional graphics. SVG 1.1 is the most recent version of the specification.

With a little effort, the MathProg printf statement can be used to generate SVG code.

Examples

[edit | edit source]

Traveling salesman problem

[edit | edit source]
SVG output generated with GLPK

The task in the traveling salesman problem is to find the shortest cyclic path through a given set of cities, visiting each city exactly once, and then returning to the start.

The model below shows how to output the solution as a scalable vector graphic. 

###################################################################
# This file demonstrates output to a scalable vector graphic (SVG).
#
# Solve with option --nomip to see the difference
#
# Traveling salesman problem
#
###################################################################

# output file
param filename, symbolic := "out.svg";
# number of cities
param n := 35;

# set of cities
set N := {1..n};
# set of bidirectional arcs
set E := setof{(i,j) in N cross N : i > j} (i,j);
# set of unidirectional arcs
set F := setof{(i,j) in N cross N : i != j} (i,j);

# random locations for the cities
param cx{i in N} := Uniform01();
param cy{i in N} := Uniform01();
#sum of x- and y- distance
#param d{(i,j) in E} := abs(cx[i]-cx[j])+abs(cy[i]-cy[j]);
#maximum of x- and y- distance
#param d{(i,j) in E} := max(abs(cx[i]-cx[j]),abs(cy[i]-cy[j]));
#euclidean distance
param d{(i,j) in E} := sqrt((cx[i]-cx[j])^2+(cy[i]-cy[j])^2);

# connection
var x{(i,j) in E}, >=0, <= 1, binary;
# flow
var f{(i,j) in F}, >= 0;

# Objective
minimize dist :
  sum{(i,j) in E} x[i,j] * d[i,j];

# Every city must have two connections for a round trip
s.t. two{ i in N } :
  sum{j in N : i > j} x[i,j] + sum{j in N : i < j} x[j,i] = 2;

# The following constraints force the graph to be connected
# Flow is controlled by binaries
s.t. flow1 {(i,j) in F} :
  f[i,j] <= (if (i==1) then n else n-1) 
          * (if (i < j) then x[j,i] else x[i,j]);

# One unit is consumed in each node
s.t. flow2 {i in N} :
  sum{(i,j) in F} (f[i,j]-f[j,i]) <= if (i==1) then n-1 else -1;

# There must be flow into every node
s.t. flow3 { i in N } :
  sum{(i,j) in F} f[j,i] >= 1;

solve;

# Output the solution as scalable vector graphic
# write header
printf "<?xml version=""1.0"" standalone=""no""?>\n" > filename;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> filename;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> filename;
printf "<svg width=""100\%"" height=""100\%"" version=""1.0"" \n" >> filename;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> filename;
# draw circles for cities
for {i in N}
  printf "<circle cx=""%f"" cy=""%f"" r=""5"" stroke=""black"" stroke-width=" &
         """2"" fill=""red""/>\n", cx[i] * 500, cy[i] * 500 >> filename;
# draw solid black lines for integer connections
for {(i,j) in E : x[i,j] == 1}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:2""/>\n", 
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
# draw dashed red lines for fractional connections
for {(i,j) in E : x[i,j] > 0 && x[i,j] < 1}
  {
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""",
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
  printf " style=""stroke:red;stroke-dasharray: 3 3;stroke-width:2""/>\n"
         >> filename;
  }
printf "</svg>\n" >> filename;
end;

Run the model (40 seconds on a Intel Core i5 processor): 

$ glpsol --math traveling.mod

This is what the created output file out.svg looks like (some lines removed): 

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="100%" height="100%" version="1.0" 
xmlns="http://www.w3.org/2000/svg">
<circle cx="14.843435" cy="64.155902" r="5" stroke="black" stroke-width="2" fill="red"/>
<circle cx="276.895963" cy="4.798338" r="5" stroke="black" stroke-width="2" fill="red"/>
...
<line x1="103.248022" y1="381.131207" x2="127.779724" y2="409.131953" style="stroke:black;stroke-width:2"/>
<line x1="103.248022" y1="381.131207" x2="96.365578" y2="282.627837" style="stroke:black;stroke-width:2"/>
</svg>

The resulting file can be viewed in an up-to-date web browser (like Firefox 3.6 or Internet Explorer 9) or viewed and modified using a (multi-platform) SVG editor (like Inkscape).

Clustering

[edit | edit source]
Solution of a clustering problem created with GLPK

The example below concerns a clustering problem. Out of 500 towns select 20 to be cluster centers and assign the other towns to the cluster such that the sum of the population weighted euclidian distances between towns and centers is minimized. 

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

# Centers
param nc := 20;
set C := {1 .. nc};

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

# 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,T}, binary;

minimize obj : sum{c in T, t in T : c != t} x[c,t] * pt[t]
               * sqrt((xt[c] - xt[t])^2 + (yt[c] - yt[t])^2);

s.t. cc : sum{c in T} x[c,c] = nc;
s.t. ct{c in T, t in T : c != t} : x[c,t] <= x[c,c];
s.t. tc{t in T} : sum{c in T} x[c,t] = 1;

solve;

for {c in T : x[c,c] > .5} {
  printf "Center %5.4f %5.4f\n", xt[c], yt[c];
  for {t in T : x[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=""%d"" height=""%d"" version=""1.0"" \n",
  1.2 * scale, 1.2 * scale >> f;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> f;

# background
printf "<rect x=""0"" y=""0"" width=""%d"" height=""%d""" &
       " stroke=""none"" fill=""white""/>\n",
       1.2 * scale, 1.2 * scale>> f;

# border
printf "<rect x=""%d"" y=""%d"" width=""%d"" height=""%d""" &
       " stroke=""black"" stroke-width="".5"" fill=""white""/>\n",
       .1 * scale, .1 * scale, scale, scale >> f;

# circles for towns
for {t in T}
  printf {s in T, c in C : x[s,t] > .5
         && c = floor( .5 + sum{u in T : u <= s} x[u,u])}
         "<circle cx=""%f"" cy=""%f"" r=""%f"" stroke=""black"" " &
         "stroke-width=""1"" fill=""rgb(%d,%d,%d)""/>\n",
         (.1 + xt[t]) * scale, (.1 + yt[t]) * scale, .007 * sqrt(pt[t]/nt) *
	 scale, red[c], green[c] , blue[c] >> f;

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

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

end;
Retrieved from "https://en.wikibooks.org/w/index.php?title=GLPK/Scalable_Vector_Graphics&oldid=3575895"