lkdoit.in

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

#! @BASH@
# @configure_input@
# lkdoit
# Run lk many experiments on specific inputs
# Using bash functions lets us be smart about lower bounds
# e.g.
#     lkdoit lin105 dsj1000
# This script is likely broken when it comes to finding data after
# installation, though.


# These might be need by other configuration-time definitions.
prefix=@prefix@
exec_prefix=@exec_prefix@

# We need to find the lk programs themselves.
if [ -d @bindir@ ]; then
	PATH=@bindir@:$PATH
fi

# But the new source directory overrides previous installs.
if [ -d @top_srcdir@/src ]; then
	PATH=@top_srcdir@/src:$PATH
fi

# So does the new scripts directory.
if [ -d @top_srcdir@/script ]; then
	PATH=@top_srcdir@/script:$PATH
fi

# We need to find the input data.
if [ -d @top_srcdir@ ]; then
	DATADIR=@top_srcdir@/data
elif [ -d @datadir@ ]; then
	DATADIR=@datadir@
fi
	
outdir=.
candidates="-c nq 10"

# Use randomized reordering
if [ -z "$permutations" ]; then 
	permutations="0 1 2 3 4 5" #seeds... 0 is identity permutation
fi

function runlk () {
	# 1 arg: lk program type
	if [ -z $geninput ]; 
	then mygeninput=/dev/null;
	else mygeninput=$DATADIR/$geninput; 
	fi
	if [ ${twod} = "yes" -a ${sfc} = "yes" ]; then
		sfcopt="--sfc"
		sl=s	# SFC letter
	else
		sfcopt=
		sl=		# SFC letter
	fi
	if [ ${rotate} = "yes" ]; then
		massage=tsprotate.pl
		massageswitch=-r
		ml=r	# Massage letter
	else
		massage=tspreorder.pl
		massageswitch=-s
		ml=
	fi
	if [ ${clone} = "yes" ]; then
		cloneproga="lk.deg ${args} ${lkoption} -M -v 0 -"
		cloneprogb="tspgen"
		clonelkopt="--no-round"
		cl=c	# clone letter
	else
		cloneproga=cat
		cloneprogb=cat
		clonelkopt=""
		cl=		# clone letter
	fi
	for p in $permutations; do
		if [ ${clone} = "yes" -a ${clonevary} = "yes" ]; then 
			clonearg="$[ $p + 15 ]" ; # 15 is arbitrary
		else 
			clonearg=""; 
		fi
		if [ ! -e stop ]; then
			${genprog} ${genargs} <$mygeninput | \
			${cloneproga} | ${cloneprogb} ${clonearg} | \
			${massage} ${massageswitch} $p | \
			lk.$1 ${args} ${sfcopt} ${lkoption} ${clonelkopt} | \
			gzip -c >$outdir/out.$instance.$ml$sl$cl.$p.$1.gz
		fi
	done
}

function gamut () {
	runlk deg
	runlk no_d
}


function lin105 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b optimal 14379"
	instance=lin105
	geninput=lin105.tsp
	gamut
}

function fl3795 {
    twod="yes"
    genprog=cat
    genargs=
    args="-v 50 ${candidates} -S dsort -b best-known 28772 --maxdepth 50"
    instance=fl3795
    geninput=fl3795.tsp
    gamut
}

function lin105.shake.98_20_5 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b shake-of-optimal 14379"
	instance=lin105.shake.98_20_5
	geninput=lin105.shake.98_20_5.tsp
	gamut
}

function lin318 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b optimal 42029"
	instance=lin318
	geninput=lin318.tsp
	gamut
}

function dsj1000 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b optimal 18659688  -r two-level"
	instance=dsj1000
	geninput=dsj1000.tsp
	gamut
}

function dsj1000.shake.98_20_5 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b shake-of-optimal 18659688  -r two-level"
	instance=dsj1000.shake.98_20_5
	geninput=dsj1000.shake.98_20_5.tsp
	gamut
}

