lkconfig.h

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

/* lkconfig.h 
 *
 * Compile-time options for the program LK.  
 *
 * vi: set tabstop=4 shiftwidth=4:
 * 
 * $Id: lkconfig.h,v 1.20 1999/01/14 17:34:47 neto Exp neto $
 * 
 *    Copyright (C) 1996, 1997 David Neto
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2, or (at your option)
 *    any later version.
 *
 *    This program is distributed in the hope that it will be useful, but
 *    WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    General Public License for more details.
 * 
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 *    USA.
 * 
 * 
 * This file sets the compile-time options for the program LK.  Behaviour
 * or availability of certain parts of the program LK are enabled or
 * modified here by defining C preprocessor symbols.  The defaults are
 * given in comments.
 * 
 * Warning!  This file is *not* generated by a web file.  It is a plain .h
 * header file so that the user who doesn't have ctangle installed (tsk,
 * tsk!) has the ability to change the configuration options for the
 * program LK.  That said, I've tried to make this file as self-documenting
 * as possible without the power of CWEB or TeX.
 * 
 * Some of the options from this file depend on definitions in config.h,
 * the package-wide configuration header file.  That file is generated
 * automatically at configuration time, and knows a lot about the target
 * system.  So files that include this header file should include
 * <config.h> first.  (See the Autoconf manual for why one should use
 * angle brackets (#include <config.h>) instead of ordinary quotes
 * (#include "config.h").)
 * 
 * Generally speaking, the first ``word'' in a symbol name corresponds to
 * the source file that it affects.  For example, ERROR_NO_CHECK controls
 * the behaviour of part of the error module in file error.w.  Sometimes
 * the name is abbreviated, e.g. KD_CHECK_VERBOSE controls behaviour of the
 * k-dimensional trees defined in kdtree.w.
 * 
 *
 * This file is divided into sections, most important first.  They are:
 *  Options to control algorithmic parameters.
 *  Options to control precision and accuracy.
 *  Options that may have an impact on performance, but not on correctness.
 *  Options to control the amount of memory used.
 *  Options to select options for repeatability -- good for experiments.
 *  Options to control in some way the amount of output generated.
 *  Options to control how much checking is done.
 * 
 * 
 */


/***************************************************************************
 * These options control algorithmic parameters.
 **************************************************************************/

/* We need to select which tabu rules are in effect.  Exactly one of
 * TABU_JBMR or TABU_Papadimitriou must be selected.  
 * (Only TABU_JBMR is implemented!!!)
 * 
 * TABU_JBMR selects the rule ``Never delete an added edge''.
 * TABU_Papadimitriou selects the rule ``Never add a deleted edge''.
 *
 * Papadimitriou's rule enables LK to solve a PLS-complete problem, but as
 * of 1997 had not yet been studied experimentally.
 *
 * Lin and Kernighan devised and used both rules, but did not name them
 * this way.  This naming scheme is my own mnemonic.
 *
 * Default:
	#define TABU_JBMR
	#undef TABU_Papadimitriou
 */

#define TABU_JBMR
#undef TABU_Papadimitriou


/* Most of the time you want to limit the probe depth of the variable-depth 
 * search.  Use command line option --maxdepth <n> to do so.  The option
 * can only be used if JBMR_LIMIT_PROBE_DEPTH is defined.  There may be
 * an insignificant performance loss if it is defined, because there is a 
 * depth check at each step deeper in the search.  
 *
 * Default:
	#define JBMR_LIMIT_PROBE_DEPTH
 */

#define JBMR_LIMIT_PROBE_DEPTH


/* Lin and Kernighan examine the farther tour neighbour of t[7] first.
 * This switch determines whether we consider the farther neighbour of t[1]
 * first.  If the value of JBMR_FARTHER_T1_FIRST is zero, then we try
 * the tour neighbours in arbitrary order.
 * 
 * A quick experiment on dsj1000 showed that (with declustering turned on),
 * it's better to turn this on:  turned off, total run time is 395 sec,
 * tour length is 19190163 (or 2.8% above optimal); turn on, total run time
 * is 91 sec, tour length is 18870278 (or 1.1% above optimal).
 *
 * Default:
	#define JBMR_FARTHER_T1_FIRST 1
 */

#if !defined(JBMR_FARTHER_T1_FIRST)
#define JBMR_FARTHER_T1_FIRST 1
#endif


/* Johnson and colleagues use a queue for the set of ``dirty'' or
 * ``active'' cities.  (Personal communication with DSJ August 1998).
 * I presume this to mean a last-in-first-out queue.
 * Applegate, Bixby, Chvatal, and Cook's implementation of LK (in Concorde)
 * definitely uses a LIFO queue.  And they seed the queue in random order.
 * Until 1998/8/5 I've used only a splay tree keyed on city number and 
 * always withdrawn the root of the splay tree as the next candidate for
 * t1. 
 * 
 * But my code has had large variance in the running time, especially on
 * clustered instances.
 *
 * Define DIRTY_SET to be DIRTY_SET_FIFO if you want the JBMR,
 * or ABCC behaviour.  Define it to be DIRTY_SET_SPLAY_ROOT if you
 * want the splay root behaviour.
 *
 * Default:
	#define DIRTY_SET DIRTY_SET_FIFO
 */

