lkconfig.h,v

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

head	1.20;
access;
symbols
	zero-five-zero:1.20
	zero-four-seventeen:1.18
	zero-four-ten:1.14
	zero-four-nine:1.14
	zero-four-eight:1.13
	zero-four-five:1.12
	zero-four-zero:1.11;
locks
	neto:1.20; strict;
comment	@ * @;


1.20
date	99.01.14.17.34.47;	author neto;	state Exp;
branches;
next	1.19;

1.19
date	98.12.05.22.38.32;	author neto;	state Exp;
branches;
next	1.18;

1.18
date	98.10.17.22.06.37;	author neto;	state Exp;
branches;
next	1.17;

1.17
date	98.10.16.20.45.32;	author neto;	state Exp;
branches;
next	1.16;

1.16
date	98.10.02.19.14.35;	author neto;	state Exp;
branches;
next	1.15;

1.15
date	98.08.28.16.43.13;	author neto;	state Exp;
branches;
next	1.14;

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

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

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

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

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

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

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

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

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

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

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

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

1.2
date	97.05.16.15.14.54;	author neto;	state Exp;
branches;
next	;


desc
@Compile-time algorithm configuration options for LK.
@


1.20
log
@Added MATCH REPORT DEPTHS
Default is 1, and changed the default for JBMR REPORT DEPTHS to 1
@
text
@/* lkconfig.h 
 *
 * Compile-time options for the program LK.  
 *
 * vi: set tabstop=4 shiftwidth=4:
 * 
 * $Id: lkconfig.h,v 1.19 1998/12/05 22:38:32 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
 */

#undef LENGTH_DOUBLE
#undef LENGTH_FLOAT
#define 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.
 *
 * I plan to implement an automatic switch from linear to splay when the
 * probe gets deep enough.
 *
 * Default:
	#undef TABU_LINEAR
	#undef TABU_SPLAY
	#define TABU_HASH
 */

#undef TABU_LINEAR
#undef TABU_SPLAY
#define 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
 */

#undef KD_NO_HIDDEN_BIT


/* Define KD_NO_HIDDEN_RNN_TEST to turn off the testing the hidden bit
 * before recursing in E2_rnn.  This is less drastic than removing hidden
 * bits altogether (see KD_NO_HIDDEN_BIT), but it still doesn't save time.
 *
 * Default:
	#undef KD_NO_HIDDEN_RNN_TEST 
 */

#undef KD_NO_HIDDEN_RNN_TEST 


/***************************************************************************
 * These options select options for repeatability -- good for experiments.
 **************************************************************************/

/* Define QSORT_DETERMINATE to make sorting stable, i.e. so that we
 * preserve the order of objects that compare as equal.  Also consider
 * command-line option -S dsort (which substitutes Bentley and McIlroy's
 * deterministic sorting routine in place of the qsort routine from the
 * system's C library.
 *
 * Turn this option on only if you want to ensure repeatable results, both
 * across runs and across systems.  For repeatable results across systems,
 * you must also use -S dsort.
 *
 * Default:
	#undef QSORT_DETERMINATE
 */
#undef QSORT_DETERMINATE


/* Define CITY_ORDER_INVARIANT to ensure that computations do not depend
 * on the initial ordering of the cities.  This is for repeatability.
 * This does not work yet.  (Faith Fich's suggestion of looking at
 * statistical behaviour under input randomization may be good enough.)
 *
 * Default:
	#undef CITY_ORDER_INVARIANT
 */

#undef CITY_ORDER_INVARIANT


/***************************************************************************
 * These options control in some way the amount of output generated.
 **************************************************************************/

/* Define LK_SHOW_AFTER_SFC to output the cities graphically (in
 * PostScript) after sorting them according to Moore's version of Hilbert's
 * space-filling curve.  The output is generated only if the -p
 * (--postscript) command-line option is used to request PostScript output.
 *
 * Default:
	#undef LK_SHOW_AFTER_SFC
 */

#undef LK_SHOW_AFTER_SFC


/* Define KD_SHOW_KDTREE to output the partitioning used for the k-d tree.
 * The output is made graphically in PostScript, and only if the -p
 * (--postscript) option is used.
 *
 * Default:
	#undef KD_SHOW_KDTREE
 */

#undef KD_SHOW_KDTREE


/* Define KD_ALLOW_VERBOSE to turn on debugging output for module KDTREE,
 *  subject to the verbose command line option.
 * 
 * Default:
	#undef KD_ALLOW_VERBOSE
 */

#undef KD_ALLOW_VERBOSE


/* Define JBMR_REPORT_DEPTHS to show how deep tabu probing goes, and how
 * deep actually improving moves go.  These are platform-independent
 * statistics of work done by the tabu search algorithm. This is not
 * affected by the value of JBMR_MAX_VERBOSE.
 *
 * Default:
	#define JBMR_REPORT_DEPTHS 1
 */

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


/* Define MATCH_REPORT_DEPTHS is analogous to JBMR_REPORT_DEPTHS,
 * but affects the minimum weight perfect matching code instead of 
 * the TSP code.
 *
 * Default:
	#define MATCH_REPORT_DEPTHS 1
 */

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


/* Define JBMR_MAX_VERBOSE to determine how much verbose output code gets
 * compiled into the LK optimization code for the TSP (i.e. in module JBMR).
 * The level of detail actually output depends on this value and the values
 * given to the -v or --verbose command-line options.  
 *
 * If undefined, then there is no runtime overhead due to verbose output 
 * code, i.e., checks against variable |verbose| are not even compiled into 
 * the code.
 *
 * Default:
	#define JBMR_MAX_VERBOSE 45
 */

#if !defined(JBMR_MAX_VERBOSE)