/* 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 */