Scaleable Vector Graphic

Introduction

The task in a travelling salesman problem is to find the shortes cyclic path through give cities visiting each city exactly once.

The model shows how to output the solution using GMPL as scalable vector graphic.

Model

###################################################################
# 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 bidiretional arks
set E := setof{(i,j) in N cross N : i > j} (i,j);
# set of unidirectional arks
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;