lkdoit.in,v

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

# <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>
@


1.13
log
@Added more statistics for optimality and guessed best bounds.
Added support for clones (both multiple varying and single.)
Added lin318
@
text
@d39 1
d69 1
a69 1
		cloneproga="lk.deg ${args} ${lkoption} -m -v 0 -"
d105 1
a105 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b optimal 14379'
d111 20
d135 1
a135 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b optimal 42029'
d145 1
a145 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b optimal 18659688  -r two-level'
d151 10
d166 1
a166 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b optimal 23260728 -r two-level'
d176 1
a176 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b best-known-soln 469445  -r two-level'
d186 1
a186 1
	args='-v 50 -c nn 20 or nq 5 -S dsort -b best-known-soln 556045  -r two-level'
d197 1
a197 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d208 1
a208 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d220 1
a220 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d231 1
a231 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d238 12
d255 1
a255 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d267 1
a267 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d277 1
a277 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d287 1
a287 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d297 1
a297 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d307 1
a307 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d317 1
a317 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d327 1
a327 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d337 1
a337 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d347 1
a347 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d357 1
a357 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d367 1
a367 1
	baseargs='-v 50 -c nn 20 or nq 5 -S dsort -r two-level --no-round'
d387 10
d405 1
a405 1
		lin105 | lin318 | dsj1000 | clouds100 | clouds500 | fullgrid1024 | unifd1000 | unifd100 | rl5934  | brd14051 | pla7397 | uni1000 | annulus1000 | arith1000 | ball1000 | clusnorm1000 | cubediam1000 | cubeedge1000 | corners1000 | grid1000 | normal1000 | spokes1000 | allBentley) $1;;
a406 3
			lin105;
			lin318;
			dsj1000;
d411 2
a413 4
			fullgrid1024;
			rl5934;
			brd14051;
			pla7397;
@


1.12
log
@Added allBentley.
Reorderd allBently in order of fast and interesting to hard and boring.
Added --lk-option to pass an option to all executions of lk.
@
text
@d67 11
d79 5
d86 1
d88 2
a89 2
			lk.$1 ${args} ${sfcopt} ${lkoption} | \
			gzip -c >$outdir/out.$instance.$ml$sl$p.$1.gz
d110 10
d266 1
a266 1
	args="$baseargs -b lk-best 14.651462"
d286 1
a286 1
	args="$baseargs"
d296 1
a296 1
	args="$baseargs"
d306 1
a306 1
	args="$baseargs"
d316 1
a316 1
	args="$baseargs"
d326 1
a326 1
	args="$baseargs"
d347 2
d352 1
a352 1
		lin105 | dsj1000 | clouds100 | clouds500 | fullgrid1024 | unifd1000 | unifd100 | rl5934  | brd14051 | pla7397 | uni1000 | annulus1000 | arith1000 | ball1000 | clusnorm1000 | cubediam1000 | cubeedge1000 | corners1000 | grid1000 | normal1000 | spokes1000 | allBentley) $1;;
d355 1
d369 3
@


1.11
log
@Added support for Bentley distributions, all, and allBentley.
@
text
@d71 1
a71 1
			lk.$1 ${args} ${sfcopt} | \
d142 1
a142 1
	args="$baseargs"
d153 1
a153 1
	args="$baseargs -b lk-best 5.288940"
d176 1
a176 1
	args="$baseargs -b expected-hk-guess 227810" # .7204 * n sqrt(n)
d188 1
a188 1
	args="$baseargs -b expected-hk-guess 72040" # 7204 * sqrt(n)
d199 1
a199 1
	args="$baseargs"
d209 1
a209 1
	args="$baseargs"
d219 1
a219 1
	args="$baseargs"
d229 1
a229 1
	args="$baseargs"
d239 1
a239 1
	args="$baseargs"
d249 1
a249 1
	args="$baseargs"
d303 14
d320 4
a323 24
for i in $*; do
	case $i in
		lin105 
		| dsj1000 
		| clouds100 
		| clouds500 
		| fullgrid1024 
		| unifd1000 
		| unifd100 
		| rl5934  
		| brd14051 
		| pla7397 
		| uni1000
		| annulus1000
		| arith1000
		| ball1000
		| clusnorm1000
		| cubediam1000
		| cubeedge1000
		| corners1000
		| grid1000
		| normal1000
		| spokes1000
		) $i;;
a324 1
			allBentley;
a328 1
			fullgrid1024;
