Rusty concorde is a convenient API for the Travelling Saleperson Problem (TSP) solver concorde.

Contrary to concorde-rs, it does not use a modified version of Concorde (the counterpart is that it assumes a working installation of Concorde). It is highly inspired from dicorde-tsp for the C and C++ languages.

[🏗️] Installation guide

Fine-tuned installation

[💻] Solving a TSP instance in Rust

1. Defining the TSP graph

First, you need to define the graph on which you want to perform a TSP call. While not checked, the graph is assumed to be symmetric. There are three methods that can help you build a SymGraph:

1. pub fn new_from_weighted_edges(weigthed_edges: &Vec<(Edge<T>, f64)>) -> SymGraph<T> take as input the list of edges of the graph with there corresponding weights. Here is how it is used:

   let weighted_edges = vec![
      (Edge(Node('A'), Node('B')), 1.),
      (Edge(Node('C'), Node('B')), 4.),
      (Edge(Node('A'), Node('C')), 3.),
      (Edge(Node('C'), Node('D')), 2.),
   ];
   
   // Note that the concrete type of SymGraph<T> is given by the type contained in the Nodes
   let graph: SymGraph<char> = SymGraph::new_from_weighted_edges(&weighted_edges);

2. pub fn new_from_lt_matrix(lt_matrix: &LtMatrix) -> SymGraph<u32> takes as input a lower triangular matrix (only subdiag coefficients are stored). A distance of f64::MAX encodes the absence of edge between two nodes. Here is how it is used:

   let lt_matrix = LtMatrix {
      width: 4,
      inline_cells: vec![
         1., 
         3., 4., 
         f64::INFINITY, f64::INFINITY, 2.,
      ],
   };
   
   // Here, Nodes are named by the index of the row/column that correspond to them 
   let graph = <SymGraph<u32>>::new_from_lt_matrix(&lt_matrix);

3. pub fn new_from_nodes(nodes: &Vec<Node<T>>) -> SymGraph<T> is the last method. It takes as input a (reference to a) vector of nodes that implement the Distance trait. Here is how it is used:

   // If needed, define the type of the nodes
   type Coordinate2D = (f64, f64);
   
   // Implement the Distance trait for this type
   impl Distance<Coordinate2D> for Node<Coordinate2D> {
      fn distance_to(&self, node: &Self) -> f64 {
         let Node((x, y)) = self;
         let Node((z, t)) = node;
   
         f64::sqrt((x - z) * (x - z) + (y - t) * (y - t))
      }
   }
   
   // Now, you can define the nodes and let the function do the rest for you
   let nodes = vec![
      Node((0., 0.)),
      Node((0., 4.)),
      Node((3., 2.)),
      Node((5., 2.)),
   ];
   
   let graph: SymGraph<Coordinate2D> = SymGraph::new_from_nodes(&nodes);

2. Defining a TSP instance

Now that you have a graph, you can define a TSP instance. It allows you to specify the type of problem you want to solve, a time limit, etc. Here is how it is used:

let instance = TspInstance {
   graph,
   problem: TspProblem::TourTsp,
   target: None,
   time_limit: None,
};

• for problem you have the choice between TspProblem::TourTsp, TspProblem::PathTsp and TspProblem::StPathTsp(source: Node<T>, target: Node<T>).
• let target as None. It is only relevant for approximate variants of the solver.
• the optional time_limit correspond to the time, in seconds, after which Rusty Concorde will raise an error if no tour/path has been found so far. If nothing is specified, the time_limit is set to 60s by default.

3. Solving a TSP instance

For solving, it suffices to call solver::tsp_hk on the instance, that returns a solution if it doesn't raise an error. Here is how it is used.

let solution = solver::tsp_hk(instance);

You can then access the fields .length, .tour, .optimality of the solution. The first is the cost of the tour/path. The second is the vec of node that represent the tour/path, where each vertex appear exactly once (yes, even for a TourTsp, the loop is kept implicit). The last is set to Optimality::Optimal if you call the solver as we just described.

Complete MWE

