GLPK/Scalable Vector Graphics

From Wikibooks, open books for an open world
Jump to: navigation, search

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.

Example[edit]

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 saleman 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 roundtrip
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).