todo,v

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

head	1.6;
access;
symbols
	zero-five-zero:1.6
	zero-four-seventeen:1.6
	zero-four-ten:1.5
	zero-four-nine:1.3
	zero-four-eight:1.3
	zero-four-five:1.2
	zero-four-three:1.1
	zero-four-zero:1.1;
locks
	neto:1.6; strict;
comment	@# @;


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

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

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

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

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

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


desc
@TODO list for the LK software.
@


1.6
log
@Many things now deprecated because I've done them.
@
text
@Medium term (post-proposal, pre-writing thesis):
------------------------------------------------
Add depth logging to match, or factor it out from jbmr and then add to
both jbmr and match.

Still need to do non-metric inspired instances.


Medium long term (post-writing, pre-defense):
---------------------------------------------

Long term (post-defense):
-------------------------

Factor out options into an lkoption object.  This should elide many of the
spurious reasons for including lk.h.  That should help in moving to
a library, and it should reduce make times when lk.w changes.

Implement Martin-Otto-Felten -style chained optimization (maybe)
(randomized acceptance of worse tours.)

Optional:
---------

Fix tspreorder so it works on all edge types (can't reorder upper row matrices
right now...)  Maybe use a fixed-up TSP.pm.  
Update: I'm fixing up TSP.pm.  It is functional enough to create a simple
tsplib2rothberg.pl
For multiple runs, DSJ uses randomized construction heuristics.  See
email from him August 1 1998.
Update: With randomized construction routines, this isn't so critical, 
so I downgraded its priority.


Insert code into match.w so that we can get graphs out of it.

Upgrade nn so it does nq. (Done)
	Be smarter about it, e.g. don't search saturated quadrants.

Write an edge length distribution sampler.
	This might not be as good as I might think, because the clones are
	not that interesting, visually anyway (for now).

Convert to use HAVE_* macros. (partially done)


Write self-check target lk.


Deprecated items:
-----------------

Write better scripts for generating graphs.
	1998/10/17.  See data dir, *.pl, and gen*.pl in this dir.

Create a script to generate all the data in the data/ directory
according to the rules given in my methodology section.
Write a script to perform Held-Karp computations on the instances
for which I haven't got values from elsewhere.
	1998/10/17.  See data dir, *.pl, and gen*.pl in this dir.

Non-metric instance data.
	1989/10/17.  DSJRandom now included; see data dir.

Adapt others' code for max-weight matching to min-weight matching.  
Must learn primal-dual.
Update: Rothberg's code does min weight and max weight matching.  But it
uses type int as the length type.
	Done. 1998/10.  Watch out in Rothberg's code for 2args vs. 3 args to
	perfect_match.
	Even better, get blossom4 from William Cook & Andre Rohe.  That works
	much better and faster.

Find out that fscking GEO distance function.  Check the reference
implementations, e.g. 
	Done. 1998/10.  Got in touch with DSJ about DSJ_RANDOM, too,
	and made it the same as behaviour in Concorde, w.r.t. seeds, etc.

Fix Held-Karp to try to use the nnlists for all but the last
iteration.  This affects decluster (MST computation) too.
	Done. 1998/10/16   I also tuned parameters.

Implement randomized construction routines.  See mail from DSJ Aug 1 1998.
1998/8/9: Done.  Now I don't have to rely on tspreorder to transform
instances.  But it was trickier than I thought it would be.

Right now I do all possibilites for t6 t7 t8 when t1 through t6 is not
a valid 3-change.  JBMR don't: they do only the first valid one (feasibile
and cumgain).  See Johnson and McGeoch chapter, page 257, first full
paragraph.  So my code does more work than theirs, potentially.  I must
fix that with a compile-time option.
Update: 1998/8/8 (lk-0.4.6).  This is a command-line option:
	--no-extra-backtrack (the default), and
	--extra-backtrack
