expttspnsqrt10

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

#! /usr/bin/perl -I../script ../script/expt.pl
# vi : set ts=4 sw=4:
# expt.data.in
# Driver tables for experiments.
#
# Kinds of lines:
# 	"require": earliest version of expt.pl that can run this script.
# 	"salt": a number to be mixed with permutation number and instance name
#		to derive a random number generator seed.
#	"algprefix": used to form algorithm-specific names for output files.
# 	"inputdir": directory where the input tsp files are
# 	"outputdir": directory where the output files should go
# 	"scriptdir": directory where scripts are.
# 	"bindir": directory where the lk programs are (lk.deg and lk.no_d).
# 	"program": base name of program to run (e.g. lk or lk.single);
#		The variations will be appended to this
# 	"variations": colon-separated list of things to append to "program" to
#		get the main optimizer program.
# 	"instance": perform experiments on the named TSP file.
#	"permutations": list seeds for permuting cities (0 is identity)
#	"lkargs": list of arguments that are always supplied
#	"preprocess": list preprocessing command (e.g. for cloning)
#		There can be multiple preprocessing commands, for multiple kinds of
#		runs
#
# instance line Fields, separated by colons:
#  	name of file (without .tsp) in $inputdir
#	N, the number of cities in the instance
#	option to always use with this instance. (Use -l and -u here)
#   (sequence of entries indicating number of iters to run.  
#		N is replaced by the number of vertices.)
#
# preprocess line fields, separated by colons:
#	the command to run on the file with output piped to reorderer.
#	the early suffix to put on instance name when generating output files
#	the late suffix to put on instance name when generating output files
#

require 	0.4.14  # First version this script can use: need "program" directive
salt	 	314159
algprefix	tsp.
inputdir	../data
outputdir	.
scriptdir	../script
bindir		../src
program		lk
variations	.deg:.no_d
#variations	.deg
#variations	.no_d
permutations 0:1:2:3:4:5:6:7:8:9
#lkargs     	-v 50 -S dsort --maxdepth 50 -c nq 10
lkargs     	-v 50 -S dsort --maxdepth 50 -c nn 20 or nq 5
preprocess cat   : :  # Empty mod letters.
#preprocess ../src/lk.deg -M -v 0 -S dsort | ../src/tspgen -s %p142 : t%p142 : c
#preprocess ../src/jitter -s %p142 : j%p142 : c
#preprocess ../src/shake -s %p142 : s%p142 : c

#instance unifd.42.1000:1000:--no-round -l expected-hk-guess  227810:1:N/sqrt(10)/10
instance lin105:105: -l optimal 14379 : 	N/sqrt(10)
instance lin318:318: -u optimal 42029 -l hk 41911 : N/sqrt(10)
instance att532:532:	-u optimal 27686 -l hk 27420 : N/sqrt(10) # computed HK from Table 8.16
instance dsj1000:1000:	-u optimal 18659688 -l hk 18546554 : N/sqrt(10)
instance pr1002:1002:	-u optimal 259045 -l hk 256766 : N/sqrt(10)
instance pcb442:442:	-u optimal 50778 -l hk 50500 : N/sqrt(10)
instance pcb1173:1173:	-u optimal 56892 -l hk 56351 : N/sqrt(10)
instance pr2392:2392:	-u optimal 378032 -l hk 373490 : N/sqrt(10) 
instance pcb3038:3038:	-u optimal 137694 -l hk 136588 : N/sqrt(10)
instance fnl4461:4461:	-u optimal 182566 -l hk 181570 : N/sqrt(10)
instance pla7397:7397:	-u optimal 23260728 -l hk 23126594 : N/sqrt(10) #computed HK
instance fl3795:3795:	-u optimal 28772 -l hk-estimate 28476 : N/sqrt(10) # take 1.04 as optimal's excess percentage over hk
#instance gr666:666:	-u optimal 294358 -l hk 292486 : N/sqrt(10) # computed HK from Table 8.16