The previous chapter has introduced the problem that this research will attempt to solve. 
This chapter will provide background material on the model format used in these experiments, as
well as the decision ordering diagrams used for the interpretation of the search results.

\section{The Defect Detection and Prevention Model}

The
Defect Detection and Prevention (DDP) requirements modeling tool~\cite{corn01,feather08}. 
is used to interactively document the 
early life-cycle
 meetings conducted by "Team X" at 
NASA's Jet Propulsion Laboratory (JPL). 
These meetings are the source of the real-world requirements models used in this thesis.

At Team X meetings, 
a large and diverse group of up to 30 experts from various fields (propulsion, engineering,
communication, navigation, science, etc) meet for short periods of time
(usually for no more than four or five days) to produce
a
``mission concept'' document. This document may commit the current project to, for example,
solar power rather than nuclear power or to some particular style of guidance software. 
All subsequent work on the project is guided by the initial design decisions contained in these mission concept documents. 



\begin{figure}[!t]
{\footnotesize
\begin{tabular}{p{\linewidth}}\hline
\be
\item Requirement goals:
\bi
\item
Spacecraft ground-based testing \& flight problem monitoring
\item
 Spacecraft experiments with on-board Intelligent Systems Health Management (ISHM)
\ei
\item Risks:
	\bi
	\item Obstacles to spacecraft ground-based testing \& flight problem monitoring
			\bi
			\item
			Customer has no, or insufficient, money available for my use
			\item
			Difficulty of building the models / design tools
			\ei
	\item ISHM Experiment is a failure (without necessarily causing flight failure)
	\item Usability, User/Recipient-system interfaces undefined
	\item V\&V (certification path) untried and scope unknown
	\item Obstacles to Spacecraft experiments with on-board ISHM
	\bi
	\item Bug tracking / fixes / configuration management issues, Managing revisions and upgrades (multi-center tech. development issue)
	\item Concern about my technology interfering with in-flight mission
	\ei
	\ei
\item Mitigations:
	\bi
	\item  Mission-specific actions
		\bi
		\item Spacecraft ground-based testing \& flight problem monitoring
		\item  Become a team member on the operations team
		\item Use Bugzilla and CVS
		\ei
	\item  Spacecraft experiments with on-board ISHM
		\bi
		\item Become a team member on the operations team
		\item Utilize xyz's experience and guidance with certification of his technology
		\ei
	\ei
\ee\\\hline
\end{tabular}}
\caption{Sample DDP requirements, risks, mitigations.}\label{fig:ddpegeg}
\end{figure}


The DDP model allows for the representation of the goals, risks, and
risk-removing mitigations that belong to a specific project.  
During  a Team X meeting,
users of DDP explore combinations of mitigations that will cost the least amount
while still supporting the largest number of requirements.  
For example, here is a trivial DDP model
where  {\tt mitigation1} costs \$10,000 to apply and each requirement is of equal
value (100). Note that the mitigation can remove 90\% of the risk. Also, unless mitigated,
the risk will disable 10\% to 99\% of requirements one and two (respectively):
\begin{equation}\label{eq:mod1}
\overbrace{mitigation1}^{\$10,000} \underbrace{\rightarrow}_{0.9} risk1 \rightarrow
\left< \begin{array}{c} \overbrace{\rightarrow}^{0.1} (requirement1=100) \\ 
\underbrace{\rightarrow}_{0.99} (requirement2=100) \end{array} \right.\end{equation}
The other numbers show the impact of mitigations on risks, and the impact of risks
on requirements. DDP propagates a series of influences over two matrices: 
one for {\em mitigations*risks} and another for
{\em risks*requirements}.

