\documentclass[12pt]{report}
\topmargin=0in
\headheight=0in
\headsep=0in
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.5in
\textheight=9in

\usepackage{setspace}
\usepackage{graphicx}
\usepackage{algorithmic,cite,footmisc,multirow,url,amsmath}
\usepackage{color}
\usepackage{pslatex}
\usepackage{fullpage}
\usepackage{alltt}
\usepackage{rotating}
\usepackage{float}
\usepackage{pifont}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage{listings}


\newenvironment{ccode}{\begin{center}\scriptsize\begin{alltt}}{\end{alltt}\end{center}\normalsize}

\singlespacing

\DeclareMathOperator*{\argmin}{arg\,min}

\newcommand{\hmm}[1]{{\underline {\bf #1}}}
\newcommand{\hey}{~~~$\blacktriangle\blacktriangle$}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\subsub}[1]{subsubsection~\ref{subsub:#1}}
\newcommand{\sub}[1]{subsection~\ref{sub:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}
\newcommand{\chap}[1]{Chapter~\ref{chap:#1}}
\newcommand{\boxplot}[5]{
\begin{picture}(100, 7)
\put(#1, 2){\line(0, 1){4}}
\put(#1, 4){\line(1, 0){#2}}
\put(#3, 4){\circle*{3}}
\put(#3, 4){\line(1, 0){#4}}
\put(#5, 2){\line(0, 1){4}}
\put(50, 3){\line(0, 1){4}}
\end{picture}
}

\begin{document}

\thispagestyle{empty}

\title{\large The Robust Optimization of Non-Linear Requirements Models}
\author{\normalsize Gregory Gay \\ \\ 
\normalsize Thesis submitted to the \\
\normalsize College of Engineering and Mineral Resources \\
\normalsize at West Virginia University \\
\normalsize in partial fulfillment of the requirements \\
\normalsize for the degree of \\ \\
\normalsize Master of Science in Computer Science \\ \\
\normalsize Tim Menzies, Ph.D., Chair \\
\normalsize Bojan Cukic, Ph.D. \\
\normalsize Katerina Goseva-Popstojanova, Ph.D. \\ \\
\normalsize Lane Department of Computer Science and Electrical Engineering \\ 
\normalsize West Virginia University \\
\normalsize Morgantown, West Virginia \\
\normalsize April 7, 2010 \\ \\
\normalsize Keywords: Search-Based Software Engineering, Treatment Learning,\\ 
\normalsize Minimal Contrast-Set Learning, Model-Based Software Engineering,\\
\normalsize Meta-Heuristic Search \\
}

\date{}
\maketitle
\begin{abstract}
\begin{center}
The Robust Optimization of Non-Linear Requirements Models \vspace{1.5ex} \\
Gregory Gay
\end{center}

\noindent Solutions to non-linear requirements engineering problems may be ``brittle''; i.e. small changes 
may dramatically alter solution effectiveness. Hence, it is not enough to just generate solutions to requirements problems- we must also
assess solution robustness. This thesis aims to address two concerns: (a)~Is demonstrating robustness a time consuming task? 
and (b)~ Is it necessary that solution quality be traded off against solution robustness? 

\noindent Using a Bayesian ranking heuristic, the KEYS2 algorithm fixes a small number of important variables, 
rapidly pushing the search into a stable, optimal plateau. 
By design, KEYS2 generates decision ordering diagrams (in time experimentally shown to be $O(N^{2})$). 
Once generated, these diagrams can confirm solution robustness in linear time.
When assessed in terms of reducing inference times, increasing solution quality, and decreasing the variance of the 
generated solution, KEYS2 out-performs other search algorithms (simulated annealing, A*, MaxWalkSat).
\end{abstract}

\doublespacing

\chapter*{Dedication}
\renewcommand{\thepage}{\roman{page}}
\setcounter{page}{3}

\begin{center}
\textit{I dedicate this work to Alan Turing
, Mark Harman, Ross Quinlan, Patrick Winston, Edward Feigenbaum, Alan Newell, 
Barry Boehm, and all of those that established the fields of
Artificial Intelligence, Machine Learning, and Search-Based Software Engineering.
You are giants, and it is only by standing on your shoulders that I may 
feel the wind. 
} \\
\end{center}

\chapter*{Acknowledgments}
There are a number of people that were pivitol to the creation of this thesis, and I would like to take this moment to 
acknowledge them. I'll start by thanking my parents for both their 
unwavering support and for letting me make my own mistakes (and, consequently, my own triumphs). 
I would also like to thank Dr. Menzies for having faith that there would 
be method in my madness. I could not have asked for a better advisor, and I owe him a debt for the opportunities that he has 
made available to me.

Of course, this type of research is never done in a vaccuum, and I would like to thank and acknowledge Omid Jalali 
for the creation of the KEYS algorithm. 
I would also like to thank Adam Nelson, Brian Sowers, Zach Milton, and everybody else at the Modeling Intelligence Lab for
being both great coworkers and great friends. 

Last, I would like to acknowledge my friends for their neverending work in keeping me sane.
I thank Michelle Hunt for being the most patient person on this planet, and for listening to me complain all of the time.
I would also like to thank Ricky Hussmann, Andrew Matheny, Wesley Corbin  and the rest of the crew for all of those great Thursday nights.

This research was conducted at West Virginia University and 
the Jet Propulsion Laboratory under a contract with the 
National Aeronautics and Space Administration. 
Reference herein to any specific commercial product, process, or service by
trade name, trademark, manufacturer, or otherwise, does not constitute or imply its endorsement
by the United States Government

\singlespacing

\tableofcontents
\listoffigures
%\listoftables
%\pagebreak

\chapter*{Symbols and Abbreviations}
{\bf ACO}: Ant Colony Optimization\\
{\bf AI}: Artificial Intelligence\\
{\bf BDD}: Binary Decision Diagram\\
{\bf DDP}: Defect Detection and Prevention Model\\
{\bf DOD}: Decision Ordering Diagram\\
{\bf DM}: Data Mining\\
{\bf GA}: Genetic Algorithm\\
{\bf HC}: Hill Climbing\\
{\bf JPL}: NASA Jet Propulsion Laboratory\\
{\bf LS}: Local Search\\
{\bf MWS}: MaxWalkSat\\
{\bf OO}: Object-Oriented Programmin\\
{\bf PSO}: Particle Swarm Optimization\\
{\bf QOC}: Questions-Options-Criteria Graph\\
{\bf RS}: Random Search\\
{\bf SA}: Simulated Annealing\\
{\bf SBSE}: Search-Based Software Engineering\\
{\bf SE}: Software Engineering\\
{\bf TS}: Tabu Search\\
{\bf UML}: Unified Modelling Language\\
{\bf VNS}: Variable-Neighborhood Search\\
{\bf WCET}: Worst-Case Execution Time\\

\doublespacing

\chapter{Introduction}\label{chap:intro}
\setcounter{page}{1}
\pagenumbering{arabic}
\input{introduction}

\chapter{Background}\label{chap:bg}
\input{background}

\chapter{Related Work}\label{chap:work}
\input{related-work}

\chapter{Algorithms}\label{chap:algos}
\input{algorithms}

\chapter{Case Studies}\label{chap:exp}
\input{case-studies}

\chapter{Conclusions}\label{chap:conclusion}
\input{conclusion}
\pagebreak

\singlespacing

\addcontentsline{toc}{chapter}{Bibliography}
\bibliography{refs,refsgreg}
\bibliographystyle{plain}

\appendix
\singlespacing

\chapter{Obtaining the System}

We have placed on-line all the  materials required for other
researchers to conduct further investigation into this problem. 
All the code, Makefiles, scripts, and so on used in this paper are available 
at 	 \url{http://unbox.org/wisp/tags/ddpExperiment/install}.  For security reasons, all the available
JPL requirements models have been ``sanitized''; i.e. all words replaced with anonymous  variables.

\chapter{Source Code}
\input{source}

\pagebreak
\thispagestyle{empty}

\end{document}
