The previous chapters have set forth the DDP requirements satisfaction problem 
(that is, how to attain the most goals for the lowest price) and provided a survey of the search-based software engineering field.
In this chapter, I will discuss the algorithms used to search and optimize
the space of model configurations. 

Numerous researchers have stressed the difficulties associated
with comparing radically different algorithms.
For example, Uribe and Stickel~\cite{uribe94}
doubted that it was fair to compare
algorithms that perform constraint satisfaction and no search (like binary decision diagrams) and
methods that perform search and no constraint satisfaction (like Davis-Putnam proofs). 
For this reason, model checking researchers like Holzmann
eschew comparisons of tools like SPIN~\cite{holzmann97}, which are search-based,  with tools like NuSMV~\cite{nusmv}, which are BDD-based.

Hence, I take care to only compare algorithms which are similar to 
my primary approach, KEYS. 
In terms of Gu's exhaustive optimization survey~\cite{gu97}, the algorithms that I have selected
(simulated annealing, A* and MaxWalkSat) share certain properties with KEYS and KEYS2.
They are each discrete, sequential, {\em unconstrained} algorithms
(constrained algorithms
work towards a  pre-determined number of possible solutions 
while unconstrained methods are allowed to adjust to the goal space).
These shared properties ensure that all algorithm comparisons are
appropriate.

For full source code of these techniques, please see the appendices. 

\section{Simulated Annealing}\label{sec:sa}

Simulated annealing (SA) is a classic stochastic search algorithm. It was first described in 1953~\cite{metropolis53} and refined in 1983 ~\cite{kirkpatrick83}. 
The algorithm's namesake, annealing, is a technique from metallurgy, where a material is heated,
then cooled. The heat causes the atoms in the material to 
wander randomly through different energy states and the cooling process increases the chances of finding a state with a lower energy than the starting position.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure SA
2. MITIGATIONS:= set of mitigations
3. SCORE:= score of MITIGATIONS
4. while TIME < MAX_TIME && SCORE < MIN_SCORE //minScore is a constant score (threshold)
5.    find a NEIGHBOR close to MITIGATIONS
6.    NEIGHBOR_SCORE:= score of NEIGHBOR
7.    if NEIGHBOR_SCORE > SCORE
8.        MITIGATIONS:= NEIGHBOR
9.        SCORE:= NEIGHBOR_SCORE
10.   else if prob(SCORE, NEIGHBOR_SCORE, TIME, temp(TIME, MAX_TIME)) > RANDOM)
11.       MITIGATIONS:= NEIGHBOR
12.       SCORE:= NEIGHBOR_SCORE
13.   TIME++
14. end while
15. return MITIGATIONS
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for SA}
\label{fig:simplesa}
\end{figure}

During each round, SA ``picks'' a neighboring set of mitigations. To calculate this neighbor, a function traverses the mitigation settings of the current state and randomly flips those mitigations (at a 5\% chance). 
If the neighbor has a better score, SA will move to it and set it as the current state. If no score improvement is seen, the algorithm will decide whether or not to move based on the probability function:
\begin{equation}\label{eq:ps1}
prob(w,x,y,temp(y,z)) = e^{((w-x) * \frac{y}{temp(y,z)})}
\end{equation}
\begin{equation}\label{eq:ps}
temp(y,z) = \frac{(z-y)}{z}
\end{equation}
If the value of the {\tt prob} function is greater than a randomly generated number, SA will move to that state anyways. 
This randomness is the very cornerstone of the Simulated Annealing algorithm. Initially, the ``atoms'' (current solutions) 
will take large random jumps, sometimes to even sub-optimal new solutions. These random jumps allow simulated
annealing to sample a large part of the search space, while avoiding being trapped in local minima.
Eventually,
the ``atoms'' will cool and stabilize and the search will converge to a simple hill climber.

As shown in line 4 of \fig{simplesa}, the algorithm will continue to operate until the number of tries is exhausted or a score meets the threshold requirement. 

Other uses for the simulated annealing algorithm in the search-based
software engineering field are discussed in Section \ref{sec:sarw}.

\section{MaxFunWalk (MaxWalkSat)}\label{sec:mfw}

The design of simulated annealing dates back to the 1950s. In
order to benchmark KEYS against a more state-of-the-art
algorithm, I implemented the variant of 
MaxWalkSat described below.

