Superperm Save

Project README


The aim of this project is to find short superpermutations. Our main technique at the moment is to encode the superpermutation problem as an instance of the Travelling Salesman Problem, and run TSP solvers. There are two main TSP solvers that we use:

  • LKH is a fast, randomised, approximate solver.

  • Concorde is a slower exact solver.

Getting started

The easiest program to start with is LKH, because it's easier to build and faster to run than Concorde.

Install LKH

Installing LKH on a Unix-like system (e.g. Linux or Mac) can be as simple as running these commands:

curl -LO
tar zxf LKH-2.0.7.tgz
cd LKH-2.0.7
cp ./LKH /usr/local/bin/

Test it out

A good way to make sure LKH is working as expected is to find a short permutation of 5 symbols, which it can do very fast.

In this directory, run:

LKH lkh/par/5.par

This should create at least one output file in the output directory lkh/out/. The filename is tagged with the length of the tour. Adding 5 to this number gives the length of the superpermutation. You will probably have an output file called lkh/out/5.148.lkh, which represents a minimal-length superpermutation. You can use the script to print the superpermutation corresponding to this tour:

bin/ 5 lkh/out/5.148.lkh

which should print something like


Break new ground

Now you’ve got LKH running, you can start to discover new things! You could look for novel short superpermutations of 6 symbols. It is recommended to use the runner script to avoid some shortcoming in the usage of LKH for this project:

bin/ -o lkh/out/

You can start multiple instances of LKH, just change the output directory to avoid conflicts:

bin/ -o lkh/out/1/
bin/ -o lkh/out/2/

LKH keeps all the solutions below a certain weight and discards the others. The max weight is configurable with -w and is 866 by default.

Or if you’re feeling ambitious, you can try 7 symbols! The input file for 7 is quite large, so it is not included in the repository and you will have to create it first:

make atsp/7.atsp
bin/ -o lkh/out/ -p atsp/7.atsp -n 7

Share what you find.

You can run the following command to see all options of the runner:

bin/ -h

Try Concorde

Concorde is a bit more fiddly to install, but once you have it working it’s simple to run:

concorde tsp/5.tsp

Be warned that it creates a LOT of temporary files in the working directory, so you may want to do something a bit more elaborate and run it from a different directory, e.g.

mkdir -p concorde/out
cd /tmp/
concorde -o "$SUPERPERM_DIR"/concorde/out/5.out "$SUPERPERM_DIR"/tsp/5.tsp

The most obvious low-hanging fruit is to use it to find a provably shortest tour on 6 symbols. This will take at least several days to run.

mkdir -p concorde/out
cd /tmp/
concorde -o "$SUPERPERM_DIR"/concorde/out/6.out "$SUPERPERM_DIR"/tsp/6.tsp

Other stuff

  • The directory superpermutations contains various known superpermutations that are interesting for some reason.

  • Want to see what's in the superpermutations? Check out the demutator directory. (Be wary of the C code.)

Open Source Agenda is not affiliated with "Superperm" Project. README Source: superpermutators/superperm
Open Issues
Last Commit
2 years ago

Open Source Agenda Badge

Open Source Agenda Rating