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.