WalkSat is a local search method designed to address the problem
of boolean satisfiability~\cite{kautz96}. MaxWalkSat is
a variant of  that algorithm that applies weights to each clause in a
conjunctive normal form equation~\cite{selman96}. 
While WalkSat tries to satisfy the entire set of clauses, MaxWalkSat
tries to maximize the sum of the weights of the satisfied
clauses. 

In one respect, both algorithms can be viewed
as a variant of simulated annealing (or the hill climbing 
approaches seen in Section \ref{sec:sarw}). Whereas simulated annealing always selects
the next solution randomly, the WalkSat algorithms will {\em sometimes}
perform random selection while, other times, conduct a local search to find the
next best setting to one variable.
 
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure MaxFunWalk
2. for TRIES:=1 to MAX-TRIES
3.    SELECTION:=A randomly generate assignment of mitigations
4.    for CHANGED:=1 to MAX-CHANGES
5.        if SCORE satisfies THRESHOLD return
6.        CHOSEN:= a random selection of mitigations from SELECTION
7.        with probability P
8.            flip a random setting in CHOSEN
9.        with probability (P-1)
10.           flip a setting in CHOSEN that maximizes SCORE
11.    end for
12. end for
13. return BESTSCORE
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for MaxFunWalk}
\label{fig:MWF}
\end{figure}

MaxFunWalk is a generalization of MaxWalkSat:
\bi
\item
MaxWalkSat is defined over CNF formulae.  The success of a collection of variable settings is determined
by how many clauses are ``satisfiable'' (defined using standard boolean truth tables).
\item 
MaxWalkFun, on the other hand, assumes that there exist an arbitrary function 
that can assess a collection of variable settings.
Here, we use the DDP model as a
assessment function.
\ei
Note that
$MaxWalkFun=MaxWalkSat$ if the assessment  is conducted via a logical 
truth table. 

The MaxFunWalk procedure is shown in \fig{MWF}. When run, the user supplies an ideal cost and attainment. This setting is normalized, scored, and set as a goal threshold. If the current setting of mitigations satisfies that threshold, the algorithm terminates. 

MaxFunWalk begins by randomly setting every mitigation. From there, it will attempt to make a {\em single} change until the threshold is met or the allowed number of changes runs out (100 by default). 
A random subset of mitigations is chosen and a random number P between 0 and 1 is generated. The value of P  will decide the form that the change takes:
\bi
\item P$\le\alpha$: A stochastic decision is made. A setting is changed completely at random within the set CHOSEN.
\item P$>\alpha$: Local search is utilized. Each mitigation in CHOSEN is tested until one is found that improves the current score.
\ei

The best setting of $\alpha$ is domain-specific. For this study,
we used $\alpha=0.3$.

If the threshold is not met by the time that the allowed number of changes is exhausted, the set of mitigations is completely reset and the algorithm starts over. This measure allows the algorithm to avoid becoming trapped in local maxima. 
For the DDP models, I found that the number of retries has little effect on solution quality.

If the threshold is never met, MaxFunWalk will reset and continue to make changes until the maximum number of allowed resets is exhausted. At that point, it will return the best settings found. 

As an additional measure to improve the results found by MaxFunWalk, a heuristic was implemented to limit the number of mitigations that could be set at one time. If too many are set, the algorithm will turn off a few in an effort to bring the cost factor down while minimizing the effect on the attainment. 


\section{A* Search}

 A* is a best-first path finding algorithm that uses distance from origin ($G$)
and estimated cost to goal ($H$)
to find the best path~\cite{hart68}. The algorithm  is widely used
in a multitude of research areas~\cite{pearl84,norvig03,stout97,hui04}. 

A* is a natural choice for DDP optimization since the objective
function used to assess DDP model configurations (see Section \ref{sec:of})
is actually a Euclidean distance measure
to the desired goal 
of maximum attainment and minimum costs.  
Hence, for the second potion of the A* heuristic,  we can make direct use of \eq{score}.

The A* algorithm keeps a {\em closed} list in order to prevent 
backtracking. We begin by adding the starting state to the closed list.
 In each ``round,'' a list of neighbors is populated from the series of possible states reached by making a change to a single mitigation. 