The DDP tool supports a graphical interface for the rapid entry of the
assertions. Such rapid entry is essential, these experts are busy and it is hard to gather them 
together for any long period of time and, as such, no tool should slow the debate. 
Therefore, DDP uses a lightweight representations for its model. Such representations are essential for early life-cycle decision making since
only high-level assertions can be collected in such short knowledge acquisition
sessions 
(if the assertions get more elaborate, then experts
may waste time trying to understand technical arguments from outside of their
own field of expertise). 
DDP uses the following ontology:
\bi
\item \textit{Requirements} (free text) describe the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) of each requirement, reflecting
their relative importance; 
\item \textit{Risks} (free text) are
events that damage the completion of requirements; 
\item \textit{Mitigations}: (free
text) are actions that reduce risks; 
\item \textit{Costs}: (numbers) reflect the cost associated with activating a mitigation;
\item \textit{Mappings}: directed, weighted edges between
requirements, mitigations, and risks that capture the quantitative relationships among them. 
\item \textit{Part-of relations}:
structure the collections of requirements, risks and mitigations; 
\ei
Note that DDP models are a form of the ``requirements models'' that were defined in Chapter 1.
For examples of risks, requirements, and mitigations, see \fig{ddpegeg}. 
For an example of the network of connections between risks and requirements and mitigations,
see
\fig{DDPexample}.


\begin{figure}
\begin{center}
\includegraphics[angle=90, height=6in,width=5in]{fig2new.png}
\end{center}
\caption{An example of a model formed by the DDP tool. Red lines connect 
risks (middle) to requirements (left). Green lines connect mitigations (right)
to the risks.} 
\label{fig:DDPexample}
\end{figure}

It can be asked whether the analysis of DDP requirements models is a  real problem.  
With these ultra-lightweight languages, aren't all open issues rendered obvious?
Such a question is typically informed by the small model fragments
that appear in the ultra-lightweight modeling literature. Those
sample model fragments are typically selected according to their
ability to fit on a page or to succinctly illustrate some point of
the authors.  Real world ultra-lightweight models can be much more
complex, paradoxically perhaps due to their simplicity: if a model
is easy to write then it is just as easy to write a lot of it.  
For example, the model seen in \fig{DDPexample} was generated in under a week by four people discussing
one project.  It is complex and densely-connected (a close inspection
of the left and right hand sides of \fig{DDPexample} reveals the
requirements and fault trees that inter-connect concepts in this
model) and it is, by no means, the biggest or most complex DDP model
that has ever been built. 

This research has been structured around DDP for three reasons.
Firstly,
one potential drawback with ultra-lightweight models is that they are excessively lightweight and contain no useful
information. DDP's models are demonstrably useful, and clear project improvements have been seen from DDP sessions at JPL. 
Cost savings of \$100,000 have been seen in multiple sessions, and in at least two sessions, they have exceeded \$1 million~\cite{feather08}. 
Cost savings are not the only benefits of these DDP sessions, numerous design improvements (such as savings of power or 
mass) have emerged as well.
Likewise, the spectrum of risks has shifted from uncertain architectural ones to more predictable and manageable ones. 
At some of these meetings, non-obvious (yet significant) risks have been identified and subsequently mitigated. 

The second reason for using DDP is that numerous real-world requirements models
have written in this format, and many projects are likely to use these models in the future.
The DDP tool can be used to document not just final decisions,
but also to review the rationale that led to those decisions.
Hence, it remains in use at JPL not only for its original purpose (group decision support),
but also as a design rationale tool to document decisions. 
Recent DDP sessions included:
\bi
\item An identification of the challenges of intelligent systems health management (ISHM) technology maturation
(to  determine the most cost-effective approach to achieving maturation)~\cite{feather08b};
\item A study on the selection and planning of deployment of prototype software~\cite{feather08c}.
\ei

The third, and most important, reason to use DDP in this research is that the
tool is representative of other requirements modeling tools in widespread use.
At its core, DDP is a set of influences expressed in a hierarchy, augmented with the occasional equation. Edges
in this hierarchy have weights that strengthen or weaken the influences that flow along those edges. 
At this level of abstraction, DDP
is just another form of QOC~\cite{shum94}  or a quantitative variant of Mylopoulos' qualitative soft goal graphs~\cite{mylo99}.

\section{Model Inputs and Outputs}
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
#include "model.h"

#define M_COUNT 2
#define O_COUNT 3
#define R_COUNT 2

