\documentstyle[11pt]{article} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{observation}[theorem]{Observation} \newtheorem{example}{Example}[section] \title{ Needed: An Empirical Science of Algorithms \thanks{ Partially supported by ONR grant N00014-92-J-1028. } } \author{ {\sc J. N. Hooker}\\ {\small Graduate School of Industrial Administration}\\ {\small Carnegie Mellon University, Pittsburgh, PA 15213 USA}\\ } \date{January 1993} \begin{document} \maketitle \begin{abstract} Deductive algorithmic science has reached a high level of sophistication, but its worst-case and average-case results seldom tell us how well an algorithm is actually going to work in practice. I argue that an empirical science of algorithms is a viable alternative. I respond to misgivings about an empirical approach, including the prevalent notion that only a deductive treatment can be ``theoretical'' or sophisticated. NP-completeness theory, for instance, is interesting partly because it has significant, if unacknowledged, empirical content. An empirical approach involves more than rigorous design of computational tests and statistical analysis of the results, although these are important. It involves the invention of empirically-based explanatory theories. I give a simple example for tabu search and suggest some more imaginative possibilities. \end{abstract} \section{Introduction} There are two ways to study the performance of algorithms. One is analytical and relies on the methods of deductive mathematics. The other is empirical and uses computational experiments. Only the first approach has developed into a science, and I believe that many researchers and practitioners feel, deep down at least, that this science is inadequate to its task. True, many brilliant results have been proved regarding the worst-case or average-case complexity of algorithms. A number of hard-won bounds have been derived on the quality of the solution delivered by inexact algorithms, both in the worst case and in the average case. But these results do not usually tell us how an algorithm is actually going to work on practical problems, or why. The complexity results are asymptotic or apply to a worst case that seldom occurs. The average-case results presuppose a probability distribution over randomly generated problems that is typically unreflective of reality. Furthermore, results of either kind are usually obtained for the simplest kinds of algorithms. The complex algorithms typically used in practice, not to mention the all-important tricks that are engineered into commercial codes, are currently beyond the reach of deductive algorithmic science. A mathematical breakthrough cannot be ruled out. Someone may invent powerful new methods that can answer algorithmic questions that clever researchers can now only chip away at. But in the meantime, the theorems seem harder and harder to prove. After years of intense effort, we still find ourselves making very strong and therefore unrealistic assumptions to get results. The only alternative on the horizon seems to be computational testing. My thesis is that the empirical approach is a viable alternative that should be pursued more consciously and more rigorously. In other words, we should try to build an empirical science of algorithms. Computational experiments are already widely reported in scholarly publications. But these efforts fall short of science on several levels. To begin with, the testing is usually quite informal, at least in the OR literature. One occasionally sees tests conducted according to the principles of experimental design, or results analyzed using rigorous statistical methods. But only occasionally. Not even minimal standards of reproducibility are observed by most authors. Crowder, Dembo and Mulvey (1978) found the state of affairs sorry enough that they would not go so far as to recommend reproducibility by others, but only that an investigator be able to reproduce {\em his or her own} results. It is symptomatic of the situation that, in OR and computer science, one cannot publish reports that an algorithm does {\em not} perform well in computational tests. Negative results are as important as positive results and are routinely reported in other empirical sciences. But the OR and computer science communities do not judge the publishability of results, whether they be positive or negative, primarily on the basis of their value as empirical knowledge. Positive results are published because they are a practical selling point for the ``theoretical'' work that occupies the first 90\% of the article. Negative results are relegated to obscurity because they do {\em not} demonstrate the applicability of the ``theory.'' We recognize their importance on an unofficial level but must rely on grapevines and email to find out about them. \section{Advantages of an Empirical Science} An empirical science of algorithms would immediately sidestep several of the problems that beset a purely deductive science. \begin{itemize} \item It does not rely on proving hard worst-case and average-case theorems. \item Unlike worst-case analysis, it can focus on typical problems. \item Unlike average-case analysis, it need not restrict itself to a simple and unrealistic distribution of random problems. \item It can finesse the issue of {\em characterizing} a ``typical'' class of problems. \end{itemize} The last point deserves expansion. We want to know the performance of an algorithm on ``typical'' problems, but we often do not know how to characterize typical problems. So even if we could carry out average-case analysis for any problem distribution we wish, we would be unsure about what distribution to use. Empirical science is equally stymied by this problem if it approaches it in the usual way. The usual way is to collect a set of ``benchmark'' problems and compare algorithmic results on them. But any choice of problems is open to the criticism that it is unrepresentative. There is another way, however. One can investigate {\em how algorithmic performance depends on problem characteristics}. The issue of problem choice therefore becomes one of experimental design. Rather than agonize over whether a problem set is representative of practice, one picks problems that vary along one or more parameters. Many investigators already do this informally, as when exploring the effect of matrix density on algorithmic performance. Over time, one may discover the important characteristics and learn to predict how an algorithm will perform on a given problem class. \section{Empirical Science Is Theoretical} Let us next dispose of the notion that empirical work in algorithms is somehow the opposite of ``theory.'' True, in its presently impoverished state it consists of little more than the tables of computational results we often see on the last page of journal articles. But it can be every bit as theoretical as, say, complexity theory. In its early stages, an empirical study of an algorithm might well involve nothing more than running a few tests to see what happens. But after a while one develops an informed hunch about what is likely to affect performance. This is a {\it hypothesis}. The hypothesis is then tested empirically, using time-honored techniques of experimental design and statistical analysis. Eventually one may put together a unifying and coherent picture that appears to explain why certain factors are important. This is a {\it theory}. From the theory one can deduce consequences that can be put to the test. This sort of development is a well-trod path in empirical sciences. It shows that theory, far from being antithetical to empirical science, is its culmination. Anyone who thinks that empirical science is nontheoretical should take a look at quantum electrodynamics. A source of confusion is that the word `empirical' has one sense in which it refers to something based purely on observation without theoretical depth. But I use the word in its classical sense, which simply means something that is ultimately answerable to experience. As for `theory,' it is again symptomatic that, within the OR and computer science communities, the word often connotes a deductive science consisting solely of theorems and proofs. It is time we broke out of this mindset. I do not mean to say that theorems and proofs play no role in empirical science. To deduce a consequence of a theory for testing is in a sense to prove a theorem. But unlike the situation in deductive science, the ``theorem'' cannot be accepted as true unless it squares with observation. How do I know that deducing the consequences of an empirical theory of algorithms will not be as hard as proving worst-case and average-case results? I do not. Deducing consequences of empirical theories is sometimes very hard. It took many years to derive the possibility of black holes from Einstein's gravitational field equations. But since we know that theorem-proving in a deductive science of algorithms is hard, it behooves us to give empirical science a chance. \section{Why the Resistance to Empiricism?} If an empirical science of algorithms is so viable an alternative, why has it not caught on? Why do many people actively resist the idea? Why are some computer scientists positively outraged by it? I can identify several reasons, none of which I think are legitimate. I will begin with the most frivolous and progress to the most serious. One practical reason researchers do not invest more energy in rigorous empirical work is that it is often considered lowbrow or unsophisticated. It is hard or impossible to get a purely empirical paper published in some prestigious journals. Behind this, in part, is a lack of standards for distinguishing high-quality empirical work. Referees are untrained in empirical science and do not know how to judge work in it. One remedy is for journal editors to start taking empirical papers seriously. They should seek out referees who have done rigorous empirical studies (there are a few; see below). Refereeing standards will evolve, particularly as the empirical science develops. Another objection to empirical work is that it is inherently irreproducible. Everyone knows that the performance of an algorithm (e.g., number of elementary operations required) can vary by an order of magnitude with the details of implementation. The data structures, coding style, compiler, machine, etc., all matter. How can testing show an algorithm to be efficient or inefficient when one can only test the algorithm-{\it cum}-implementation? The problem is one of distinguishing the phenomenon (here, the algorithm) from the apparatus used to investigate it (here, the data structures, code, etc.). This is an old problem in empirical science that is attacked by {\em developing a science that governs the apparatus}. An astronomer, for example, can test a theory regarding the brightness of stars by photographing them through a telescope. Another astronomer may get different results on a different night. But their results can be reconciled if they understand how atmospheric conditions and the construction of their telescopes affect the photograph. Similarly, we need an understanding of how data structures and coding practices affect our observations of algorithmic behavior. We already have some nonempirical understanding of this sort, but empirical investigation can augment it. Perhaps this is a little too facile, however, since whereas it is easy to distinguish stellar brightness from atmospheric interference, etc., it is not so easy to distinguish algorithms from the data structures and code that embody them. Perhaps an algorithm is not really well specified until implemented. Or to put it differently, the very act of implementing (i.e., observing) an algorithm alters the algorithm being observed. It is not so obvious that deductive science is better positioned to deal with this problem than empirical science. But this aside, it is again a problem that empirical science has dealt with. In quantum physics, the method of observation is notoriously inseparable from the phenomenon measured. Admittedly this poses a profound conundrum that by many accounts remains unresolved. But quantum physics has enjoyed spectacular success, both in theoretical power and in practical application, despite it. Perhaps there is a role for an ``uncertainty principle'' in algorithmic science. In any event, I think we can agree that this empirical endeavor is beginning to look less and less like a humdrum affair of tabulating CPU times. \section{The Main Objection} The main source of uneasiness over an empirical approach, however, seems to run deeper. It is too much like verifying that opposite interior angles are equal by measuring them with a protractor. The behavior of an algorithm over any finite period of time is in principle deducible, using formal methods, from a statement of an algorithm. It seems fundamentally wrong-headed to use empirical methods to study what is essentially a formal system. I have two responses to this objection. One is that the natural phenomena we study very successfully with empirical methods may themselves be deducible in a formal system. In fact this was the prevailing view in the early days of modern science. Such luminaries as Descartes, Leibniz, and Newton believed, and Kant allowed for the possibility, that physics could in principle be studied with the same deductive methods as geometry, if only we had the intelligence to do it. It is only our dim-wittedness that obliges us to use empirical observation as a crutch. Even some recent physicists have suggested, off the record at least, that this view deserves reconsideration, partly because it is hard to imagine how the numerical values of fundamental physical constants could be explained except in the manner we explain how $\pi$ has the value it does. I do not claim that nature reflects an underlying formal system. My point is that many of the founders of modern science saw (and some recent scientists see) nothing contradictory or wrong-headed about studying a formal system with empirical methods. So I think the onus is on those who see impropriety to defend their view. My second response is more substantive. To insist on studying algorithms at the level of a formal system may commit the fallacy of reductionism: the fallacy that one can and should explain a phenomenon by reducing it to its ultimate constituents. Consider the theory of plate techtonics, which explains the formation of the continents by the way pieces of the earth's crust float on magma. One might ``explain'' the same phenomenon by reducing it to quantum physics, perhaps by formulating Schr\"{o}dinger's equation for every atom in the earth and showing that our present topography corresponds to the simultaneous solution of the equations. But this approach presents two difficulties. There is the obvious practical problem that no mortal can carry it out. But even if we could do it, even if we could {\em deduce} earth's topography, this is no way to {\em explain} it. We would get a massive computer printout containing billions of numbers, with no insight whatever as to {\em why} continents look the way they do. Geologists, meanwhile, point out that the eastern coast of the Americas is shaped like the western coasts of Europe and Africa because they once collided, etc., and it all starts to make sense. The key to explanation is obviously finding {\em the right level of analysis}---the level of floating plates rather than swarming atoms. Perhaps investigating the behavior of algorithms with formal methods is like applying quantum physics to geology. Even if one can in principle {\em deduce} what the algorithms are going to do, it is beyond human powers to do so, and even if we did, we would not {\em understand why} they behave as they do. Quantum mechanics is not a deductive science in the way that complexity theory is, but the situations seem otherwise analogous. (To take an analogy that does involve deductive science, one can ask: does the computer-implemented proof of the 4-color map lemma, granting that it {\em proves} the lemma, {\em explain} why the lemma is true?) \section{Steps in the Right Direction} The OR and computer science communities have taken two steps toward an empirical science of algorithms. Both are helpful, but both fall short of the goal. A Ph.D. thesis by Catherine McGeoch (1986) nicely surveys much of the research in this area. One step involves statistical methodology. A few researchers have used rigorous methods of experimental design to concoct computational tests and statistical analysis to evaluate the results, and there seems to be a rising level of interest in these matters. One of the first efforts in the OR literature was a sophisticated application of experimental design principles by Lin and Rardin (1980). Golden and Stewart (1985), and more recently Amini and Racer (1992), used rigorous statistical methods to analyze test results. Eddy (1977) and Hart (1983) used less elaborate analyses. Barton (1987) discussed experimental design for comparing optimization procedures. Crowder, Dembo and Mulvey (1978) as well as Hoaglin and Andrews (1975) addressed the issue of computational reporting. This movement toward rigorous methods is commendable, but it is only one ingredient of empirical science. Another key ingredient is the development of empirically-based theories that can be submitted to rigorous testing. A second encouraging step toward an empirical science is the {\em heuristic} use of experimentation. By this I mean the practice of using experiments to suggest hypotheses about the behavior of algorithms. Bentley {\it et al.} (1983,1984) took this approach to bin packing algorithms and discovered theorems later proved by Shor (1984). Manacher and Zobrist (1983) took a similar approach to some matching problems, McGeoch (1986) to sorting, and Rivest (1976) to self-organizing search. Varga (1990) discussed the use of experimentation in mathematics generally. We all know that mathematicians have long used heuristic experimentation, but the positive aspect of the recent trend is that we are owning up to it in print. It falls short of empirical science because experimentation is used only to suggest theorems that are later proved. In empirical science, experimentation not only suggests hypotheses but is the basis on which they are accepted or rejected. Yet heuristic mathematicians perform a valuable service by bringing mathematical experimentation out of the closet. \section{Empirical Science in Disguise} The empirical approach may seem more acceptable if we note the extent to which it has already crept into what is ostensibly our deductive science of algorithms. This has occurred in nothing less than one of the crowning achievements of ``theoretical'' (i.e., deductive) computer science: NP-completeness theory. NP-completeness theory is, strictly speaking, a theory of problems rather than algorithms. But it bears importantly on algorithms because no known algorithm can solve any NP-complete problem in polynomial time. The reader can consult Garey and Johnson (1979) for an introduction to NP-completeness theory, but I will state the essentials very briefly. Roughly speaking, a problem belongs to the class NP if it is possible to {\em verify}, in polynomial time, that a given solution for it is in fact a solution. (``Polynomial time'' means that the time required increases no faster than some polynomial function of the problem size, which is measured by the number of bits needed to represent the problem in a computer.) We know that at least some of the problems in NP can in fact be {\em solved} in polynomial time. These comprise the class P, which is a subset of NP. A large variety of apparently hard problems also belong to NP. A class of problems in NP is NP-complete if a polynomial-time algorithm for solving them (supposing such an algorithm existed) could be used to solve {\em any} problem in NP in polynomial time. Since no such algorithm has been found, an NP-complete problem class is regarded as {\em characteristically} hard in some sense, although everybody recognizes that it may contain easy problems among the hard ones. The empirical content of NP-completeness theory becomes evident when we note that any problem class in NP that {\em contains} an NP-complete class is itself NP-complete on that basis alone. Consider, for instance the famous class TSP of traveling salesman problems. The standard proof of NP-completeness for TSP shows that one could solve any satisfiability problem in polynomial time if he could solve any problem in a certain subset $T_0$ of TSP in polynomial time. Since the class of satisfiability problems is NP-complete, it follows that TSP is NP-complete. What interests us here is that this argument shows equally well that $T_0$ is NP-complete, where $T_0$ is a very small subset of very special traveling salesman problems. Let us grant that this shows that the problems in $T_0$ are ``characteristically hard'' in some sense. But on what ground do we infer that the much larger superset TSP is a class of ``hard'' problems? Recall that {\em any} class of problems in NP that contains $T_0$ is {\it ipso facto} NP-complete. Consider the class P$'$ that consists of all the problems in $P$ (i.e., all problems soluble in polynomial time) and the very special traveling salesman problems in $T_0$. P$'$ is no less NP-complete than TSP, because it contains $T_0$. But it seems odd to say that the problems in P$'$ are characteristically hard, since they include all the easy problems in the world. What, then, gives us the right to say that TSP consists of characteristically hard problems? Perhaps it is the fact that all the problems in TSP share a structural similarity with the problems in $T_0$. But this only postpones the question: on what ground do we say that the TSP structure, rather than some other structure shared by problems in $T_0$, makes $T_0$ hard? I suggest that we regard TSP as a hard class because {\em we in fact find problems in TSP to be hard in practice}. Again, we acknowledge all along that TSP contains many easy problems. But when one generates larger and larger TSP problems according to almost any reasonable scheme that is not designed to produce easy problems, their difficulty tends to explode. It is this fact, I submit, that justifies our saying that TSP contains characteristically hard problems. It the fact that, to a large degree, makes the NP-completeness result for TSP {\em interesting}. And it is an empirical fact. TSP is what philosophers of science sometimes call a ``natural kind.'' To use Goodman's (1979) well-known example, let us define `grue' to mean `green until 2000 A.D. and blue thereafter.' Observing a large number of trees justifies a generalization that most trees are green. But the same observation, even if it takes place before 2000, fails to justify a generalization that most trees are grue. The reason is that `green' is a natural kind where trees are concerned and `grue' is not. We have found empirically that properties like green relate to the order of nature in a way that properties like grue do not. Similarly, TSP appears to be a natural kind where problem difficulty is concerned, whereas P$'$ is not. Again, we found out about this empirically. \section{An Example.} To make my proposal for an empirical science of algorithms more concrete, I will conclude by describing one example of what an empirical theory might be like. I will deduce a consequence of the theory that can be submitted to empirical testing. I will make no attempt, however, to illustrate experimental design techniques or report the results of experiments. These tasks are reserved for subsequent papers. My simple theory is intended to help explain the behavior of tabu heuristics. Tabu heuristics have met with considerable success in solving hard combinatorial problems, but there is little or no theoretical understanding of when or why they work well. For concreteness I will discuss a rudimentary tabu heuristic for the knapsack problem. See Glover (1989,1990a,1990b) for a thorough discussion of tabu heuristics. The knapsack problem begins with a collection of items, each having a specified weight and value. The object is to put some of the items into a knapsack so as to maximize value subject to a weight limit. Any choice of items within the weight limit is a {\em solution}, and we want to find the best solution we can. The tabu heuristic begins with an arbitrary solution. In each iteration, it goes to the best solution that is {\em adjacent} to the current solution. A solution is adjacent to another if it results from removing an item from the knapsack, or adding an item to it. The best adjacent solution may be worse than the current one, but the tabu heuristic goes to it anyway. The process is repeated a predetermined number of iterations, keeping track of the best solution found so far. A {\em tabu list} prevents the heuristic from cycling through the same solutions over and over. It is a list of the {\em moves} that have been made recently, where a move is the removal or addition of a specified item from the knapsack. Any move that reverses a move on the list is ``tabu'' (more often spelled `taboo' in other contexts), meaning that it cannot be used. For instance, if the removal of item 1 is listed, item 1 cannot be restored to the knapsack. The oldest moves are dropped to maintain the list at a fixed length that is adjusted by trial and error. If the list is too short, the heuristic may cycle, and if it is too long, it may reach a point where all moves are tabu and terminate prematurely. In discussing my model of tabu search, it is more convenient to speak of minimizing the ``cost'' of the knapsack contents, rather than maximizing the value. The cost can be regarded as the negation of the value. Consider a network whose nodes are solutions and whose arcs connect adjacent solutions. Since adjacency is symmetric in the case of the knapsack problem, we can suppose the network is undirected. The motivating idea for the model is to view the nodes as points on an undulating landscape, so that nodes connected by arcs are ``close'' in some sense. The elevation of each node is the cost of the corresponding solution, and the object is to find a point of low elevation. The tabu search operates by finding a steepest possible downhill hill path until the bottom of a basin (a local minimum) is reached. At this point the heuristic ``climbs out of'' the basin until it reaches the ``rim,'' whereupon it descends into another basin, on the chance it contains a lower point. The tabu list is supposed to prevent the search from falling back down into a basin before it climbs out. This visualization is vague because ``close'' is not well defined, and it if it were there would probably be no reasonable way to embed the nodes in any two-dimensional surface. But it motivates concepts that can be rigorously defined as follows. Let a local minimum be any node whose adjacent solutions are no better than it. A local search is a downhill path: a sequence of nodes, each of which i) is a best solution adjacent to the previous node, and ii) is at least as good as the previous node. The basin surrounding a local minimum is the set of nodes from which some local search leads to the local minimum. The rim of the basin is the set of its nodes that are adjacent to at least one node outside the basin. Tabu search can be interpreted as a form of implicit enumeration. Once the search descends into a basin and finds a local minimum, there is no point in visiting any of the other nodes in the basin (except to climb out again). The unvisited nodes are implicitly enumerated. My theory states that the performance of the heuristic can be explained by the efficiency of this implicit enumeration. If the heuristic visits only a small fraction of the nodes in a basin, it should in effect enumerate a large number of solutions in a short time and therefore perform well. We can take the length of a path in the network to be the number of nodes on it. The distance between two nodes is the length of a shortest path between them. Given these definitions, we should expect the tabu heuristic to visit a small fraction of the nodes in a basin when the number of nodes in the basin is large relative to the distance from the rim to the local minimum. Let this distance be the radius of the basin, defined as the mean distance from rim nodes to the local minimum. (If there are multiple local minima, we can take the one resulting in the smallest mean.) We can now propose a hypothesis, to be tested empirically: \begin{itemize} \item Tabu search works better when the ratio of average basin size to average radius (which we call the ``search ratio'') is large. \end{itemize} Intuitively we can think of the search ratio as being large when the network is embedded in a higher dimensional space, since the volume-to-radius ratio for spheres and other bodies increases as the number of dimensions increases (when the radius is greater than one). So tabu search should work better in higher-dimensional spaces, albeit this idea of dimensionality is not formally part of the model. This little theory is useful only if conjoined with a theory of how the basin characteristics depend on the problem type, so that one can predict performance for a particular problem. I leave the formulation of such a theory to another occasion. The theory also leaves much room for elaboration. Problem ``landscapes'' have many features other than the size and diameter of basins, and these may help explain tabu performance. The landscape may consist essentially of a plain that is pockmarked with small basins, or of large hills and valleys that are similarly indented. Tabu search may find better solutions on the latter type of manifold because it tends to spill out of each basin it visits into a lower one. It is an interesting challenge to formulate operational definitions of these intuitive ideas. Other approaches are possible. Empirical theories often find it useful to postulate an internal structure for the objects under investigation, as Rutherford suggested an orbital model of the atom to explain its scattering of Xrays. Perhaps this can be done for algorithms. The postulated structure, however, need have no relation to the sequence of steps or subroutines in a statement of the algorithm. The steps pertain to a {\em formal} explanation of its behavior, which we are trying to avoid here. In fact it may be good policy to forget all about the formal structure of the algorithm, to free one's imagination to invent empirically-inspired explanations. A biological level of explanation, for instance, may be useful, since algorithms can be viewed as ``organisms'' that act upon their environment. This is not as far-fetched as it sounds. Farmer and Belin (1990) argue that computer viruses (which are essentially algorithms) possess most and conceivably all of the formal characteristics of living organisms. It is hard to be more specific, since one cannot propose interesting and plausible empirical theories on the first day of work. Empirical science takes time to build. I suggest we get started. \section{References} \begin{description} \item {\sc Amini, M. M., and M. Racer.} 1992. A variable-depth-search heuristic for the generalized assignment problem, working paper, Civil Engineering, Memphis State University, Memphis, TN 38152 USA. \item {\sc Barton, R. R.}. 1987. Testing strategies for simulation optimization, {\it Proceedings of the 1987 Winter Simulation Conference}, 391-401. \item {\sc Bentley, J. L., D. S. Johnson, F. T. Leighton and C. C. McGeoch.} 1983. An experimental study of bin packing, in {\it Proceedings, 21st Allerton Conference on Communications, Control and Computing}, University of Illinois, Urbana, IL, USA. \item {\sc Bentley, J. L., D. S. Johnson, F. T. Leighton, C. C. McGeoch and L. A. McGeoch.} 1984. Some unexpected expected-behavior results for bin packing, in {\it Proceedings, 16th Symposium on Theory of Computation}, ACM. \item {\sc Crowder, H. P., R. S. Dembo and J. M. Mulvey.} 1978. Reporting computational experiments in mathematical programming, {\it Mathematical Programming} {\bf 15}, 316-329. \item {\sc Eddy, W. F.} 1977. A new convex hull algorithm for planar sets, {\it ACM Transactions on Mathematical Software} {\bf 3} 398-402. \item {\sc Farmer, J. D., and A. d'A. Belin.} 1990. Artificial life: The coming evolution, manuscript 90-003, Santa Fe Institute, 1120 Canyon Rd., Sante Fe, NM 87501 USA. \item {\sc Garey, M. R., and D. S. Johnson.} 1979. {\it Computers and Intractability: A Guide to the Theory of NP-Completeness}, W. H. Freeman, San Francisco. \item {\sc Glover, F.} 1989. Tabu search---Part I, {\it ORSA Journal on Computing} {\bf 1}, 190-206. \item {\sc Glover, F.} 1990a. Tabu search---Part II, {\it ORSA Journal on Computing} {\bf 2}, 4-32. \item {\sc Glover, F.} 1990b. Tabu search: A tutorial, {\it Interfaces} {\bf 20}, 74-94. \item {\sc Golden, B. L., and W. R. Stewart.} 1985. Empirical analysis of heuristics, in Lawler, Lenstra, Rinnooy Kan and Schmoys, eds., {\it The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization}, Wiley. \item {\sc Goodman, N.} 1965. {\it Fact, Fiction and Forecast, 2nd ed.}, Bobbs-Merrill, Indianapolis. \item {\sc Hart, R. R.} 1983. The average height of binary search trees, masters thesis, University of California at Irvine. \item {\sc Hoaglin, D. C., and D. F. Andrews.} 1975. The reporting of computation-based results in statistics, {\it The American Statistician} {\bf 29}, 122-126. \item {\sc Kant, I.} 1929. {\it Critique of Pure Reason}, transl. N. Kemp Smith, St. Martin's Press. \item {\sc Lin, B. W., and R. L. Rardin.} 1980. Controlled experimental design for statistical comparison of integer programming algorithms, {\it Management Science}, 1258-1271. \item {\sc Manacher, G. K., and A. L. Zobrist.} 1983. Probabilistic methods with heaps for fast-average-case greedy algorithms, in F. P. Preparata, ed., {\it Advances in Computing Research: Computational Geometry}, JAI Press, Greenwich, CT, 261-278. \item {\sc McGeoch, C. C.} 1986. Experimental analysis of algorithms, Ph.D. thesis, CMU-CS-87-124, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213 USA. \item {\sc Rivest, R.} 1976. On self-organizing sequential search heuristics, {\it Communications of the ACM} {\bf 19}, 63-67. \item {\sc Shor, P. W.} 1984. The average-case analysis of some on-line algorithms for bin packing, in {\it Proceedings, 25th Symposium on Foundations of Computer Science}, IEEE, 193-200. \item {\sc Tenenbaum, A.} 1978. Simulations of dynamic sequential search algorithms, {\it Communications of the ACM} {\bf 21}, 790-791. \item {\sc Varga, R. S.} 1990. {\it Scientific Computation on Mathematical Problems and Conjectures,} Regional Conference Series in Applied Mathematics, v. 60, SIAM. \end{description} \end{document}