If that neighbor is not on the closed list, two calculations are made: 
\bi
\item G = Distance from the start to the current state plus the additional distance between the current state and that neighbor.
\item H = Distance from that neighbor to the goal (an ideal spot, usually 0 cost and a high attainment). 
For DDP models, we use \eq{score} to compute H.
\ei
The {\em best} neighbor is the one with the lowest $F=G+H$. The algorithm ``travels'' to that neighbor and adds it to the closed list. 
Part of the optimality of the A* algorithm is that the distance to the goal is underestimated. 
Thus, the final goal is never actually reached by A*. 
My implementation terminates once it stops
finding better solutions
for a total of ten rounds. This number was chosen to give ample time for A* to become ``unstuck'' if it hits a corner early on.  


\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure A*
2. CURRENT_POSITION:= Starting assignment of mitigations
3. CLOSED[0]:= Add starting position to closed list
4.
5. while END:= false
6.    NEIGHBOR_LIST:=list of neighbors
7.    for each NEIGHBOR in NEIGHBOR_LIST
8.        if NEIGHBOR is not in CLOSED
9.            G:=distance from start
10.           H:=distance to goal
11.           F:=G+H
12.           if F<BEST_F
13.               BEST_NEIGHBOR:=NEIGHBOR
14.   end for
15.   CURRENT_POSITION:= BEST_NEIGHBOR
16.   CLOSED[++]:=Add new state to closed list
17.   if STUCK
18.       END:= true
19. end while	
20. return CURRENT_POSITION
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for A*}
\label{fig:A*}
\end{figure}



\section{KEYS and KEYS2}\label{sec:keysalgo}

The core premise of KEYS and KEYS2 is that the above algorithms perform over-elaborate searches.
Suppose 
that the behavior of a large system is
determined by a small number of {\em key} variables. 
If so, then a very rapid search for solutions can be found by
(a)~finding these {\em keys} then (b)
explore the ranges of the key variables.

The following small example illustrates this idea.
Within a model, there are chains of {\em reasons} linking inputs to desired goals.
Some of the links clash with others. 
Some of those clashes are most upstream; they are not dependent on other clashes. 
In the following chains of reasoning 
the clashes are $\{e, \neg e\}$, 
$\{g, \neg g\}$ 
\& $\{j,\neg j\}$;
the most upstream clashes 
are
$\{e \neg e\}$, 
\& $\{g \neg g\}$, 
\[\begin{array}{r@{}l@{}l}
&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
input_1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
input_2 \longrightarrow  &k \rightarrow \neg g \longrightarrow l \longrightarrow m \rightarrow \neg j & \longrightarrow goal\\
%&n \longrightarrow o \longrightarrow p \longrightarrow q \longrightarrow
\neg e
\end{array}
\]
In order to optimize decision making about this model, we must first decide about these {\em most upstream clashing reasons} (the ``keys'').
Returning to the above reasoning chains,
any of $\{a, b, ..q\}$ are subject to discussion.
However, most of this model is completely irrelevant to the task of
$input_i\vdash~goal$. For example, 
the $\{e, \neg e\}$ clash is
unimportant to the decision making process
as no reason uses $e$ or $\neg e$. 
In the context of reaching $goal$ from 
$input_i$, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$.
Further, since $\{j, \neg
j\}$ are dependent on $\{g,\neg g\}$, then the core decision
must be about variable $g$ with two disputed values: true and
false. 

Setting the keys reduces the number of reachable states within the model. 
Formally, the reachable states reduce to
the cross-product of all of the ranges of the collars.
This is called the $clumping$ effect. Only a small fraction of the possible states are actually reachable.
The effects of clumping can be quite dramatic.
Without knowledge of these keys,  the above model has $2^{20} > 1,000,000$ possible consistent states.
However, in the context of 
$input_i\vdash~goal$,
those 1,000,000 states clumps to just the following two states: 
$\{input_1,f,g,h,i,j,goal\}$ or
$\{input_2,k,\neg g,l,m,\neg j,goal\}$.

As documented in the Section \ref{sec:keys},
this notion of $keys$ has been
discovered and rediscovered
many times by many researchers.
The KEYS algorithm finds the keys uses a Bayesian sampling method. 
If a model contains keys then, by definition, those variables must appear in all solutions
to that model. If model outputs are scored by some oracle, then the key variables are those with ranges that occur with very different frequencies
in high/low scoring model outputs.
Therefore, we need not search for the keys- rather, we just need to keep frequency counts on how often ranges appear in $best$ or $rest$ outputs.