function pla7397 {
# Note: I haven't implemented CEIL_2D
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b optimal 23260728 -r two-level"
	instance=pla7397
	geninput=pla7397.tsp
	gamut
}

function brd14051 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b best-known-soln 469445  -r two-level"
	instance=brd14051
	geninput=brd14051.tsp
	gamut
}

function rl5934 {
	twod="yes"
	genprog=cat
	genargs=
	args="-v 50 ${candidates} -S dsort -b best-known-soln 556045  -r two-level"
	instance=rl5934
	geninput=rl5934.tsp
	gamut
}


function clouds100 {
	twod="yes"
	genprog=ifs
	geninput=clouds.ifs
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=clouds.42.100
	genargs='42 100 clouds.42.100'
	args="$baseargs -b lk-best 1.571260"
	gamut
}

function clouds500 {
	twod="yes"
	genprog=ifs
	geninput=clouds.ifs
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=clouds.42.500
	genargs='42 500 clouds.42.500'
	args="$baseargs -b lk-best 5.277079"
	gamut
}

function fullgrid1024 {
	twod="yes"
	genprog=fullgrid
	genargs='5 fullgrid1024'
	geninput=''
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=fullgrid1024
	args="$baseargs -b optimal 320000 " #
	gamut
}

function unifd1000 {
	twod="yes"
	# unifd generates cities on a 10000x10000 square
	genprog=unifd
	geninput=''
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=unifd.42.1000
	genargs='42 1000 unifd.42.1000'
	args="$baseargs -b expected-hk-guess 227810" # 10000 * .7204 * sqrt(n)
	gamut
}

function unifd1000.shake.98_20_5 {
	twod="yes"
	# unifd generates cities on a 10000x10000 square
	genprog=cat
	geninput=unifd1000.shake.98_20_5.42.1000.tsp
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=unifd1000.shake.98_20_5.42.1000
	genargs=
	args="$baseargs -b shake-of-expected-hk-guess 227810" # 10000 * .7204 * sqrt(n)
	gamut
}

function unifd100 {
	twod="yes"
	# unifd generates cities on a 10000x10000 square
	genprog=unifd
	geninput=''
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=unifd.42.100
	genargs='42 100 unifd.42.100'
	args="$baseargs -b expected-hk-guess 72040" # 10000 * .7204 * sqrt(n)
	gamut
}

# Bentley distributions
function uni1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D uni -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=uni.98.1000
	args="$baseargs -b expected-hk-guess 22.781048" # .7204 * sqrt(n)
	gamut
}

function annulus1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D annulus -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=annulus.98.1000
	args="$baseargs -b probable-optimal 6.283129"
	gamut
}

function arith1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D arith -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=arith.98.1000
	args="$baseargs -b optimal 1996002"
	gamut
}

function ball1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D ball -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=ball.98.1000
	args="$baseargs -b lk-best 39.861509"
	gamut
}

function clusnorm1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D clusnorm -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=clusnorm.98.1000
	args="$baseargs -b lk-best 14.616720"
	gamut
}

function cubediam1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D cubediam -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=cubediam.98.1000
	args="$baseargs -b probable-optimal 2.822169"
	gamut
}

function cubeedge1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D cubeedge -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=cubeedge.98.1000
	args="$baseargs -b probable-optimal 1.995574"
	gamut
}

function corners1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D corners -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=corners.98.1000
	args="$baseargs -b lk-best 51.273379"
	gamut
}

function grid1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D grid -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=grid.98.1000
	args="$baseargs -b lk-best 1054.864055"
	gamut
}

function normal1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D normal -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=normal.98.1000
	args="$baseargs -b lk-best 106.790541"
	gamut
}

function spokes1000 {
	twod="yes"
	genprog=tspbgen.pl
	genargs='-D spokes -n 1000 -s 98'
	baseargs="-v 50 ${candidates} -S dsort -r two-level --no-round"
	instance=spokes.98.1000
	args="$baseargs -b probable-optimal 3.402766"
	gamut
}

