Version:  September 28, 2007

Concorde TSP Verification Code
For information on the verification process, see the paper

  Title:   Certification of an optimal TSP tour through 85,900 cities
  Authors: David L. Applegate, Robert Bixby, Vasek Chvatal, William Cook, 
           Daniel G. Espinoza, Marcos Goycoolea, and Keld Helsgaun

To build the executable code "bbcheck" issue the command "make bbcheck"
in the directory containing the source code.

To run bbcheck on the 532-city instance "att532" use

      bbcheck att532.tsp att532.allproof

The file att532.tsp describes the TSP instance in TSPLIB format.  This
file can be obtained from Gerd Reinelt's TSPLIB site

      http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

or as part of the allproofs.tgz file on the page

      http://www.math.uwaterloo.ca/tsp/pla85900/proof

The att532.allproof file contains the certification data.  This file is also
part of allproofs.tgz.

By default, bbcheck will verify the branch-and-bound search tree, but
it will not verify the cutting-planes having hypergraphs that do not match
a list of known templates.  To verify the remaining cutting-planes (using
the Held-Karp TSP solver), the option -h should be given.  In the case of
att532.allproof, all hypergraphs of cutting-planes match known templates.
To test the verification of non-template cuts, use the file att532.hkproof.

      bbcheck -h att532.tsp att532.hkproof
      
To run bbcheck on the 85,900-city instance pla85900 use

      bbceck pla85900.tsp pla85900.allproof

This will take approximately 30 minutes.  To verify the full set of
cutting planes, use

      bbcheck -h pla85900.tsp pla85900.allproof

This will take approximately 600 hours.

If a network of computers is available, the cutting-plane verification can be
carried out in parallel by building the bbboss and bbgrunt codes.  On
a "boss" machine issue the command

      bbboss pla85900.allproof

Suppose the boss machine name is "iorek".  On a set of "worker" machines
issue the command

      bbgrunt iorek

The workers will communicate with the boss via NFS sockets, reporting back
the successful verification of individual cutting planes.