struct ddpStruct
{
    float oWeight[O_COUNT+1];
    float oAttainment[O_COUNT+1];
    float oAtRiskProp[O_COUNT+1];
        float rAPL[R_COUNT+1];
    float rLikelihood[R_COUNT+1];
    float mCost[M_COUNT+1];
    float roImpact[R_COUNT+1][O_COUNT+1];
    float mrEffect[M_COUNT+1][R_COUNT+1];
};

ddpStruct *ddpData;

void setupModel(void)
{
    ddpData = (ddpStruct *) malloc(sizeof(ddpStruct));
    ddpData->mCost[1]=11;
    ddpData->mCost[2]=22;
    ddpData->rAPL[1]=1;
    ddpData->rAPL[2]=1;
    ddpData->oWeight[1]=1;
    ddpData->oWeight[2]=2;
    ddpData->oWeight[3]=3;
    ddpData->roImpact[1][1] = 0.1;
    ddpData->roImpact[1][2] = 0.3;
    ddpData->roImpact[2][1] = 0.2;
    ddpData->mrEffect[1][1] = 0.9;
    ddpData->mrEffect[1][2] = 0.3;
    ddpData->mrEffect[2][1] = 0.4;
}

void model(float *cost, float *att, float m[])
{
    float costTotal, attTotal;
    ddpData->rLikelihood[1] = ddpData->rAPL[1] * (1 - m[1] * ddpData->mrEffect[1][1]) 
        			* (1 - m[2] * ddpData->mrEffect[2][1]);
    ddpData->rLikelihood[2] = ddpData->rAPL[2] * (1 - m[1] * ddpData->mrEffect[1][2]);
    ddpData->oAtRiskProp[1] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][1]) 
        			+ (ddpData->rLikelihood[2] * ddpData->roImpact[2][1]);
    ddpData->oAtRiskProp[2] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][2]);
    ddpData->oAtRiskProp[3] = 0;
    ddpData->oAttainment[1] = ddpData->oWeight[1] * (1 - minValue(1, ddpData->oAtRiskProp[1]));
    ddpData->oAttainment[2] = ddpData->oWeight[2] * (1 - minValue(1, ddpData->oAtRiskProp[2]));
    ddpData->oAttainment[3] = ddpData->oWeight[3] * (1 - minValue(1, ddpData->oAtRiskProp[3]));
    attTotal = ddpData->oAttainment[1] + ddpData->oAttainment[2] + ddpData->oAttainment[3];
    costTotal = m[1] * ddpData->mCost[1] + m[2] * ddpData->mCost[2];

    *cost = costTotal;
    *att = attTotal; 
}
\end{verbatim}}
~\hrule~
\caption{A trivial DDP model after knowledge compilation}
\label{fig:ddpExample}
\end{figure}

\subsection{Pre-Processing}

To enable fast runtimes,
a simple compiler  exports the DDP models into a form easily accessible by optimization algorithms.
This compiler stores a flattened form of the DDP requirements tree in a function usable by any program in the C language. 
In the compiled form, all computations are  performed once 
and added as a constant to each reference of the requirement.
For example, the compiler converts the trivial model of \eq{mod1}
into {\tt setupModel} and {\tt model} functions 
similar to those in \fig{ddpExample}.
The {\tt setupModel} function is called only once (before an algorithm performs any configuration of the mitigation settings) 
and sets several constant values. 
The {\tt model} function is called whenever cost and attainment values are needed for a particular configuration.
The topology of the mitigation network is represented as terms in equations within these functions. 
As the models grow more complex, so do these equations. For example,
the biggest real-world model used in this research, which contains 99 mitigations, generates 1427 lines of code.
\fig{ddpModels} compares this large model to four other real-world DDP models.
Without any form of compilation, any DDP assessment algorithm would have to read a separate file and import it into a usable format
every time that it needed new cost and attainment values. This one-time compilation removes that pressure, leading to exponential 
improvements in execution time (earlier DDP algorithms would take thirty minutes or more to run).

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|c|c|} \hline
Model&LOC&Objectives&Risks&Mitigations\\ \hline
model1.c&  55  &3         &2    &2          \\ \hline
model2.c& 272   &1         &30   &31         \\ \hline
model3.c& 72   &3         &2    &3         \\ \hline
model4.c& 1241   &50        &31   &58         \\ \hline
model5.c&1427    &32        &70   &99         \\ \hline
\end{tabular}
\end{center}
\caption{Details of Five DDP Models. }
\label{fig:ddpModels}
\end{figure}

