NEOS Server Home

NEOS Interfaces to concorde

WWW Form & Sample Submissions
Email
XML-RPC

concorde

The NEOS Server offers Concorde for the solution of Traveling Salesman Problems.

Concorde was written by David Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook.

Source code, binaries, and documentation are available from the Concorde homepage

This solver was implemented by Hans Mittelmann and executes at


Using the NEOS Server for Concorde

The user must submit a symmetric TSP problem in either the simple 2-d coordinate form (first line is just the number of cities!)

              #cities
              x_0 y_0
              x_1 y_1
              .
              .
              .
              x_n-1 y_n-1 

or in TSPLIB format.

The user can currently choose between applying the exact algorithm and the Lin-Kernighan heuristic (especially for large instances). Concorde can be called with the authors' QSopt LP solver or CPLEX. This small benchmark gives you an impression of its performance with different LP solvers. If Concorde terminates prematurely it may have run out of time or memory. Either the fixed random seed 99 can be used or a variable one.
Users who submit via web submission (not email or XML-RPC) can further choose to receive a PDF file plotting the optimal resp. final tour.

Web Submission Form
Concorde data(xy-list file, L2 norm)
Enter the complete path to the file with the xy-list (distances measured in the Euclidean(L2) norm)
Concorde data(xy-list file, L1 norm)
Or, enter the complete path to the file with the xy-list (distances measured in the Manhattan(L1) norm)
Concorde data(TSPLIB format file)
Or, enter the complete path to the symmetric TSPLIB file
Algorithm
Choose the algorithm (cqs=QSopt, con=CPLEX [default], lk=Lin-Kernighan)
Concorde(CPLEX)
Concorde(QSopt)
Lin-Kernighan
Random seed
Choose the random seed (fixed=99 [default], variable=random)
fixed
variable
PDF plot
PDF file of the optimal tour? (no [default], cp=yes, pf=w/o cities)
No tour plot
PDF of optimal tour
Without cities
Comments
Additional Settings
Dry run: generate job XML instead of submitting it to NEOS
Short Priority: submit to higher priority queue with maximum CPU time of 5 minutes
E-Mail address:
Please do not click the 'Submit to NEOS' button more than once.