
\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} 
