Editing Obtaining a TSP solver
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | + | To generate TSP art, a TSP solver is needed. However, generating TSP solutions with a TSP solver takes a lot of computer time. An image stippled to a thousand points may take several hours to solve the Travelling Salesman Problem for. Consequently, it is preferred to use a fast, approximate TSP solver instead. The Concorde TSP solver package includes both a TSP solver as well as some fast, approximate solvers. Of chief interest is the "linkern" approximate solver which can produce satisfactory solutions in under a minute. | |
− | |||
− | |||
− | |||
− | To generate TSP art, a TSP solver is needed. However, generating TSP solutions with a TSP solver takes a lot of computer time. An image stippled to a thousand points may take several hours to solve the Travelling Salesman Problem for. Consequently, it is preferred to use a fast, approximate TSP solver instead. The Concorde TSP solver package includes both a TSP solver as well as some fast, approximate solvers. Of chief interest is the "linkern" solver which can produce satisfactory solutions in under a minute. | ||
Binaries for linkern for Red Hat Linux 8.0, Solaris SPARC, and Windows (with Cygwin installed) are available at | Binaries for linkern for Red Hat Linux 8.0, Solaris SPARC, and Windows (with Cygwin installed) are available at | ||
− | + | [http://www.tsp.gatech.edu/concorde/downloads/downloads.htm Concorde TSP downloads] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | == Building on Macs == | |
− | + | For Macs with OS X, obtain the sources from the Concorde TSP downloads page cited above. You will also want the QSopt Linear Programming (LP) solver library and header file (<tt>qsopt.a</tt> and <tt>qsopt.h</tt>) from | |
− | + | [http://www2.isye.gatech.edu/~wcook/qsopt/beta/index.html QSopt LP downloads] | |
− | When obtaining the QSopt libraries, use the library files labelled as "OS X 10.5" for 32bit builds; the OS X 10.6 files are 64bit libraries. To configure | + | You will need a C compiler and assorted build tools as well. (E.g., Apple's Xcode developer tool kit.) When obtaining the QSopt libraries, use the library files labelled as "OS X 10.5" for 32bit builds; the OS X 10.6 files are 64bit libraries. To configure concorde for building, use the commands (assuming the Bash shell) |
<pre> | <pre> | ||
Line 49: | Line 20: | ||
</pre> | </pre> | ||
− | You must specify a complete, absolute directory path for | + | You must specify a complete, absolute directory path for the QSopt files. Failure to do so will result in a build failure. Also, ignore the "checking host system warning" generated by the configuration script. You have to specify the <tt>--host</tt> switch, but there's no acceptable value on a Mac for the script. Once the script finishes running, build the package with the <tt>make</tt> command. There is no install target for the makefile. The Concorde TSP solver will be the file <tt>./TSP/concorde</tt>. The linkern executable, <tt>./LINKERN/linkern</tt>. |
A shell script for obtaining, building, and installing the sources is available at the Eggbot code site, | A shell script for obtaining, building, and installing the sources is available at the Eggbot code site, | ||
− | + | [http://code.google.com/p/eggbotcode/downloads/detail?name=build-concorde-osx-0_2.sh build-concorde-osx-0_2.sh] | |
− | |||
− | |||
− | |||
− | |||
− | + | As the script builds in the <tt>/usr/local/</tt> directory tree, it needs to be run with root privileges. To build and install Concorde TSP elsewhere, edit the script changing the <tt>SRCDIR</tt> and <tt>BINDIR</tt> variables. | |
− | |||
− |