lkdoit.in,v

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

head	1.14;
access;
symbols
	zero-five-zero:1.14
	zero-four-seventeen:1.14
	zero-four-ten:1.14
	zero-four-nine:1.14
	zero-four-eight:1.14
	zero-four-five:1.14
	zero-four-three:1.14
	zero-four-zero:1.14;
locks
	neto:1.14; strict;
comment	@# @;


1.14
date	98.01.23.21.39.22;	author neto;	state Exp;
branches;
next	1.13;

1.13
date	97.11.14.22.55.39;	author neto;	state Exp;
branches;
next	1.12;

1.12
date	97.11.07.22.22.45;	author neto;	state Exp;
branches;
next	1.11;

1.11
date	97.11.01.19.14.39;	author neto;	state Exp;
branches;
next	1.10;

1.10
date	97.10.28.21.46.01;	author neto;	state Exp;
branches;
next	1.9;

1.9
date	97.10.17.15.34.40;	author neto;	state Exp;
branches;
next	1.8;

1.8
date	97.10.17.15.06.27;	author neto;	state Exp;
branches;
next	1.7;

1.7
date	97.10.16.19.00.15;	author neto;	state Exp;
branches;
next	1.6;

1.6
date	97.06.25.21.04.55;	author neto;	state Exp;
branches;
next	1.5;

1.5
date	97.06.25.18.52.48;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	97.06.20.22.58.47;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	97.06.19.19.04.13;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	97.06.19.18.59.42;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	97.06.19.18.58.36;	author neto;	state Exp;
branches;
next	;


desc
@Run many lk experiments on specific inputs.
@


1.14
log
@Added fl3795
Made the candidate set easily parameterizable in the script, and
ddefault is nq 10
@
text
@#! @@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>