KEYS has
two main components - a greedy search and the BORE (best or rest) ranking heuristic.
The greedy
search explores a space of $M$ 
mitigations over the course of 
$M$ ``eras.'' 
Initially, the entire set of mitigations is set randomly. 
During each era, one more
mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. 
In the original version of KEYS~\cite{jalali08}, the greedy search fixes one variable per era.
A newer variant, KEYS2, fixes an increasing number of variables as the search progresses
(see below for details).

In KEYS (and KEYS2), each era $e$ generates
a set $<input,score>$ as follows:
\be
\item[1:]
$MaxTries$ times repeat:
\bi
\item
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item
	$Guessed$ are randomly selected values for unfixed mitigations.  
\item
	$Input = selected \cup guessed$.
\item
Call {\tt model} to compute $score=ddp(input)$;
\ei
\item[2:] The $MaxTries$ $score$s are divided into $\beta$\% ``best'' 
and remainder become ``rest''. 
\item[3:]
The $input$ mitigation values are then scored using BORE
(described below).
\item[4:]
The top ranked mitigations (the default is one, but the user may fix multiple mitigations at once) are fixed and stored in $selected[e]$.\ee
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure KEYS
2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.    for I:=1 to 100
4.       SELECTED[1...(I-1)] = best decisions up to this step
5.       GUESSED = random settings to the remaining mitigations
6.       INPUT = SELECTED + GUESSED
7.       SCORES= SCORE(INPUT)
8.    end for   
9.    for J:=1 to NUM_MITIGATIONS_TO_SET 
10.      TOP_MITIGATION = BORE(SCORES)       
11.      SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.   end for  
13. end while          
14. return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudocode for KEYS}
\label{fig:KEYS}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=5in]{keys.png}
\end{center}
\caption{The data architecture of the KEYS algorithm.} 
\label{fig:keysarch}
\end{figure}

The search moves to era $e+1$ and repeats steps 1,2,3,4.
This process stops 
when every mitigation has a setting.  
The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment.
After some experimentation, we used $MaxTries=100$ and $\beta=10$.
For full details, see \fig{KEYS}. 

KEYS ranks mitigations using a support-based
Bayesian ranking measure called BORE.
BORE ~\cite{clark05} (short for ``best or rest'')
divides numeric scores seen over $K$ runs and stores the top 10\%  in $best$ and the remaining 90\% scores in the set $rest$
(the $best$ set is computed by studying the delta
of each score 
to the best score seen in any era).
It then computes the probability that a value is found in $best$
using
Bayes theorem.
The theorem uses
evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$,
to calculate a  posteriori  probability
$P(H|E)=P(E|H) P(H)\; /\; P(E)$.
When applying the theorem, {\em likelihoods}
are computed from observed
frequencies. These likelihoods (called "like" below) are then normalized to create
probabilities. This normalization cancels out $P(E)$ in Bayes theorem.
For example, after $K=10,000$ runs are divided into  1,000 {\em best} solutions and 9,000
{\em rest}, the  value \mbox{$mitigation31=false$} might appear 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:\newline
\begin{minipage}{1.0\linewidth}
{\scriptsize
\begin{eqnarray}\nonumber
E&=& (mitigation31=false)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(E|best)&=&10/1000 = 0.01\\\nonumber
freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
\end{eqnarray}}
\end{minipage}\newline
Previously~\cite{clark05},
it has been found that Bayes theorem
is a poor ranking heuristic
since it is easily distracted by low frequency evidence.
For example, note how
the probability of $E$ belonging to the best class
is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but
$freq(E|best) = 0.01$. 

To avoid the problem of unreliable low frequency evidence, I augment \eq{ten}
with a support term.
Support should $increase$ as the frequency of a value $increases$,  i.e. 
$like(best|E)$ is a valid support measure.
 Hence, step 3 of the greedy search ranks values  via
\begin{equation}\label{eq:ps3}
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

During each era, KEYS samples the DDP models and fixes the top $N=1$ 
settings. KEYS2 assigns progressively larger values. 
In era 1, KEYS2 behaves exactly the same as KEYS
while
in (say) era 3, KEYS2 will
fix the top 3 ranked ranges. Then, in era 4, KEYS2 will fix the top four ranges.
Since it sets more variables at each era,
KEYS2 terminates earlier than KEYS.
A summary of the architecture of KEYS can be seen in \fig{keysarch}.
Note that
decision ordering diagrams could be 
directly generated during execution,
just by collection statistics from the {\tt SCORES} array used in
line 7  of \fig{KEYS}.