d331 2
a336 13
		allBentley) 
			 uni1000;
			 annulus1000;
			 arith1000;
			 ball1000;
			 clusnorm1000;
			 cubediam1000;
			 cubeedge1000;
			 corners1000;
			 grid1000;
			 normal1000;
			 spokes1000;
			;;
d340 4
a343 1
		*) echo doit: instance $i unknown, skipping >&2;;
d345 1
@


1.10
log
@Added -c nn 20 or nq 5 to all the tests
@
text
@d157 1
a157 1
function grid1024 {
d159 2
a160 2
	genprog=grid
	genargs='5 grid1024'
d163 1
a163 1
	instance=grid1024
d192 112
d308 48
a355 1
		lin105 | dsj1000 | clouds100 | clouds500 | grid1024 | unifd1000 | unifd100 | rl5934  | brd14051 | pla7397 ) $i;;
@


1.9
log
@Added encoding of SFC and massage type into output filename.
@
text
@d87 1
a87 1
	args='-v 50 -S dsort -b optimal 14379'
d97 1
a97 1
	args='-v 50 -S dsort -b optimal 18659688  -r two-level'
d108 1
a108 1
	args='-v 50 -S dsort -b optimal 23260728 -r two-level'
d118 1
a118 1
	args='-v 50 -S dsort -b best-known-soln 469445  -r two-level'
d128 1
a128 1
	args='-v 50 -S dsort -b best-known-soln 556045  -r two-level'
d139 1
a139 1
	baseargs='-v 50 -S dsort -r two-level --no-round'
d150 1
a150 1
	baseargs='-v 50 -S dsort -r two-level --no-round'
d162 1
a162 1
	baseargs='-v 50 -S dsort -r two-level --no-round'
d173 1
a173 1
	baseargs='-v 50 -S dsort -r two-level --no-round'
d185 1
a185 1
	baseargs='-v 50 -S dsort -r two-level --no-round'
@


1.8
log
@Added option for doing sfc across all the runs.
@
text
@d53 1
d56 1
d61 1
a61 1
		mp=r
d65 1
a65 1
		mp=r
d72 1
a72 1
			gzip -c >$outdir/out.$instance.$p.$1.gz
@


1.7
log
@Added support for rotating a eucliden instance .
Added support for more instances.
Allow user to specify permutations (by an environment variable.)
@
text
@d51 5
d69 2
a70 1
			lk.$1 $args | gzip -c >$outdir/out.$instance.$p.$1.gz
d82 1
d92 1
d103 1
d113 1
d123 1
d134 1
d145 1
d156 1
a156 1
	# unifd generates cities on a 10000x10000 square
d167 1
d179 1
d191 1
d197 1
@


1.6
log
@New better value for clouds 42 500
@
text
@d27 2
a28 2
if [ -d @@top_srcdir@@/scripts ]; then
	PATH=@@top_srcdir@@/scripts:$PATH
d38 2
d41 3
a43 3
reorder=tspreorder.pl
permutations="0 1 2 3 4 5" #seeds... 0 is identity permutation
outdir=.
d51 9
d62 3
a64 2
			${genprog} ${genargs} <$mygeninput | ${reorder} -s $p | \
					lk.$1 $args >$outdir/out.$instance.$p.$1
d93 28
d142 11
d175 1
d178 3
a180 1
		lin105 | dsj1000 | clouds100 | clouds500 | unifd1000 | unifd100) $i;;
@


1.5
log
@Take binaries and input data from reasonable places.
@
text
@d98 1
a98 1
	args="$baseargs -b lk-best 5.294496"
@


1.4
log
@More parameterization.
(paths wise)
output directory is current directory.
@
text
@d12 4
d17 5
d25 2
d30 7
a36 1
PATH=@@bindir@@:$PATH
d43 1
a43 1
function runlk () { 
d45 4
d51 1
a51 1
			${genprog} ${genargs} <$geninput | ${reorder} -s $p | \
d105 1
a105 1
	geninput=/dev/null
d116 1
a116 1
	geninput=/dev/null
@


1.3
log
@output directory is out.   :)
@
text
@d8 2
d11 10
d22 1
a22 1
reorder=../scripts/tspreorder.pl
d24 1
a24 1
outdir=out
d45 1
a45 1
	args='-v 25 -S dsort -b optimal 14379'
d54 1
a54 1
	args='-v 25 -S dsort -b optimal 18659688  -r two-level'
@


1.2
log
@output directory is now .
@
text
@d12 1
a12 1
outdir=.
@


1.1
log
@Initial revision
@
text
@d12 1
d19 1
a19 1
					lk.$1 $args >out/out.$instance.$p.$1
@