Editing Obtaining a TSP solver

Jump to: navigation, search

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:
[[TSP art|<<< Introduction (TSP Art)]] || Obtaining a TSP solver || [[Producing a stippled image with Gimp|Producing a stippled image with GImp >>>]]
 
----
 
 
== Introduction ==
 
== Introduction ==
  
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.
+
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.
  
 
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.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm Concorde TSP downloads]
+
:[http://www.tsp.gatech.edu/concorde/downloads/downloads.htm Concorde TSP downloads]
 
 
 
 
'''Note:''' While this tutorial is provided in the hopes that it might be helpful, ''we do not offer technical support for obtaining, installing, or using a TSP solver''.
 
 
 
  
 
== Concorde TSP on Windows ==
 
== Concorde TSP on Windows ==
Line 19: Line 13:
 
:[http://cygwin.com/ Cygwin home page]
 
:[http://cygwin.com/ Cygwin home page]
  
and download the latest Cygwin setup.exe.  Launch setup.exe and do not select or de-select any additional packages: the minimal set is selected upon startup of setup.exe.  Allow the program to run which will download, install, and configure the Cygwin environment.
+
and download the latest Cygwin <tt>setup.exe</tt>.  Launch <tt>setup.exe</tt> and do not select or de-select any additional packages: the minimal set is selected upon startup of <tt>setup.exe</tt>.  Allow the program to run which will download, install, and configure the Cygwin environment.
  
After the Cygwin install has completed, you should be able to open up a command window (DOS window) and manually run the linkern.exe executable you downloaded from the Concorde TSP downloads site.  To open a command window on Windows XP, select the "Run..." item from the "Start" menu,
+
After the Cygwin install has completed, you should be able to open up a command window (DOS window) and manually run the <tt>linkern.exe</tt> executable you downloaded from the Concorde TSP downloads site mentioned in the Introduction above.  To open a command window on Windows XP, select the "Run..." item from the "Start" menu,
  
http://wiki.evilmadscience.com/s3/eggbot/tspart/run01.png
+
http://mtbaldy.us/~dnewman/tspart/run01.png
  
 
In the pop-up window, type "cmd.exe" and then click the "OK" button,
 
In the pop-up window, type "cmd.exe" and then click the "OK" button,
  
http://wiki.evilmadscience.com/s3/eggbot/tspart/run02.png
+
http://mtbaldy.us/~dnewman/tspart/run02.png
  
 
You should then see a command window appear.  In that window, enter the full directory path to the linkern executable and press return.  The executable should run and display its command line options.  In the following figure, it is assumed that the executable is in the top-level directory of the C: drive,
 
You should then see a command window appear.  In that window, enter the full directory path to the linkern executable and press return.  The executable should run and display its command line options.  In the following figure, it is assumed that the executable is in the top-level directory of the C: drive,
  
http://wiki.evilmadscience.com/s3/eggbot/tspart/run03.png
+
http://mtbaldy.us/~dnewman/tspart/run03.png
  
 
== Concorde TSP on Macs ==
 
== Concorde TSP on Macs ==
  
Concorde TSP is not available pre-built for Macs.  However, if you are familiar with obtaining and building sources on your Mac, then building a copy of Concorde TSP is relatively straightforward.  You will need a C compiler and other build tools.  Apple's Xcode Developer Toolkit for OS X provides everything you will need.  That toolkit is available for download from Apple.  For on-line download, a registration is required and you will want the Xcode for "Mac Dev Center", not the "IOS Dev Center"The Xcode toolkit is often also included with your OS X distribution DVD as an extra package which you can manually install.
+
Concorde TSP is not available pre-built for Macs.  However, if you are familiar with obtaining and building sources on your Mac, then building a copy of Concorde TSP is relatively straightforward.  You will need a C compiler and other build tools.  Apple's Xcode Developer Toolkit for OS X provides everything you will need.  That toolkit is available for download from Apple (registration required)It is often also included with your OS X distribution DVD as an extra package which you can manually install.
  
To build Concorde TSP, first  obtain the sources from the Concorde TSP downloads page cited in the Introduction above.  You will also want the QSopt Linear Programming (LP) solver library and header file (qsopt.a and qsopt.h) from
+
To build Concorde TSP, first  obtain the sources from the Concorde TSP downloads page cited in the Introduction 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]
 
:[http://www2.isye.gatech.edu/~wcook/qsopt/beta/index.html QSopt LP downloads]
Line 49: Line 43:
 
</pre>
 
</pre>
  
You must specify a complete, absolute directory path for the directory containing the QSopt files as 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 "make" command.  There is no install target for the makefile.  The Concorde TSP solver will be the file ./TSP/concorde.  The linkern executable, ./LINKERN/linkern
+
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,
Line 55: Line 49:
 
:[http://code.google.com/p/eggbotcode/downloads/detail?name=build-concorde-osx-0_2.sh build-concorde-osx-0_2.sh]
 
:[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 /usr/local/ directory tree, it needs to be run with root privileges.  To build and install Concorde TSP elsewhere, edit the script changing the SRCDIR and BINDIR variables.
+
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.
  
 
== Concorde TSP on Linux ==
 
== Concorde TSP on Linux ==
  
Not much to worry about here: just obtain the binaries as per the Introduction above.  If you wish to build the binaries yourself, the OS X shell script cited in the Mac section should be a good starting point.  You'll want to omit the <tt>-m32</tt> compiler switch and consider specifying a recognized value for the <tt>--host</tt> switch.
+
Not much to worry about here.  Just obtain the binaries from as per the Introduction above.  If you wish to build the binaries yourself, you OS X shell script cited in the section above should be a good starting point.  You'll want to omit the <tt>-m32</tt> compiler switch and consider specifying a recognized value for the <tt>--host</tt> switch.
----
 
[[TSP art|<<< Introduction (TSP Art)]] || Obtaining a TSP solver || [[Producing a stippled image with Gimp|Producing a stippled image with GImp >>>]]
 

Please note that all contributions to Evil Mad Scientist Wiki are considered to be released under the GNU Free Documentation License 1.3 (see Evil Mad Scientist Wiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel | Editing help (opens in new window)