Logo pla85900 Home > Solution > Software
Concorde Plane
  Home
  Optimal Tours
  pla85900 Home
  The Application
  Pictures
  15-Year Race
  Solution
  CPU Time
Software
  Hardware
  B&C Trees
  DP-Log 0
  Data Sets
Computer Software used in the pla85900 Computation
Concorde

The Concorde TSP code was used in the pla85900 computation, including the domino-parity (DP) inequality extension.

LKH

Variants of the new 2.0 version of the LKH tour-finding code were used by Keld Helsgaun in his work that produced the first pla85900 tour of value 142,382,641.

LP Solver

The linear programming (LP) problems encountered in the pla85900 computation were solved with the simplex method as implemented in the ILOG Cplex solver. The computations made use of Cplex 6.5 and Cplex 8.0. The solver interface is described in the file LP/lpcplex.c in the Concorde distribution.

Parallel Code

Concorde's parallel implementation of branch-and-cut makes use of NFS sockets for machine communication; the source code for the communication functions is contained in the file UTIL/safe_io.c in the Concorde distribution. The shared-memory parallel cutserver makes use of the PThreads library; the source code can be found in the file TSP/cutpool.c.

Operating Systems

The pla85900 computations were carried out on a clusters dual-processor Intel Xeon and AMD Athlon workstations running version of Red Hat Linux.

Home | pla85900 Home Back
Last Updated: October 2007