A -c nq 10 -i 100 (40 quadrant neighbours, ILK(100)) run on dsj1000, the
optimization phase is 2-8 times faster, with better answers (sometimes 2
times closer to optimal).  Sounds good.
But variance in run times is still moderate: up to 25% on different
tspreorder'ed runs.  

Modify all code so it can handle arbitrary instances.
	Now LK runs from start to finish with arbitrary instances supported by 
	read (i.e. LOWER_DIAG_ROW, UPPER_ROW, EXPLICIT, EUC_2D, CEIL_2D).
	1998/4/16.

Finish jitter
	src/jitter.w

Write shake
	src/shake.w

Generate Bentley distributions
	script/tspbgen.pl.in

Run experiments with --maxdepth 50
	This is now supported in lkdoit via --lk-option

Generate TSP instances based on distribution of edge lengths.
	DONE.  They all look the same: very sparse, fractal dimension 1.1?

Switch over from LINEAR to SPLAY in the tabu check.
	In light of declustering this might not matter much.

Implement CEIL_2D, and check that kdtree is ok with it.
Implement supports_kd_tree.
	DONE October 1997.  Both work.

Write to log: cost(t[1],t[2]) and decluster_d(t[1],t[2]):
	DONE.  It appears variation in runtimes is mainly
	due to start tour variation, and these effects might be
	exacerbated by very clustered instances.

Be smarter about which city we next choose for t[1].
	- most recently changed
	- longest edge remaining among dirty cities
	- edge with longest excess over cluster distance. (this might be great!) 
	- edge with longest excess over nearest neighbour. (this might be better...)
	In light of the above, this might not matter much.


Dust off HK code from 1994.
	Done.  It works with read, error, memory as in LK.
	Now integrate it with lk?
	Add better option handling.
graft held-karp code onto lk, or write a script to get its output and
	dump it into an answer database.
	Integrate
		prim.w
		hk.w
		ascend.w
		ee.w
		branch.w
		kruskal.w
		upper.w
	Namespace clean:
		prim
	Sequential only:
		prim
This item has been finished.  The output isn't pretty, but it's functional.
	
	
write a perl script to combine results into a latex table.
	Done.  
	See script/least.pl for getting least length among runs on an instance.
	See script/results.pl for generating a table.  It's semi-automatic.

extend expt.pl to allow for clones (perhaps parameter inside expt.data)
	Done.  See also the ``require'' directive for expt scripts.


Adapt match for graphs with odd number of vertices (see. DIMACS1)
	Done.  See src/read.w

Release the code as lk-0.1.0.
Update: Released at lk-0.4.0
See http://www.cs.utoronto.ca/~neto/research/lk

Check the distribution on IRIX.  
	Use the native C compiler on IRIX.  
	(CC=cc ./configure; also, make sure we aren't using COFF)

Check the distribution on cygwin32.
	(I get an internal compiler error with beta 18.  Did not investigate.)
Update: Under beta19, it compiles once I change the return type of
getpagesize to size_t as it properly should be.


JBMR and Cook et.al. use a FIFO for the dirty/active cities.  Do the same,
with a compile-time option for previous behaviour.
Update: done in lk-0.4.5.

ILK for matching.
	Done.  match.w version 1.12
	Iterating LK for matching doesn't seem to improves solutions.  But it
	*does* take longer.... :-)


Use hash tables (even broken ones) for TABU check. (maybe)
->Update: Cook et. al's Concorde is released.  It uses a conservative test:
hash function is h(u,v) = u xor v.  It doesn't resolve collisions with
chains.  It just answers ``present'' possibly too many times.  Simple,
effective, and mostly right.   But IIRC, the splay tree dictionary 
code uses no more than 6% of runtime, and it is precise.
->Update: Finished 1998/8/20.  I implemented precise tabu for TSP lists 
based on hash (xor func) with chaining.  Same deg vs. no_d dichotomy.
Thank goodness!  Still don't have it for matching.  But it's slightly 
more complicated because matching is simpler.  (It backs off one by one
in the backtracking phase.)  I'd have to change the tabu_hash module
interface.