\section{Other KEYS Variants}

KEYS was orders of magnitude faster than prior treatment learning solutions to the 
DDP requirements problem~\cite{promise08}. While other algorithms would take minutes to execute, KEYS is capable of 
optimizing the largest models in a fraction of a second. While this is adequate for current requirements
models, it is always desirable to find faster solutions. 
Therefore, it became necessary to research methods that would speed up KEYS' current performance. 

Several different methods and rates have been tested for fixing multiple settings per round. KEYS2, presented in 
the previous section, was found to be the best of these for its balance of execution time and low result variance. 
KEYS2 was not the first attempt to improve the performance of the 
original KEYS, nor was it the last. Some of the other heuristics benchmarked were:
\bi
\item Fix all mitigations with a performance score within 5\% of the top score for that round.
\item Set all mitigations that are correlated (i.e. that have the same frequency in the "best" instances) to the top-performing configuration.
\item Generate fewer random configurations each round. That is, on the first round, it would generate $N$ configurations 
($N >=$ number of mitigations). On the second round, it would generate $N-1$ instances. 
\item Introduce a sloping threshold for the split between the {\em best} and {\em rest} instances. 
\item On the first round, fix a mitigation as KEYS normally would. At the same time, this variant would populate a list 
of similar-scoring instances. The following round, it would only look at those instances instead of generating new ones. On the third
round, it would form a new list of "neighboring" instances and consider those for the fourth round. This continues until 
all mitigations have fixed settings.
\item A KEYS variant combining the above {\em neighbor} concept with KEYS2, setting a larger number of mitigation values each round.
\ei

In benchmarking tests, some of these were faster than KEYS2, but those variants returned either sub-par performance or 
too much variance in their judgments (in the language of the decision ordering diagrams, they were {\em well-behaved} but not {\em tame}). 
Other variants represented too small of a runtime improvement over KEYS. Ultimately, KEYS2's heuristic was selected as the most 
effective. 

\subsection{KEYS-R}\label{sec:keysr}

While KEYS2 represents a large runtime improvement over the original KEYS, 
it contains a flaw that limits future performance improvements. By setting multiple mitigations each round, the 
algorithm loses the "support" built by the one-hundred instances generated each round. 
Therefore, while KEYS2 is faster than the original KEYS, its results are less tame.

The small amount of additional variance in KEYS2 is still within acceptable boundaries; therefore,
it has found some use in DDP-related experiments. However, this has limited the further improvements that could be made to the KEYS 
algorithm. Numerous other variations on how to set multiple mitigations per round have shown result variance far outside acceptable 
values. Other methods have not shown variance problems, but these versions were slower than KEYS2, limiting their possible use. 
This issue prompted a new round of research. If the key to speeding up the KEYS algorithm was not in setting additional mitigations
each round, where was it? 

When a software profiler was used on KEYS2, one interesting point was revealed. Nearly {\em 70\%} of the runtime was spent in calling the model
(i.e. sending a new set of mitigations to the precompiled model and receiving back a new cost and attainment value).
Each round, both KEYS and KEYS2 generate one-hundred sets of mitigations and score them. They use these instances to find the best set of mitigations
to fix for that round. The instance generation step is the chief bottleneck in the KEYS algorithm. However, a large number of instances is needed to 
provide the {\em support} necessary to accurately rank mitigations. If fewer instances are generated, you have the same issue as when too many mitigations
are set. There is a larger variance in results, and those results tend to contain higher cost and lower attainment values.
Therefore, the question is how to call the model {\em fewer} times while retaining {\em high} support for the instance set.