#define DIRTY_SET_FIFO 			0
#define DIRTY_SET_SPLAY_ROOT 	1

#if !defined(DIRTY_SET)
#define DIRTY_SET DIRTY_SET_FIFO
#endif



/***************************************************************************
 * These options control precision and accuracy.
 **************************************************************************/

/* We need to define a C data type for lengths.  Only one of the following
 * should be active at a time.  See length.w for more information.  
 *
 * Type long long is not pure ANSI; it is supported by GCC and by the IRIX
 * native C compiler.  At package configuration time, symbol
 * SIZEOF_LONG_LONG is set to zero if type long long is unsupported; it is
 * set to the number of bytes in long long otherwise, usually 8.  So we
 * can allow it conditionally as follows:
 * 
 * Example:
	#if SIZEOF_LONG_LONG
	#define LENGTH_LONG_LONG
	#end
 * 
 * Default: 
	#undef  LENGTH_DOUBLE 
	#undef  LENGTH_FLOAT
	#define LENGTH_INT
	#undef  LENGTH_LONG_LONG
 */

#define LENGTH_DOUBLE
#undef LENGTH_FLOAT
#undef LENGTH_INT
#undef LENGTH_LONG_LONG

/* Should we use the math library's hypot function instead of open-coding
 * the Euclidean distance function?  Numerical analysts might argue for
 * using hypot, but it turned out to be much slower.   
 *
 * The many cost functions are defined in the READ module, read.w.
 *
 * Default: 
	#undef COST_USE_HYPOT 
 */

#undef COST_USE_HYPOT


/* JBMR_REQUIRE_JOINED_GAIN_VAR   
 *
 * If an inexact type is specified for length then by default the LK
 * optimization phase computes cumulative gains in a split variable: a
 * positive part and a negative part.  This default is safer but slower than
 * using a single cumulative gain variable.
 *
 * To force a unified variable, define the symbol
 * JBMR_REQUIRE_JOINED_GAIN_VAR.  Turn this option on if you trust summing
 * an alternating series with floating point numbers.  :)
 * (Hint: you shouldn't!)
 * 
 * However, I do use machine epsilon intelligently in cutting off the
 * search, so these alternating sums might not be such a big issue.
 *
 * Default:
	#define JBMR_REQUIRE_JOINED_GAIN_VAR
 */

#define JBMR_REQUIRE_JOINED_GAIN_VAR


/***************************************************************************
 * These options may have an impact on performance, but not on correctness.
 **************************************************************************/

/* We must determine what data structure to use for the tabu check.
 * Exactly one of TABU_LINEAR or TABU_SPLAY must be defined.
 *
 * TABU_LINEAR uses an unordered array; each check takes time linear in the
 * number of items in the array.  This is best for probes up to a depth of
 * about 50.  See also JBMR_LIMIT_PROBE_DEPTH.
 *
 * TABU_SPLAY uses a splay tree; each check takes (amortized) time
 * logarithmic in the number of items in the array, but has greater
 * overhead for smaller dictionaries.  This is better than TABU_LINEAR for
 * deeper probes.
 *
 * TABU_HASH uses hashing with chaining.  This might be the fastest of
 * them all.  (Actually, it is slightly buggy.  Johnson and McGeoch's 
 * C31k.1 instance can make it crap out.  Use TABU_LINEAR instead.
 *
 * I plan to implement an automatic switch from linear to splay when the
 * probe gets deep enough.
 *
 * Default:
	#define TABU_LINEAR
	#undef TABU_SPLAY
	#undef TABU_LINEAR
 */

#define TABU_LINEAR
#undef TABU_SPLAY
#undef TABU_HASH


/* Define KD_BUILD_SMALLEST_SEGMENT_FIRST to make the k-d tree building
 * routine build the segment with the fewest number of cities first.
 * This may or may not prevent stack overflow.  (In fact, I think a
 * seriously smart compiler is needed for this trick to prevent stack
 * overflow.
 * 
 * Default:
	#undef KD_BUILD_SMALLEST_SEGMENT_FIRST
 */

#undef KD_BUILD_SMALLEST_SEGMENT_FIRST


/* Define KD_NO_HIDDEN_BIT to remove all support for hidden bits in nodes
 * of k-d trees.  After running some experiments, it appears that the
 * reduction in bookkeeping (time and space) is more than offset by useless
 * node searches.  So the default is to not define this symbol.
 *
 * Default:
	#undef KD_NO_HIDDEN_BIT
 */