MST dangle and construct (and other inspired distributions)
->Update: Sun Aug 23 17:45:21 EDT 1998
	Dangle and construct now works.  See tspgen.  However, geometry
	sometimes makes pure dangling and constructing impossible.  We try
	our greedy best, though, and report how far off we are.
	The instances produced by dangle and construct are *locally* similar
	in TSP, but globally are very stringy and too far separated, much
	like tspgen output when packing factor and join length bias are small.
	Alas.

@


1.5
log
@Dangle and construct is as good as it will get.
@
text
@a2 1

a5 3
Find out that fscking GEO distance function.  Check the reference
implementations, e.g. 

a7 9
Non-metric instance data.

Adapt others' code for max-weight matching to min-weight matching.  
Must learn primal-dual.
Update: Rothberg's code does min weight and max weight matching.  But it
uses type int as the length type.

Write better scripts for generating graphs.

d52 31
@


1.4
log
@Implemented hash tables.
@
text
@d10 1
a10 1
MST dangle and construct (and other inspired distributions)
d12 1
a12 1
Non-metric instance data
d193 10
@


1.3
log
@Updated.
@
text
@a34 8
Use hash tables (even broken ones) for TABU check. (maybe)
Update: Cook et. al's Concorde is released.  It uses a conservative test:
hash function is h(u,v) = u xor v.  It doesn't resolve collisions with
chains.  It just answers ``present'' possibly too many times.  Simple,
effective, and mostly right.   But IIRC, the splay tree dictionary 
code uses no more than 6% of runtime, and it is precise.


d178 16
@


1.2
log
@Many items are done.
Some new items arise from discussion with DSJ about his team's implementation.
@
text
@d7 1
a7 14
Right now I do all possibilites for t6 t7 t8 when t1 through t6 is not
a valid 3-change.  JBMR don't: they do only the first valid one (feasibile
and cumgain).  See Johnson and McGeoch chapter, page 257, first full
paragraph.  So my code does more work than theirs, potentially.  I must
fix that with a compile-time option.

fix tspreorder so it works on all edge types (can't reorder upper row matrices
right now...)  Maybe use a fixed-up TSP.pm.  
Update: I'm fixing up TSP.pm.  It is functional enough to create a simple
tsplib2rothberg.pl
For multiple runs, DSJ uses randomized construction heuristics.  See
email from him late July 1998.

find out that fscking GEO distance function.  Check the reference
d28 4
d46 10
d73 18
@


1.1
log
@Initial revision
@
text
@a0 4

Short term (pre-proposal):
--------------------------

d4 8
d14 5
a18 24
right now...)  Maybe use a fixed-up TSP.pm.

find out that fscking GEO distance function.

write a perl script to combine results into a latex table.

extend expt.pl to allow for clones (perhaps parameter inside expt.data)

graft held-karp code onto lk, or write a script to get its output and
	dump it into an answer database.
	Integrate
		prim.w
		hk.w
		ascend.w
		ee.w
		branch.w
		kruskal.w
		upper.w
	Namespace clean:
		prim
	Sequential only:
		prim
	
	
d20 2
a21 7


------
ILK for matching.
	Done.  match.w version 1.12
	Iterating LK for matching doesn't seem to improves solutions.  But it
	*does* take longer.... :-)
a26 7
Adapt match for graphs with odd number of vertices (see. DIMACS1)

Dust off HK code from 1994.
	Done.  It works with read, error, memory as in LK.
	Now integrate it with lk?
	Add better option handling.

d29 2
d34 1
a37 2
Release the code as lk-0.9.0.

a40 2
Release the code as lk-1.0.0.

d42 1
d45 5
a65 6
Check the distribution on IRIX.  
	Use the native C compiler on IRIX.  
	(CC=cc ./configure; also, make sure we aren't using COFF)

Check the distribution on cygwin32.  
	(I get an internal compiler error with beta 18.  Did not investigate.)
d110 57
@