Currently, it takes
about two seconds to compile a model with 50 requirements, 31 risks, and 58 mitigations. 
This compilation only has to happen once, after which an algorithm can run any number of what-if scenarios.
While this is not a significant bottleneck, the current compiler (written in
unoptimized Visual Basic code) can certainly be sped up.
Experts usually change a small portion of the model before running up to $2^{|d|}$ what-if scenarios to
understand the impact of that change. Therefore, an incremental compiler
(that only updates changed portions) would run much faster than a full 
compilation of the entire DDP model.

\subsection{Artificial Model Generation}\label{sec:igen}

Although the core experiments of this thesis are based on a series of five real-world models, it is 
always desirable to have more data to work with. Unfortuantely, large repositories of real-world models are not always available, and they
do not always meet the criteria (number of mitigations, complexity of the interconnections, etc) of a given experiment. However, 
artificial models are an acceptable substitute, assuming that they follow the same structures and guidelines as the real-world models. 

Thus, an artificial model generator was constructed in Python that:
\bi
\item
Examined the real-world DDP models of \fig{ddpModels}; 
\item
Extracted
statistics related to the different types  of nodes (mitigations or risks or requirements) and the number of
edges between different types of nodes; 
\item 
Used those statistics to build  random models that are both larger and more complex than the original models.
\ei

This structure of the real-world models is recreated in a set of arrays that record the internal calculations as follows:
\bi
\item The raw number of goals, risks, and mitigations.
\item The cost of each mitigation.
\item The weight of each goal.
\item The impacts of risks on goals.
\item The effects of mitigations on risks. 
\item Other internal values.
\ei
The decisions made during the construction of a new artificial model must be constrained by the same rules that govern real-world 
DDP models. 
To ensure this, a user must choose one of the existing models as an initial starting-point.
The model generator takes that real-world model and mutates it into a new one based on several user-specified parameters:
\bi
\item {\em Model-Type}: Which existing model to base the artificial model off of. 
\item {\em Size}: A multiplier value used to increase the number of goals, risks, mitigations, and connections between the three. 
If the original model had two risks, six mitigations, and three goals, setting a size multiplier of four would give the artificial model
eight risks, twenty-four mitigations, and twelve goals. 
\item {\em Density}: Governs the connections between risks and goals, and between mitigations and risks. The user supplies density values 
for both types. The size parameter grows density linearly (a model four times the size of one of the originals will have four times the connections.
This density parameter is an additional multiplier on that, which lets you produce models that are not only larger, but more complicated. 
\item {\em Variance}: When creating a new model, each mitigation, goal, and connection must have a value. These values should be informed by, but 
not directly copied from, the original model. The variance parameter controls the deviation from the distribution of values in the real-world model.
For example, setting a variance of 0.25 would allow for values within +/- 25\% of those in the original model.  
\ei

\begin{figure}
\begin{center}
\includegraphics[width=6in]{igen.png}
\end{center}
\caption{An example of creating an artificial model. The new model is twice as large as the original, 
with no additional connection density, and values come from a
distribution within +/- 25\% of the original distribution.} 
\label{fig:genexample}
\end{figure}

After loading the specified real-world model into the arrays specified above, a coded function conducts a sampling of the model values.
A second function, governed by the user-supplied settings to each parameter, builds arrays that represent the new model. 
These arrays are then converted into the compiled "C" format read by the optimization algorithms and saved to the local file system. 

A simple example of this process can be seen in \fig{genexample}. 
The original model, seen on the left, has three mitigations, two risks, and two goals. The user chooses to create a new model that is twice as large,
but with the same level of density. The user also wants all values to remain within 25\% of the original value distribution. 
The new model, on the right, demonstrates all of these qualities (goal weights, risk $\rightarrow$ goal impact, 
and mitigation $\rightarrow$ risk impact not pictured).  

This model generator is used in the scale-up study of Section \ref{sec:scaleup} and to benchmark an algorithm variant in Section \ref{sec:bkr}.
In the absence of a large donation of real-world DDP models, artificial models will likely find more and more use as this research progresses.

\subsection{Objective Function}\label{sec:of}

When the {\tt model} function is called, a pairing of the total cost of the selected mitigations and the number of reachable requirements (
the attainment) is returned. 
These two values are used by an objective function to score the current configuration of mitigations.
The performance values are normalized into a single score that represents the Euclidean distance to a {\em sweet spot} of 
maximum requirement attainment and minimum cost: 
\begin{equation}\label{eq:score}
score = \sqrt{\overline{cost}^2 + (\overline{attainment}-1)^2}
\end{equation}

Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, my scores ranges $0 \le score \le \sqrt{2}$ and
{\em lower} scores are {\em better}.

\subsection{Decision Ordering Diagrams}\label{sec:dod}

The objective function described above summarizes {\em one} call to a DDP model. 
This section describes
{\em decision ordering diagrams}, which are a tool for summarizing the 
results of thousands of calls to DDP models.

Consider some recommendation for changes to a project that requires decisions $d$ of size $|d|$.
In the general case, $d$ is a subset of the space of all solutions $D$  ($d \subseteq D$).
When checking for solution robustness, or reflecting over  modifications to 
$d$, a stakeholder may
need to consider up to $d'\subseteq N^{|d|}$  possibilities (and $N=2$ for binary decisions, like whether or not to enable a mitigation
in a DDP model).
This can be a slow process, especially if evaluating each decision 
requires invoking a
slow and complex simulator.

