hk.pl

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

#! /usr/bin/perl -w
use strict;

# Extract approximate held karp bounds from output of lk --held-karp.
# Output format is as instance lines for expt.pl

my $iters = "N";
my $seed =0;
my $n=0;
my $d=-1;
my $last_bound = -1;
my $bound = -1;
my $last_file="none";
my $last_instance="none";
my $last_n=-1;
my $verbose=10;
foreach (@ARGV) {
	my $file = $_;
	print "# $file\n" if $verbose >= 50;
	if ( $file =~ m/^ben.(\d+).(\d+).(\d+)/ ) {
		if ( !($1 == $d && $2 == $seed & $3 == $n) ) {
			print "instance ben.$d.$seed.$n:$n:-l hka $last_bound : $iters\n";
			$last_bound = -1;
			$last_file = $file;
		}
		($d,$seed,$n) = ($1,$2,$3);
		open IN, "grep 'Held-Karp lower bound' $file|"
			|| die "Couldn't open $file for grepping";
		while (<IN>) {
			if ( m/^Held-Karp lower bound: (\d+\.\d+)/ ) {
				print "#$_" if $verbose >= 75;
				$bound = $1+0;
				$last_bound >= $bound || ($last_bound = $bound);
			}
		}
		close IN;
	} elsif ( m/^(.*)\.tsp/ ) {
		my $instance = $1;
		$instance =~ m/(\d+)$/;
		$n = $1;
		if ( !($file eq $last_file) ) {
			$last_n = int(1.1*$n) if m/^infill/; # Hack for infill instances:Add 10%
			print "instance $last_instance:$last_n:-l hka $last_bound : $iters\n";
			$last_bound = -1;
			$last_file = $file;
			$last_instance = $instance;
			$last_n = $n;
		}
		open IN, "grep 'Held-Karp lower bound' $file|" 
			|| die "Couldn't open $file for grepping";
		while (<IN>) {
			if ( m/^Held-Karp lower bound: (\d+\.\d+)/ ) {
				print "#$_" if $verbose >= 75;
				$bound = $1+0;
				$last_bound >= $bound || ($last_bound = $bound);
			}
		}
		close IN;
	}
}