wm.pl

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

#! /usr/bin/perl -w

use strict;

# Arguments are taken as file names of the tsp.wm.gz files.
# Extract exact matching length from output of blossom4.
# Output format is as instance lines for expt.pl

my $iters = "N";
my $verbose=50;
my $n=-1;
my $instance;

foreach (@ARGV) {
	my $file = $_;
	if ( $file =~ m/^([^\s]+)\.tsp\.wp?m\.gz/ ) {
		$instance = $1;
		$instance =~ m/(\d+)$/;
		$n = $1;
		if ( -r $file ) {
			open IN, "gzip -d -c $file|";
			while (<IN>) {
				if ( m/Matching Length: (\d+\.\d+).*Dual/ ) {
					my $bound = $1;
					print "instance $instance:$n:-l optimal $bound : $iters\n";
				}
			}
		}
	}
}