Decision ordering diagrams are a linear-time method for studying the
robustness and neighborhood of a set of decisions.
The diagrams assume that some method could offer a {\em linear ordering} of the decisions $x \in d$
ranked from 
{\em most-important} to {\em least-important}.
They also assume that some
method
offers
information on the effects of applying the top-ranked $1\le x \le |d|$
decisions
(e.g. the median and variance seen in the model's
objective function after applying solution \mbox{$\{d_1 .. d_x\}$}).
For example, the decision ordering diagram of \fig{actiono} shows such a linear ordering
(this figure presents
$benefit$  and $cost$ results).
In that figure:
\bi
\item
 The x-axis denotes the number of decisions made.
\item
The y-axis shows performance statistics of an objective function seen after imposing the conjunction of decisions
$1 \le i \le x$.  
\ei
To assess performance, some objective function is run, and the results
report the median (50th percentile) and {\em spread} (the range given by 
the 75th percentile - the 50th percentile) of the values reported by this function. 
I use median and spread to avoid any parametric assumptions.


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{dod.png}
\end{center}
\caption{A Decision Ordering Diagram. The median and spread plots show 50\%-the
percentile and the (75-25)\%-th percentile range (respectively) values generated
from some objective function.}\label{fig:actiono}
\end{figure}

These diagrams can comment on the robustness and neighborhood of
solution $\{d_1.. d_x\}$ as follows:
\bi
\item By considering the variance of the performance statistics after applying $\{d_1 .. d_x\}$.
\item By comparing the results of using the first $x$ decisions to that of using the first $x-1$ or $x+1$
actions.
\ei
The neighborhood of a solution that uses decisions $\{d_1..d_x\}$ are solutions
that use the decisions $\{d_1..d_{x\pm j}\}$.  Since $j$ is bounded $0 \le |d|-1$, this means that 
{\em reflecting
over solution neighborhoods takes time linear on the number of decisions $d$}.

Decision ordering diagrams are a natural representation for
``trade studies,''
the activity of a multidisciplinary team to identify the most balanced 
technical solution among a set of proposed viable solutions~\cite{faa06}.
For example, minimum costs and maximum benefits 
are achieved at point $x_2$ of \fig{actiono}. However, after applying only half the decisions (see $x_1$)
most of the benefits could be achieved, albeit at a somewhat higher cost.