function allBentley {
	 uni1000;
	 annulus1000;
	 ball1000;
	 clusnorm1000;
	 corners1000;
	 grid1000;
	 normal1000;
	 spokes1000;
	 arith1000;
	 cubediam1000;
	 cubeedge1000;
}

function allTSPLIB {
	lin105;
	lin318;
	dsj1000;
	pla7397;
	rl5934;
	brd14051;
	fl3795;
}


rotate="no"
sfc="no"
clone="no"
clonevary="no"
lkoption=""
while [ "$1" ]; do
	case $1 in
		fl3795 | lin105 | lin318 | dsj1000.shake.98_20_5 | lin105.shake.98_20_5 | dsj1000 | clouds100 | clouds500 | fullgrid1024 | unifd1000.shake.98_20_5 | unifd1000 | unifd100 | rl5934  | brd14051 | pla7397 | uni1000 | annulus1000 | arith1000 | ball1000 | clusnorm1000 | cubediam1000 | cubeedge1000 | corners1000 | grid1000 | normal1000 | spokes1000 | allBentley | allTSPLIB) $1;;
		all)
			clouds100;
			clouds500;
			unifd1000;
			unifd100;
			fullgrid1024;
			allTSPLIB;
			allBentley;
			;;
		-r) rotate="yes";;
		-p) rotate="no";;
		-c | --clone) clone="yes";;
		--clone-vary) clonevary="yes";;
		--no-clone) clone="no";;
		-s) sfc="yes";;
		--lk-option) 
			shift; lkoption=$1;
			;;
		*) echo doit: instance $1 unknown, skipping >&2;;
	esac
	shift;
done


