Traveling Salesman Problems using Solver Foundation: C# code

I was asked to post the complete TSP sample code. In my previous posts the code was spread out and had a couple of typos.  Here goes:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.SolverFoundation.Services;

namespace Microsoft.SolverFoundation.Samples.TravelingSalesman {

  class Program {
    // TSP coordinate.
    public class Coordinate {
      public int Name { get; set; }

      // X-coordinate (from TSPLIB)
      public double X { get; set; }

      // Y-coordinate (from TSPLIB)
      public double Y { get; set; }

      public Coordinate(int name, double x, double y) {
        Name = name;
        X = x;
        Y = y;
      }

      // Latitude in radians.
      public double Latitude {
        get { return Math.PI * (Math.Truncate(X) + 5 * (X - Math.Truncate(X)) / 3) / 180; }
      }

      // Longitude in radians.
      public double Longitude {
        get { return Math.PI * (Math.Truncate(Y) + 5 * (Y - Math.Truncate(Y)) / 3) / 180; }
      }

      // Geographic distance between two points (as an integer).
      public int Distance(Coordinate p) {
        double q1 = Math.Cos(Longitude - p.Longitude);
        double q2 = Math.Cos(Latitude - p.Latitude);
        double q3 = Math.Cos(Latitude + p.Latitude);
        // There may rounding difficulties her if the points are close together...just sayin'.
        return (int)(6378.388 * Math.Acos(0.5 * ((1 + q1) * q2 - (1 - q1) * q3)) + 1);
      }
    }

    // TSP city-city arc.
    // 
    public class Arc {
      public int City1 { get; set; }
      public int City2 { get; set; }
      public double Distance { get; set; }
    }

    // Burma14 from TSPLIB. Optimal tour = 3323.
    private static Coordinate[] data = new Coordinate[] {
      new Coordinate(0, 16.47, 96.10),
      new Coordinate(1, 16.47, 94.44),
      new Coordinate(2, 20.09, 92.54),
      new Coordinate(3, 22.39, 93.37),
      new Coordinate(4, 25.23, 97.24),
      new Coordinate(5, 22.00, 96.05),
      new Coordinate(6, 20.47, 97.02),
      new Coordinate(7, 17.20, 96.29),
      new Coordinate(8, 16.30, 97.38),
      new Coordinate(9, 14.05, 98.12),
      new Coordinate(10, 16.53, 97.38),
      new Coordinate(11, 21.52, 95.59),
      new Coordinate(12, 19.41, 97.13),
      new Coordinate(13, 20.09, 94.55)
    };

    static void Main(string[] args) {
      SolveTsp();
    }

    private static void SolveTsp() {
      SolverContext context = SolverContext.GetContext();
      Model model = context.CreateModel();

      // ------------
      // Parameters
      Set city = new Set(Domain.IntegerNonnegative, "city");
      Parameter dist = new Parameter(Domain.Real, "dist", city, city);
      var arcs = from p1 in data
                 from p2 in data
                 select new Arc { City1 = p1.Name, City2 = p2.Name, Distance = p1.Distance(p2) };
      dist.SetBinding(arcs, "Distance", "City1", "City2");
      model.AddParameters(dist);

      // ------------
      // Decisions
      Decision assign = new Decision(Domain.IntegerRange(0, 1), "assign", city, city);
      Decision rank = new Decision(Domain.RealNonnegative, "rank", city);
      model.AddDecisions(assign, rank);

      // ------------
      // Goal: minimize the length of the tour.
      Goal goal = model.AddGoal("TourLength", GoalKind.Minimize,
        Model.Sum(Model.ForEach(city, i => Model.ForEachWhere(city, j => dist[i, j] * assign[i, j], j => i != j))));

      // ------------
      // Enter and leave each city only once.
      int N = data.Length;
      model.AddConstraint("assign_1",
        Model.ForEach(city, i => Model.Sum(Model.ForEachWhere(city, j => assign[i, j],
          j => i != j)) == 1));
      model.AddConstraint("assign_2",
        Model.ForEach(city, j => Model.Sum(Model.ForEachWhere(city, i => assign[i, j], i => i != j)) == 1));

      // Forbid subtours (Miller, Tucker, Zemlin - 1960...)
      model.AddConstraint("no_subtours",
        Model.ForEach(city,
          i => Model.ForEachWhere(city,
            j => rank[i] + 1 <= rank[j] + N * (1 - assign[i, j]),
            j => Model.And(i != j, i >= 1, j >= 1)
          )
        )
      );

      Solution solution = context.Solve();

      // Retrieve solution information.
      Console.WriteLine("Cost = {0}", goal.ToDouble());
      Console.WriteLine("Tour:");
      var tour = from p in assign.GetValues() where (double)p[0] > 0.9 select p[2];
      foreach (var i in tour.ToArray()) {
        Console.Write(i + " -> ");
      }
      Console.WriteLine();
    }
  }
}