A new variant of the KEYS algorithm, KEYS-R addresses this issue by retaining certain subsets of previously-generated instances and reusing them in later rounds. KEYS-R begins by calculating two {\em threshold} values. These values are the highest possible cost (i.e. the cost if all mitigations are used)
and the highest possible attainment. 
The central loop (instance generation, ranking, and mitigation fixing) commence in the same way as the original KEYS. 
One hundred new instances are generated and stored. The key difference comes in the next step. Once an instance is scored, its cost and attainment 
values are compared to the previously-calculated threshold values. If an instance scores within ten percent of these values (if its cost is less than 10\% of the highest possible cost and its attainment is greater than 90\% of the model's possible attainment), it is stored in a collection of the {\em best} 
instances. If the instance's cost value is within 10\% to 35\% of the cost threshold and its attainment is from 65\% to 90\% of the possible attainment value, it is stored in a collection of {\em middle} instances. 

Each round, before a new set of instances is generated, a random subset of the {\em top} and {\em middle} sets are used instead of generating new instances. In order to ensure that support is maintained, new instances must be generated. Therefore, up to 33 instances can come from each set, and the remaining 34 will be randomly generated new instances. 

As individual mitigations are fixed, these previously used instances will begin to lose their support value. That is to say,
results will lose their rigidity and variance will increase. Therefore, it is still important that we not reuse an instance too many times. 
A balance must be maintained between the stored instances and the newly-generated ones. To address this, a decay timer is attached to each instance when it is added to either the {\em top} or {\em middle} subsets. Whenever a new instance is added to once of these subsets, it will immediately replace an instance whose decay timer has expired. This allows support to be maintained while reducing the number of new instances that must be generated each round.  

Benchmarking experiments assessing KEYS-R can be seen in Section \ref{sec:bkr}.

\section{Other Work on ``Keys''}\label{sec:keys}

The core premise of the KEYS algorithm is that a small number of important variables effectively set the rest, greatly reducing the 
search space.
Elsewhere ~\cite{me03l}, 
dozens of papers that have reported this same effect under a variety of names, including {\em
narrows, master-variables, back doors,} and {\em feature subset
selection}.

Amarel ~\cite{Amarel86} observed that search problems contain narrow sets of variables or collars that must be used in any solution.
In such a search space, what matters is not so much how you get to these collars, but what decision you make when you get there.
Amarel defined macros encoding paths between {\em narrows}, effectively permitting a search engine to jump between them.

In a similar theoretical analysis,
Menzies \& Singh~\cite{me03l} 
computed the odds of a system selecting solutions
to goals using complex, or simpler, sets of preconditions.
In their
simulations, they found that a system will naturally select for tiny
sets of preconditions (a.k.a. the keys) at a very high probability.

Numerous researchers have examined {\em feature subset selection};
i.e. what happens when a data miner deliberately ignores some of
the variables in the training data. For example, Kohavi and
John~\cite{kohavi97} showed in numerous datasets that as few as
20\% of the variables are $key$ - the remaining 80\% of variables
can be ignored without degrading a learner's classification accuracy.

Williams et.al.~\cite{williams03} discuss how
to use keys  (which they call ``back doors'') to optimize search.
Constraining these back doors also constrains the rest of the program. 
So, to quickly search a program, they suggest imposing some set values on the key variables.
They showed that setting the keys
can reduce
the solution time of certain hard problems from exponential to polytime, provided that the
keys can be cheaply located, an issue on which Williams et.al. are curiously silent.

Crawford and Baker ~\cite{crawford94} compared the performance of
a complete TABLEAU prover to a very simple randomized search engine
called ISAMP.  Both algorithms assign a value to one variable, then
infer some consequence of that assignment with forward checking.
If contradictions are detected, TABLEAU backtracks while ISAMP
simply starts over and re-assigns other variables randomly. Incredibly,
ISAMP took {\em less} time than TABLEAU to find {\em more} solutions
using just a small number of tries. Crawford and Baker hypothesized
that a small set of {\em master variables} set the rest and that
solutions are not uniformly distributed throughout the search space.
TABLEAU's depth-first search sometimes drove the algorithm into
regions containing no solutions.  On the other hand, ISAMP's
randomized sampling effectively searches in a smaller space.

In summary, this "keys" assumption, that a small subset of variables are far more important than all others, is supported in many different domains.

\section{Summary}

This chapter has discussed a series of algorithm implementations intended to offer ideal solutions to the DDP problem 
(that is, a balance between the budget and the attainment of goals). Each algorithm chosen for my experiments is
discrete, sequential, and unconstrained, and thus, is appropriate for comparison to the others. 
These methods all operate in different ways - 
A* treats the search space as a graph, while simulated annealing jumps between solutions based on a probability
function - but they all utilize the same objective function and offer compatible results. 

In this chapter, I have also presents my own approach to the problem - the KEYS (and KEYS2) algorithm. This technique focuses on the idea
that a small number of variables have a disproportionate influence over the search space, and by setting those variables,
you can quickly force the results into a somewhat-optimal area of the search space. There is much evidence for such a notion in the data mining
field, as shown in Section \ref{sec:keys}. 

The next chapter details a series of case studies benchmarking the algorithms presented in this chapter.  