Decision ordering diagrams are {\em useful} under at least three conditions:
\bi
\item  
The scores output by the objective functions are {\em well-behaved}; i.e. move smoothly to
a plateau.
\item
The decisions {\em tame} the variance; i.e.
the spread falls to value much lower than then median (otherwise, it is hard to show that decisions
have any effect on the system performance).
\item The are generated in a {\em timely} manner.
Fast runtimes are required in order to keep up with fast moving discussion.
\ei
According to these definitions, \fig{actiono} is a {\em useful} decision ordering diagram if it can be generated in a {\em timely} manner.

It is an open issue if real worlds requirements models  generate useful
decision ordering diagrams.  
The experiments of this thesis test if, in practice, decision ordering
diagrams generated from  
real world requirements models are {\em timely} to generate while being  {\em well-behaved} and {\em tame}.

	\section{Models of Requirements Engineering}\label{sec:ffm}

The Defect Detection and Prevention model is a ultra-lightweight modeling tool.
The value of ultra-lightweight ontologies
in early life cycle modeling
is widely recognized.
For example, 
Mylopoulos' {\em soft-goal} graphs~\cite{mylo92,mylo99}
represent
knowledge about non-functional requirements.
The primitive values in soft goal modeling include statements of partial
influence such as {\em helps} and {\em hurts} relationships.
An example of a soft-goals graph can be seen in Figure \ref{fig:sg}.

\begin{figure}
\fbox{
	\begin{minipage}{6.33in}
	\begin{center}
	\includegraphics[width=6.25in]{softgoals.png}
	\end{center}
	\caption{An example soft-goals graph, from ~\cite{mylo99} which represents employee attributes.}
	\label{fig:sg}
	\end{minipage}
}
\end{figure}

Another  commonly used  framework in the design rationale
community is a  ``questions-options-criteria'' (QOC)
graph~\cite{shum94}. In  QOC
graphs:
\bi
\item {\em Questions} suggest {\em options}.
 Deciding on  one option can