Author: natebrix

Follow me on twitter at @natebrix.

7 thoughts on “Traveling Salesman Problems using Solver Foundation: C# code”

  1. When I run this unmodified it puts out:

    Cost = 3323
    Tour:
    9 -> 0 -> 13 -> 2 -> 3 -> 4 -> 11 -> 12 -> 10 -> 8 -> 7 -> 5 -> 6 -> 1 ->

    The cost is correct but the tour in wrong. The printed tour has these costs:

    372+398+211+289+491+418+275+315+43+154+522+168+507 = 4163

    It is obviously not the right tour if you trace it out on a map.

  2. You can get the correct tour by changing “select p[2]” to “select p” in “var tour..”. And “Console.Write(i + ” -> “);” to “Console.Write(i[1] + ” -> ” + i[2]);” when printing out.

  3. I tried your solution on a not complete Graph (with some not existed edges) and your code did not provide any useful output. Can u please present a TSP solution for situation like I face?

  4. Hi Natebrix,

    Thank you very much for the help with the use of the solver, however, It seems like the current implementation selects a non-optimized path. I tried placing some restrictions to force an output however, for some reason, the solver generates an unexpected output.

    I Updated the constructor of Coordinate to take an extra parameter “ID” as a parameter. Below is the updated Constructor

    public Coordinate(int name, double x, double y, string id)
    {
    Name = name;
    X = x;
    Y = y;
    ID = id;
    }
    .
    .
    .

    I then update the distance property to force an optimized path however:

    public int Distance(Coordinate p)
    {
    double q1 = Math.Cos(Longitude – p.Longitude);
    double q2 = Math.Cos(Latitude – p.Latitude);
    double q3 = Math.Cos(Latitude + p.Latitude);
    int retValue;
    if (this.ID == p.ID)
    {
    retValue = 0;
    }
    else
    {
    retValue= (int)(6378.388 * Math.Acos(0.5 * ((1 + q1) * q2 – (1 – q1) * q3)) + 1);
    }
    return retValue;
    }

    Essentially the above code enforces a situation where two coordinates have the same the ID, they are made to have a distance of 0.

    I ran the code with the coordinates below:

    private static Coordinate[] data = new Coordinate[] {
    new Coordinate(0, 16.47, 96.10,”a”),
    new Coordinate(1, 16.47, 96.10,”a”),
    new Coordinate(2, 16.47, 94.44,”b”),
    new Coordinate(3, 20.09, 92.54,”c”),
    new Coordinate(4, 22.39, 93.37,”d”),
    new Coordinate(5, 22.39, 93.37,”d”),
    new Coordinate(6, 25.23, 97.24,”e”),
    new Coordinate(7, 25.23, 97.24,”e”),
    new Coordinate(8, 22.00, 96.05,”f”),
    new Coordinate(9, 20.47, 97.02,”g”),
    new Coordinate(10, 20.47, 97.02,”g”),
    new Coordinate(11, 22.00, 96.05,”f”),
    new Coordinate(12, 22.00, 96.05,”f”),
    new Coordinate(13, 22.00, 96.05,”f”),
    new Coordinate(14, 21.52, 95.59,”h”)
    }

    As it can be noticed from the coordinates above, Cities 11, 12, 13 have the same X,Y properties and ID’s. One will expect the selected path will have coordinates with the same ID right next to one another. However, that is not the case. I get the result below

    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 12 -> 13 -> 0 -> 9 -> 14 -> 8 -> 11 -> 10 ->

    which is inaccurate.

    I have tried revising the code based on the comments, but that has been to no avail. Can you please point me in the right direction, if I have a wrong implementation.

    1. Hi Jerome,

      Thanks for your question but I am focused on my new role at Frontline Systems – which provides both Excel and C# platforms for building optimization models, and many things besides. If I find time I will try to look into your issue, but I would urge you to have a look at Frontline: http://www.solver.com.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s