Here is a test from solver.rs:

   type Coordinate2D = (f64, f64);

   // Implement the Distance trait for this type
   impl Distance<Coordinate2D> for Node<Coordinate2D> {
      fn distance_to(&self, node: &Self) -> f64 {
         let Node((x, y)) = self;
         let Node((z, t)) = node;

         f64::sqrt((x - z) * (x - z) + (y - t) * (y - t))
      }
   }

   // Define the graph
   let nodes = vec![
       Node((0, 0)),
       Node((0, 1)),
       Node((0, 2)),
       Node((0, 3)),
       Node((0, 4)),
   ];

   // Solve StPathTSP
   let graph: SymGraph<Coordinate2D> = SymGraph::new_from_nodes(&nodes);
   let solution = solver::tsp_hk(TspInstance {
       graph: graph,
       problem: TspProblem::StPathTsp(Node((0, 2)), Node((0, 3))),
       target: None,
       time_limit: None,
   });

   assert_eq!(solution.length, 7.0);
   assert_eq!(solution.tour.len(), 5);
   assert_eq!(solution.optimality, crate::optimality::Optimality::Optimal);

[⚙️] A quick overview of the program operation

On calling solver::tsp_hk or solver::tsp_lk, the user problem (that is either a TourTsp, PathTsp or StPathTsp instance) is translated into a TourTsp instance. The underlying solver (Concorde or LKH) is then called directly on the instance, without writing/reading to a file. The recovered solution to the reduced TourTsp instance is then translated back into a solution to the user problem.

The Concorde solver is called using pub fn CCtsp_solve_sparse (from concorde/TSP/tsp_call.c).

Defining a TSP instance

Under the hood, Rusty concorde calls Concorde with either CCtsp_solve_sparse or CCtsp_linked_tour, that take as input an integer symmetric instance of TSP written as the (serialized) list of its edges. For convenience, Rusty concorde propose multiple way of defining a TSP instance, as well as way to call the solver on variants of TSP (eg. PathTSP, s-t-PathTSP).

Installing Concorde

(for academic use only, for commercial refer to: )

Here is a short tutorial on how to install Concorde on a Mac M4. I hope the steps are sufficiently clear so that it can be used by anyone.

Get the Concorde source code

wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz
tar -xzvf co031219.tgz

Get a LP software compatible with Concorde. Put it with concorde -# For non "M1-mac", qsopt links differ. Explore the website, or see (eg.) https://github.com/jvkersch/pyconcorde/blob/main/setup.py

cd concorde
mkdir qsopt
cd qsopt
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/m1/qsopt.a
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/m1/qsopt.h
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/m1/qsopt
cd ..

Then you need to make Concorde. First, fix the config file: -# for Linux, remove ''

sed -i '' 's/^main(){return(0);}/int main(){return(0);}/g' configure

In order to help the tool to guess Mac architecture, copy those files

cp /opt/homebrew/Cellar/automake/1.17/share/automake-1.17/config.* .

You can now make the thing -# update with your path to the qsopt folder

./configure --host=darwin --with-qsopt=/Users/lackerma/Documents/01_research/04_tools/concorde/qsopt
make

You can now check concorde is installed correctly with (eg. solving a random instance)

./TSP/concorde -s 99 -k 100

Also, give concorde.a a prettty name for Rusty concorde to see it.

cp concorde.a libconcorde.a
cp qsopt/qsopt.a qsopt/libqsopt.a

Installing Rusty Concorde

In the rusty_concorde folder, create a symlink toward your concorde installation with ln -s path/to/concorde/folder ..

Ensure the Mac deployement target is the same as the one of concorde (otherwise it will not be able to link): ``

export MACOSX_DEPLOYMENT_TARGET=15.0

You can then make the library with cargo build and check the installation with cargo test.

MWE

See the test solver.rs for a solver call. See the tests of graph.rs for multiple ways of defining a graph.

Devlog

The simplest entry point is probably int CCtsp_solve_sparse this is the function called by Pyconcorde (https://github.com/jvkersch/pyconcorde)

https://users.rust-lang.org/t/compile-rust-binary-for-older-versions-of-mac-osx/38695/2

Discovery: Concorde always use integers distances (see. concorde/UTIL/edgelen.c for details)

Todo:

• Remove magic number (cancelled)
• Handle PathTSP instance
• Handle stPathTSP instance