Code/data repository

[Robin Houston]

Following Niles Johnson’s excellent suggestion, I have created a repository on GitHub at https://github.com/superpermutators/superperm

It includes some basic instructions for getting started with LKH.

Please do send pull requests with improvements – and report to the group if you managed to get LKH or Concorde working; also report back if you didn’t get something working, so we can help.

If you’d like to be added to the “superpermutators” organisation, send me your GitHub username.

Robin

[Niles Johnson]

Hi all,

I did get LKH working, although unfortunately I haven't yet got the correct answer for 5 symbols :/  I ran it half a dozen times, but only got length 149.  I guess it's a matter of chance?

I did not get concorde running yet; here's the error message:

Host: kepler.math.osu.edu  Current process id: 61125

Using random seed 1517400603

Problem Name: superperm 5 (symmetrised)

Problem Type: TSP

Number of Nodes: 240

Explicit Lengths (CC_MATRIXNORM)

Set initial upperbound to 2070 (from tour)

Basic dual change required, but no candidate edges

ERROR: No dual change in basis finding code

Did not find a basic optimal solution

Fractional matching routine failed

Warning: restarting running timer Miscellaneous

need to link an lp solver to use this function

couldn't load problem

load_lp failed

need to link an lp solver to use this function

CCtsp_init_lp failed

I think I missed a part of the installation, and I wonder if it's this line:

NOTE that to build the concorde TSP solver (for the exact solution of TSPs), you must specify an LP solver in the configure step (either QSopt for CPLEX). 

Since I don't see a link for CPLEX, should I use QSopt?

-Niles 

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq2aQtEtwaPNo3H%2BsLOQih2%3DFfDRWjXAWk3qhU1gJxYRDg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Joshua Moerman]

Hi Niles,

 

Yes you should install QSopt, it worked for me (had similar errors without it). I had to use the beta version, the old version gave me linker errors : http://www.math.uwaterloo.ca/~bico/qsopt/beta/index.html

You need to specify a path to those files as one of the configure flag (as stated in the readme).

 

CPLEX is a commercial product, although I believe they have an academic license.

 

 

As for LKH, I have it (the arxiv version of the software) running on the problem for 6 symbols and found a solution for 873 so far. Since it’s randomised, it is a matter of luck and time, I guess.

 

Kind regards,
Joshua

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAACv-Db5TwSL5Csj%2BATPhfEB%3DjXikuDubfCpWmB%3DmQBDefyPVA%40mail.gmail.com.

[Robin Houston]

Thanks! Interesting. Perhaps my computer is especially lucky. Try increasing the RUNS parameter in the parameter file lkh/par/5.par, or setting MAX_TRIALS to something larger than the default (which is either 120 or 240 in this case – it’s documented to be the dimension, which is 120, but I think it might be doubled for an ATSP problem) and let us know what parameters work for you.

Yes, you need to install a Linear Programming solver to use Concorde. I have heard that CPLEX is considerably better than QSopt, though it has a restrictive license and I have not used it myself.

If anyone manages to get CPLEX going, that would be interesting. Here is IBM’s product page. Those of you with academic affiliations (as students or teachers) should be able to use the full version for free. I’m not sure whether the limited version that’s free to anyone would suffice for our purposes. It seems to be limited to 1000 variables and 1000 constraints.

[Niles Johnson]

On Wed, Jan 31, 2018 at 7:29 AM Joshua Moerman <ma...@joshuamoerman.nl> wrote:

Hi Niles,

 

Yes you should install QSopt, it worked for me (had similar errors without it). I had to use the beta version, the old version gave me linker errors : http://www.math.uwaterloo.ca/~bico/qsopt/beta/index.html

You need to specify a path to those files as one of the configure flag (as stated in the readme).

Thanks for the pointer to the beta page -- I needed that because my distro/processor wasn't on the other one :)

 

 

CPLEX is a commercial product, although I believe they have an academic license.

 

 

As for LKH, I have it (the arxiv version of the software) running on the problem for 6 symbols and found a solution for 873 so far. Since it’s randomised, it is a matter of luck and time, I guess.

 

Kind regards,
Joshua

 

From: Niles Johnson
Sent: 31 January 2018 13:17
To: Robin Houston
Cc: superper...@googlegroups.com
Subject: Re: Code/data repository

 

Hi all,

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAACv-Db5TwSL5Csj%2BATPhfEB%3DjXikuDubfCpWmB%3DmQBDefyPVA%40mail.gmail.com.

[Niles Johnson]

On Wed, Jan 31, 2018 at 7:40 AM Robin Houston <robin....@gmail.com> wrote:

Thanks! Interesting. Perhaps my computer is especially lucky. Try increasing the RUNS parameter in the parameter file lkh/par/5.par, or setting MAX_TRIALS to something larger than the default (which is either 120 or 240 in this case – it’s documented to be the dimension, which is 120, but I think it might be doubled for an ATSP problem) and let us know what parameters work for you.

Increasing to 500 did not work on the first try; increasing to 1000 did :)