raise other  questions;   
\item Options   shown  in  a  box denote  {\em selected
options};  
\item
Options are assessed  by  {\em criteria}; 
\item Criteria represent gradual
knowledge.
\ei
QOC graphs can succinctly  summarize lengthy debates. For example, the four-hundred and eighty
sentences stated in  a  debate on  interface options  can be    displayed    in  a single-page QOC   graph (as can be seen in Figure \ref{fig:qoc}.

\begin{figure}
\begin{center}
\includegraphics[width=5in]{qoc.png}
\end{center}
\caption{An example QOC graph, from ~\cite{maclean96}.\newline
This graph represents the design space for the XCL project. The boxed Options are the
decisions made in the design of the XCL environment.} 
\label{fig:qoc}
\end{figure}

While DDP shares many of the design aspects of soft-goal and QOC graphs, it differs in its representations
and inference methods.  
As explained above around \eq{mod1},
while QOC  and soft-goals
propagate influences over hierarchies,  DDP propagate influences over matrices.

Zave \& Jackson~\cite{zave97}  define requirements engineering as finding the specification $S$ for the
domain assumptions $K$ that satisfies the given requirements $R$:
\begin{equation}\label{eq:zj}
\mbox{find $S$ such that~} S \vdash R
\end{equation}
Jureta et al.~\cite{jureta08} take issue with \eq{zj}, saying 
that it
implicitly assumes that $K,S,R$ are precise and complete enough for the satisfaction relation to hold. 
More specifically, Jureta complains that \eq{zj}
does not permit
partial fulfillment of (some) non-functional requirements. Additionally, the Zave \& Jackson definition
does not allow any preference ordering; that is, $specification_1$ cannot be said to be more important than $specification_2$. 
Jureta et al. offer a replacement ontology where classical inference
is replaced with  operators that support the generation and ranking of
subsets of domain assumptions that lead to maximal (with respect to size) subsets of 
the possible goals, as well as soft-goal quality criteria. 

DDP reinterprets ``$\vdash$''  in \eq{zj} as an inference across numeric quantities, rather than the inference
over discrete logical variables suggested by Zave \& Jackson. Hence, it can achieve the same goals as
Jureta (the ranking of partial solutions with weighted goals) without requiring Jureta's ontology.

\section{Early vs Later Life-cycle Requirements Engineering}\label{sec:emod}
The DDP models presented in this thesis come from the NASA Jet Propulsion 
Lab's Team X meetings, which conduct early life-cycle requirement discussions.

Once a system is running, released, and being maintained or extended, 
another problem to solve
is {\em release planning}; i.e.
what features to add to the next $N$
releases. To solve this problem,
some sort of inference engine must
reason about which functionality extensions
to current software can best satisfy outstanding stakeholder requirements. 
The challenge of release planning is that the
 benefits of added functionality must be weighed against the cost of implementing those
extensions.

Several approaches have been applied to this problem.
The {\em Next Release Problem} was elaborated on by Bagnall et al. in 2001~\cite{bagnall01}.
This problem is how to find the appropriate balance between customer satisfaction and available resources. 
They found that designing an optimal next release is an NP-hard problem. Their study focused on benchmarking
heuristics that could find a high-quality but potentially sub-optimal solution. Best solutions for the large problems
were found using variants of Simulated Annealing, which produced solutions within 1.5\% of the optimal value.

Ngo-The and Ruhe~\cite{ruhe09} studied how to allocate resources towards the implementation of features such that 
the value gained from adding such features was maximized. 
They proposed a two-phase optimization approach called $OPTIMIZE_{RASORP}$ that, in the first phase, applies integer linear programming
to the problem. In the second phase, a genetic algorithm executes over the reduced search space in order to generate resource allocation plans.
Their approach proved favorable over a standard greedy search when evaluated over six-hundred randomly generated problems.

Zhang et al.~\cite{zhang07b} also tackled the Next Release Problem from the multi-objective point of view.
They were concerned with the quality of the solutions, the number of possible solutions, the range of solutions covered, and the number of 
solutions obtained that were optimal. In order to solve the problem, they employed two metaheuristics, called NSGA-II and MOCell. 
They found that MOCell's solutions covered a larger range, while NSGA-II obtained better solution quality on large problems. 
Both obtained optimal solutions with a high percentage of low-cost requirements as well as requirements that most satisfied the customers.

Without further experimentation, I cannot assert that KEYS2 (or any of the DDP optimization algorithms elaborated on in this thesis) will work
as well on later life-cycle models - such as those used in release planning - as it does on the earlier life-cycle Team X models.  
However, at this time, I can see no reason why KEYS2 would not work as a non-linear optimizer of these later life-cycle models. 
Despite the differing intentions, the structure of late life-cycle models is relatively similar to that of early life-cycle models.
This could be a productive area for future work.

\section{Summary}

This chapter has presented the Defect Detection and Prevention model. This model, used by NASA's Jet Propulsion Laboratory, 
maps the requirements of a project to a series of risks. These risks are, in turn, mapped to a collection of mitigations. These
mitigations can prevent risks for a certain price. These models can be precompiled into a "C" file that contains a series of values
and equations. Precompiling models leads to faster execution times for search algorithms, as it is now faster to obtain a cost and attainment
score from the model for any given input. 
While the experiments in this thesis largely concentrate on five real-world DDP models, I would like to have larger models in 
order to study the effects of scale-up on the KEYS algorithm. This chapter details a generator used to create synthetic DDP models.
DDP is a form of early life-cycle modeling tool. I have discussed related tools in this chapter, as well as their uses. 

I am concerned with obtaining the ideal balance between the cost of a project and the number of attained goals. For any given input,
the model will generate separate cost and attainment values. This chapter presents the objective function used to transform those values
into a score. 

In order to study the output of any assessment algorithm, we must have a result visualization that is easy to read and understand. This
chapter discusses decision ordering diagrams, which allow a user to understand the impact of each decision during the search process.

The following chapter will detail a set of candidate algorithms to assess the DDP requirements satisfaction problem.
