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:
The easiest program to start with is LKH, because it's easier to build and faster to run than Concorde.
Installing LKH on a Unix-like system (e.g. Linux or Mac) can be as simple as running these commands:
curl -LO http://www.akira.ruc.dk/~keld/research/LKH/LKH-2.0.7.tgz tar zxf LKH-2.0.7.tgz cd LKH-2.0.7 make 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:
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
printtour.py to print the superpermutation corresponding to this tour:
bin/printtour.py 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/lkh_runner.py -o lkh/out/
You can start multiple instances of LKH, just change the output directory to avoid conflicts:
bin/lkh_runner.py -o lkh/out/1/ bin/lkh_runner.py -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/lkh_runner.py -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:
Concorde is a bit more fiddly to install, but once you have it working it’s simple to run:
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.
SUPERPERM_DIR=$(pwd) mkdir -p concorde/out cd /tmp/ concorde -o "$SUPERPERM_DIR"/concorde/out/5.out "$SUPERPERM_DIR"/tsp/5.tsp cd "$SUPERPERM_DIR"
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.
SUPERPERM_DIR=$(pwd) mkdir -p concorde/out cd /tmp/ concorde -o "$SUPERPERM_DIR"/concorde/out/6.out "$SUPERPERM_DIR"/tsp/6.tsp
superpermutationscontains various known superpermutations that are interesting for some reason.
Want to see what's in the superpermutations? Check out the
demutatordirectory. (Be wary of the C code.)