# <HTML>
# <HEAD>
# <TITLE>Symmetric TSPs</TITLE>
# </HEAD>
# 
# <BODY>
# <HR>
# <H1> Best known solutions for symmetric TSPs </H1>
# <HR><H2>
# <UL>
# <LI> a280 :        2579  </LI> 
# <LI> ali535 :       202310  </LI> 
# <LI> att48 :       10628  </LI> 
# <LI> att532 :        27686  </LI> 
# <LI> bayg29 :       1610  </LI> 
# <LI> bays29 :       2020  </LI> 
# <LI> berlin52 :       7542  </LI> 
# <LI> bier127 :       118282  </LI> 
# <LI> brazil58 :       25395  </LI> 
# <LI> brd14051 :   [468942,469445] </LI> 
# <LI> brg180 :       1950  </LI> 
# <LI> burma14 :        3323  </LI> 
# <LI> ch130 :       6110  </LI> 
# <LI> ch150 :       6528  </LI> 
# <LI> d198 :        15780  </LI> 
# <LI> d493 :        35002  </LI> 
# <LI> d657 :        48912  </LI> 
# <LI> d1291 :       50801  </LI> 
# <LI> d1655 :       62128  </LI> 
# <LI> d2103 :       [79952,80450] </LI> 
# <LI> d15112 :     [1564590,1573152] </LI> 
# <LI> d18512 :       [644650,645300] </LI> 
# <LI> dantzig42 :       699  </LI> 
# <LI> dsj1000 :         18659688  </LI> 
# <LI> eil51 :         426  </LI> 
# <LI> eil76 :         538  </LI> 
# <LI> fl417 :       11861  </LI> 
# <LI> fl1400 :        20127  </LI> 
# <LI> fl1577 :       [22204,22249] </LI> 
# <LI> fl3795 :       [28723,28772] </LI> 
# <LI> fnl4461 :       182566  </LI> 
# <LI> fri26 :         937  </LI> 
# <LI> gil262 :       2378  </LI> 
# <LI> gr17 :         2085  </LI> 
# <LI> gr21 :         2707  </LI> 
# <LI> gr24 :         1272  </LI> 
# <LI> gr48 :         5046  </LI> 
# <LI> gr96 :        55209  </LI> 
# <LI> gr120 :        6942  </LI> 
# <LI> gr137 :       69853  </LI> 
# <LI> gr202 :       40160  </LI> 
# <LI> gr229 :        134602  </LI> 
# <LI> gr431 :        171414  </LI> 
# <LI> gr666 :        294358  </LI> 
# <LI> hk48 :        11461  </LI> 
# <LI> kroA100 :       21282  </LI> 
# <LI> kroB100 :       22141  </LI> 
# <LI> kroC100 :       20749  </LI> 
# <LI> kroD100 :       21294  </LI> 
# <LI> kroE100 :       22068  </LI> 
# <LI> kroA150 :       26524  </LI> 
# <LI> kroB150 :       26130  </LI> 
# <LI> kroA200 :       29368  </LI> 
# <LI> kroB200 :       29437  </LI> 
# <LI> lin105 :        14379  </LI> 
# <LI> lin318 :        42029  </LI> 
# <LI> linhp318 :       41345  </LI> 
# <LI> nrw1379 :       56638  </LI> 
# <LI> p654 :        34643  </LI> 
# <LI> pa561 :        2763  </LI> 
# <LI> pcb442 :        50778  </LI> 
# <LI> pcb1173 :       56892  </LI> 
# <LI> pcb3038 :       137694  </LI> 
# <LI> pla7397 :         23260728  </LI> 
# <LI> pla33810 :       [65913275,66116530] </LI> 
# <LI> pla85900 :       [141904862,142487006] </LI> 
# <LI> pr76 :       108159  </LI> 
# <LI> pr107 :       44303  </LI> 
# <LI> pr124 :       59030  </LI> 
# <LI> pr136 :       96772  </LI> 
# <LI> pr144 :       58537  </LI> 
# <LI> pr152 :       73682  </LI> 
# <LI> pr226 :       80369  </LI> 
# <LI> pr264 :       49135  </LI> 
# <LI> pr299 :       48191  </LI> 
# <LI> pr439 :        107217  </LI> 
# <LI> pr1002 :       259045  </LI> 
# <LI> pr2392 :       378032  </LI> 
# <LI> rat99 :        1211  </LI> 
# <LI> rat195 :       2323  </LI> 
# <LI> rat575 :       6773  </LI> 
# <LI> rat783 :       8806  </LI> 
# <LI> rd100 :        7910  </LI> 
# <LI> rd400 :       15281  </LI> 
# <LI> rl1304 :       252948  </LI> 
# <LI> rl1323 :       270199  </LI> 
# <LI> rl1889 :       316536  </LI> 
# <LI> rl5915 :       [565040,565530] </LI> 
# <LI> rl5934 :       [554070,556045] </LI> 
# <LI> rl11849 :       [920847,923368] </LI> 
# <LI> si175 :       21407  </LI> 
# <LI> si535 :       48450  </LI> 
# <LI> si1032 :        92650  </LI> 
# <LI> st70 :          675  </LI> 
# <LI> swiss42 :        1273  </LI> 
# <LI> ts225 :        126643  </LI> 
# <LI> tsp225 :       3919  </LI> 
# <LI> u159 :        42080  </LI> 
# <LI> u574 :        36905  </LI> 
# <LI> u724 :        41910  </LI> 
# <LI> u1060 :        224094  </LI> 
# <LI> u1432 :        152970  </LI> 
# <LI> u1817 :       57201  </LI> 
# <LI> u2152 :       64253  </LI> 
# <LI> u2319 :        234256  </LI> 
# <LI> ulysses16 :       6859  </LI> 
# <LI> ulysses22 :       7013  </LI> 
# <LI> usa13509 :       [19947008,19982889] </LI> 
# <LI> vm1084 :       239297  </LI> 
# <LI> vm1748 :       336556  </LI> 
# </UL>
# <HR>
# <UL>
# April 11, 1995
# </UL>
# <HR>
# </BODY>
# </HTML> 
# 
# <p>
# <h3> Return to <a href=../../home.html> our group</a> </h3>