% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass[10pt]{llncs}
\usepackage{graphicx}
\usepackage{wrapfig,pifont,url,cite,times}
%
\usepackage{makeidx}  % allows for indexgeneration
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%
\begin{document}
%
\frontmatter          % for the preliminaries
%
%\addtocmark{Hamiltonian Mechanics} % additional mark in the TOC
%
%\chapter*{Preface}
%%
%This textbook is intended for use by students of physics, physical
%chemistry, and theoretical chemistry. The reader is presumed to have a
%basic knowledge of atomic and quantum physics at the level provided, for
%example, by the first few chapters in our book {\it The Physics of Atoms
%and Quanta}. The student of physics will find here material which should
%be included in the basic education of every physicist. This book should
%furthermore allow students to acquire an appreciation of the breadth and
%variety within the field of molecular physics and its future as a
%fascinating area of research.
%
%For the student of chemistry, the concepts introduced in this book will
%provide a theoretical framework for that entire field of study. With the
%help of these concepts, it is at least in principle possible to reduce
%the enormous body of empirical chemical knowledge to a few basic
%principles: those of quantum mechanics. In addition, modern physical
%methods whose fundamentals are introduced here are becoming increasingly
%important in chemistry and now represent indispensable tools for the
%chemist. As examples, we might mention the structural analysis of
%complex organic compounds, spectroscopic investigation of very rapid
%reaction processes or, as a practical application, the remote detection
%of pollutants in the air.
%
%\vspace{1cm}
%\begin{flushright}\noindent
%April 1995\hfill Walter Olthoff\\
%Program Chair\\
%ECOOP'95
%\end{flushright}
%%
%\chapter*{Organization}
%ECOOP'95 is organized by the department of Computer Science, University
%of \AA rhus and AITO (association Internationa pour les Technologie
%Object) in cooperation with ACM/SIGPLAN.
%%
%\section*{Executive Committee}
%\begin{tabular}{@{}p{5cm}@{}p{7.2cm}@{}}
%Conference Chair:&Ole Lehrmann Madsen (\AA rhus University, DK)\\
%Program Chair:   &Walter Olthoff (DFKI GmbH, Germany)\\
%Organizing Chair:&J\o rgen Lindskov Knudsen (\AA rhus University, DK)\\
%Tutorials:&Birger M\o ller-Pedersen\hfil\break
%(Norwegian Computing Center, Norway)\\
%Workshops:&Eric Jul (University of Kopenhagen, Denmark)\\
%Panels:&Boris Magnusson (Lund University, Sweden)\\
%Exhibition:&Elmer Sandvad (\AA rhus University, DK)\\
%Demonstrations:&Kurt N\o rdmark (\AA rhus University, DK)
%\end{tabular}
%%
%\section*{Program Committee}
%\begin{tabular}{@{}p{5cm}@{}p{7.2cm}@{}}
%Conference Chair:&Ole Lehrmann Madsen (\AA rhus University, DK)\\
%Program Chair:   &Walter Olthoff (DFKI GmbH, Germany)\\
%Organizing Chair:&J\o rgen Lindskov Knudsen (\AA rhus University, DK)\\
%Tutorials:&Birger M\o ller-Pedersen\hfil\break
%(Norwegian Computing Center, Norway)\\
%Workshops:&Eric Jul (University of Kopenhagen, Denmark)\\
%Panels:&Boris Magnusson (Lund University, Sweden)\\
%Exhibition:&Elmer Sandvad (\AA rhus University, DK)\\
%Demonstrations:&Kurt N\o rdmark (\AA rhus University, DK)
%\end{tabular}
%%
%\begin{multicols}{3}[\section*{Referees}]
%V.~Andreev\\
%B\"arwolff\\
%E.~Barrelet\\
%H.P.~Beck\\
%G.~Bernardi\\
%E.~Binder\\
%P.C.~Bosetti\\
%Braunschweig\\
%F.W.~B\"usser\\
%T.~Carli\\
%A.B.~Clegg\\
%G.~Cozzika\\
%S.~Dagoret\\
%Del~Buono\\
%P.~Dingus\\
%H.~Duhm\\
%J.~Ebert\\
%S.~Eichenberger\\
%R.J.~Ellison\\
%Feltesse\\
%W.~Flauger\\
%A.~Fomenko\\
%G.~Franke\\
%J.~Garvey\\
%M.~Gennis\\
%L.~Goerlich\\
%P.~Goritchev\\
%H.~Greif\\
%E.M.~Hanlon\\
%R.~Haydar\\
%R.C.W.~Henderso\\
%P.~Hill\\
%H.~Hufnagel\\
%A.~Jacholkowska\\
%Johannsen\\
%S.~Kasarian\\
%I.R.~Kenyon\\
%C.~Kleinwort\\
%T.~K\"ohler\\
%S.D.~Kolya\\
%P.~Kostka\\
%U.~Kr\"uger\\
%J.~Kurzh\"ofer\\
%M.P.J.~Landon\\
%A.~Lebedev\\
%Ch.~Ley\\
%F.~Linsel\\
%H.~Lohmand\\
%Martin\\
%S.~Masson\\
%K.~Meier\\
%C.A.~Meyer\\
%S.~Mikocki\\
%J.V.~Morris\\
%B.~Naroska\\
%Nguyen\\
%U.~Obrock\\
%G.D.~Patel\\
%Ch.~Pichler\\
%S.~Prell\\
%F.~Raupach\\
%V.~Riech\\
%P.~Robmann\\
%N.~Sahlmann\\
%P.~Schleper\\
%Sch\"oning\\
%B.~Schwab\\
%A.~Semenov\\
%G.~Siegmon\\
%J.R.~Smith\\
%M.~Steenbock\\
%U.~Straumann\\
%C.~Thiebaux\\
%P.~Van~Esch\\
%from Yerevan Ph\\
%L.R.~West\\
%G.-G.~Winter\\
%T.P.~Yiou\\
%M.~Zimmer\end{multicols}
%%
%\section*{Sponsoring Institutions}
%%
%Bernauer-Budiman Inc., Reading, Mass.\\
%The Hofmann-International Company, San Louis Obispo, Cal.\\
%Kramer Industries, Heidelberg, Germany
%%
%\tableofcontents
%%
%\mainmatter              % start of the contributions
%
\title{Accurate Estimates Without Calibration?}

%
%
\author{Tim Menzies \inst{1} \and Oussama Elrawas  \inst{1}  \and
Barry Boehm \inst{2}\and Raymond Madachy \inst{2} \and \\
Jairus Hihn\inst{3} \and Daniel Baker\inst{1} \and Karen Lum\inst{3}
\thanks{
This research was conducted at WVU, USC,  and NASA's Jet Propulsion Laboratory partially 
under a NASA 
sub-contract. 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.} }
%
\authorrunning{Menzies et.al.}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Tim Menzies,Oussama Elrawas,Barry Boehm, Ray Madachy}

%
\institute{LCSEE,
West Virginia University, 
Morgantown, WV, USA,
\email{tim@menzies.us}, \email{oelrawas@mix.wvu.edu}, \email{danielryanbaker@gmail.com}
\and
CS,
 University of Southern California,
Los Angeles, California, USA,
\email{boehm@sunset.usc.edu},
\email{madachy@usc.edu}
\and
JPL,  California, USA,
\email{jairus.hihn@jpl.nasa.gov}, \email{karen.t.lum@jpl.nasa.gov}}
 
\pagenumbering{arabic}
\pagestyle{plain}  % switches on printing of running heads
\thispagestyle{empty}
\maketitle              % typeset the title of the contribution

\begin{abstract}
Most process models calibrate their internal settings using historical data.
Collecting this data is 
expensive, tedious, and often an incomplete process.

Is it possible to make accurate software process estimates without
historical data? 
Suppose
 much of uncertainty in a model comes from a small subset
of the model variables. If so, then after (a)~ranking variables
by their ability to constrain the output; and
(b)~applying a small number of the top-ranked variables;
then 
it should be possible to (c)~make
stable predictions
in the constrained space.

To test that hypothesis, we  combined a simulated annealer
(to generate random solutions) with a variable ranker.
The results where quite dramatic: in one of the studies in this 
paper,
we found process options that reduced the median and
variance of the effort estimates by a factor of 20.
In ten case studies, we show that the estimates
generated in this manner are usually similar to those
produced by standard local calibration. 

Our conclusion is that while it is
always preferable to tune models to local data,  it is
possible to learn process control options {\em without} that data.
\end{abstract}
%
\section{Introduction}


Without precise knowledge from an organization, it is difficult
to make precise estimates about software processes at that site.
 For example, initial development effort estimates may be incorrect
by a factor of four~\cite{boehm81} or even more~\cite{kemerer87}.

%% Consequently, for some years now, we have been exploring methods to
%% reduce the uncertainty in model
%% estimation~\cite{me04h,me05a,me05c,me05d,me06d,me06e,me06f,baker07}.  Like
%% other researchers, we have explored data pruning methods: given a
%% table of $V$ variables from $P$ projects, we find a new table $P'*V'$
%% where $P' \subseteq P$ and $V' \subseteq V$.  Pruning is useful since
%% project data collected in one context may not be relevant to another.
%% Similar projects have less variation in their data and so can make
%% better use of local data for the purposes of model calibration.  For
%% example, Chulani et.al.~\cite{chulani99} \& Shepperd and
%% Schofield~\cite{shepperd97} report that intelligently pruning project
%% data improves estimation accuracy.  Similarly, there are many
%% theoretical~\cite{miller02} and experimental
%% results~\cite{me05c,me05d,me06d} showing that intelligently pruning
%% model variables can reduce estimation variance and error.

%% While certainly useful, data pruning still assumes that there is data to prune.
%% This is not always the case.
It can be  very difficult
to find relevant data within a single organization to fully
specify all the internal parameters inside a process model.
For example, after 26 years of trying, we have only collected less
than 200 sample projects for the COCOMO database.
There are many reasons for this, not the least being
 the business sensitivity associated
   with the data.
Therefore, in this paper, we explore what can be decided from process models
 {\em without} local data.

For this experiment, we adopt the following framework.
We say that a process model $P$ yields estimates from
a combination of $Project$ and $Model$ variables:
\[
estimates = P(Project, Model)
\]
$P$ describes the space of influences between variables. 
	    and may take many forms:
\bi
\item
discrete-event models~\cite{law00,kelton02};
\item
system dynamics models~\cite{hamid91}; 
\item
state-based models~\cite{akhavi93,harel90,martin00};
\item
rule-based programs~\cite{mi90}; 
\item standard programming constructs
such as those used in Little-JIL~\cite{cass00,wise00};
\item
or the linear models used in COCOMO~\cite{boehm81,boehm00b},
PRICE-S~\cite{park88} and 
SEER-SEM~\cite{jensen83}.  
\ei
The strength of each influence is controlled
by the $Model$ variables.
Taken together, the process model $P$ and the $Model$ variables store
what we've leaned from the {\em past}. 

$Project$ variables, on the other had,  concern 
a {\em new} situation that should
be analyzed using past knowledge.
For example,
$P$ could assert  ``$effort \propto pcap$''
(programmer skills is proportional to development effort)
while
$Model$ could assert the proportionality constant of  -0.7
(i.e. ``$effort=-0.7pcap$'').
Finally,
$Project$ could assert that programmer skills are ``in the upper range''; e.g. for a COCOMO model
``$pcap \in \{4,5\}$''. 

We say $Project$ and $Model$ variables can be:
\bi
\item  $fixed$ to one value such as ``programmer capability ($pcap$) is nominal'';
\item $free$ to take on any legal value. In COCOMO, a free $pcap$ 
can
take
values \[\{veryLow=1, low=2, nominal=3, high=4, veryHigh=5\}\]
\item or $float$ to some subset of the whole range. 
For example, a manager might declare that ``our programmers
are in the upper ranges''; i.e. this
$pcap$ floats in a particular part of the
entire $pcap$ range 
($pcap \in \{4,5\}$).
\ei
The range of legal values for variables
increases from $fixed$ to $float$ to $free$:
\[\left(|fixed|=1\right) < |float| < |free|\]

This paper reports an experiment that frees {\em both} the $Model$ and
$Project$ variables.  
At first glance, such an experiment may seem perverse, particularly if the goal
is to reduce uncertainty. Free variables range over a larger space
than fixed variables: the more free variables, the wider the range of $Estimates$. If we free
both $Model$ and $Project$ variables then, surely, this will result in  greater $Estimate$
uncertainty?

However, our analysis is not just some passive observer of a large space of options. Instead, it is an active
agent that seeks parts of the options space where predictions can be made with greater certainty.
We augment a Monte Carlo analysis with two tools.
SA is a {\em simulated annealing algorithm} that minimizes   $Estimates$.
RANKER is a {\em variable pruning algorithm},  that seeks the {\em smallest} number of $Project$ 
variables that {\em most} reduce the $Estimates$.
The combination of SA+RANKER is  called STAR\footnote{The name is a geek joke. 
In regular expressions, the star meta-character ``*''
matches any characters. That is, just like STAR,  it can be used to search a wide range of options.}.Since
 it  knows
the most influential $Project$ ranges, 
STAR can discover (and then constrain)  the factors that most most impact   $Estimates$.  



\begin{figure}
{\footnotesize


\begin{center}
\begin{minipage}{.48\linewidth}
\begin{center}
\begin{tabular}{|c|r|r|}\cline{2-3}
\multicolumn{1}{c|}{}&Monte Carlo & STAR\\\hline

case study&SCAT &STAR\\\hline

flight	&712 		&44\\
ground	&389 		&18	\\
OSP	&629 		&68	\\
OSP2	&84		&31	\\\hline
\multicolumn{3}{c}{~}\\
\multicolumn{3}{c}{{\bf Fig 1a:} variance, in months.}\\
\end{tabular}
\end{center}
\end{minipage}\begin{minipage}{.48\linewidth}
\begin{center}
\begin{tabular}{|c|r|r|}\cline{2-3}

\multicolumn{1}{c|}{~}&
\multicolumn{1}{|c}{Monte Carlo}&
\multicolumn{1}{|c|}{STAR}\\\hline

case study &
\multicolumn{1}{|c}{SCAT}&
\multicolumn{1}{|c|}{STAR}\\\hline
flight	&1357 	&86 	\\
ground	&737	&38 	\\
OSP	&1951   	&410 	 \\
OSP2	&297        &182 	\\\hline
\multicolumn{3}{c}{~}\\
\multicolumn{3}{c}{{\bf Fig 1b:} median, in months.}\\
\end{tabular}
\end{center}
\end{minipage}
\end{center}}
\caption{
Effort estimates
seen in 1000 simulations of the $Project$ ranges found by STAR.
``Variance'' (left hand side)
shows the difference between the 75th and 50th percentile.
``Median'' (right hand side)
 shows the 50th percentile estimate. 
 }\label{fig:outv}
\end{figure}


When compared to state-of-the-art process models, the effects
of a STAR-style analysis are quite dramatic.
\fig{outv}  compares STAR's estimates to those
 generated by
SCAT~\cite{lum02,lum03handbook,lum05scat}, a COCOMO-based tool used at
NASA's Jet Propulsion Laboratory. SCAT fixes $Model$ and perform a
Monte Carlo simulation of the $Project$ ranges. 
%% In comparisons with other estimation tools~\cite{lum02}, the SCAT approach
%% was found to be more accurate than SEER-SEM,
%% and insignificantly different to PRICE-S.
%% Lum et.al. prefer SCAT to PRICE-S since, they argue,  SCAT makes it easier
%% to 
%% to understand how  specific inputs impact the estimated cost~\cite{lum02}.
Each row of \fig{outv}.A  is one case study:\bi
\item $flight$ and $ground$ systems software from
NASA's Jet Propulsion Laboratory; 
\item $OSP$ is the GNC\footnote{GNC= guidance, navigation,
and control} for NASA's Orbital
Space Plane (prototype); 
\item $OSP2$ is a newer version of OSP.  
\ei
 Note that, for all four case
studies, STAR reduces the variance and median estimates
to a small fraction of SCAT's
estimates, sometimes as much as a factor of 20 (in Figure 1a:
$\frac{712}{44}\approx 20$; in Figure 1b:
$\frac{737}{38}\approx 20$).


The rest of this paper describes STAR. We
extend prior work in two ways.
Prior reports on STAR~\cite{me07f}  were based on  limited case studies; here we report
ten new case studies showing that our main effect (reduced median and variance)
holds in a wide range of cases.
Also, prior reports on  \fig{outv}~\cite{me07g}
failed to check the validity of those results. The ten case studies
discussed below show that STAR's estimated are shown
to be close to those generated via standard local calibration, 
despite being generated
from a large space of $Project$ and $Model$ options.
This validity check greatly increases our confidence in the STAR method.

It is unknown if our results apply to software process models more
complex than STAR's COCOMO-style of models. However,
our results to date suggest that other process models could make
reasonably accurate predictions without local data by:
\bi
\item finding the fewest number of variables that most effect model output;
\item constrain them;
\item check for stable conclusions in the constrained space.
\ei


\section{Related Work}


In terms of the framework of this paper, related work may be divided into:
 \bi
 \item {\em Prediction}:
 fix $Model$ and $Project$ and generates  fixed $estimates$.
 \item {\em Calibration}:
 import an  log of
 fixed   $estimates$ and $Project$ variables, find
 fixes to $Model$ that best explain how $Project$ inputs lead to $estimation$ outputs.
 \item {\em Monte Carlo} studies:
 fix the $Model$ values (perhaps to values learned via calibration),
 import floating $Project$ values, generates a range of possible 
 $estimates$. 
 \ei
 In the field of effort estimation:
 \bi
 \item
 {\em Prediction} is used to create one point estimate for a project;
 e.g. COCOMO~\cite{boehm81,boehm00a},PRICE-S~\cite{park88} and 
 SEER-SEM~\cite{jensen83}.  
 \item
 {\em Calibration} is useful for learning from historical data; e.g. see Boehm's
 local calibration procedure~\cite[p526-529]{boehm81} 
 or the COSEEKMO toolkit~\cite{me06d}.
 \item
 {\em Monte Carlo} studies are useful for conducting what-if queries across a
 range of possible projects~\cite{raffo99}. Such Monte Carlo
 studies are conducted by many tools including
 COBRA~\cite{briand98},
 CrystalBall~\cite{bailey02},
 SCAT~\cite{lum03handbook,lum05scat}, and
 2CEE~\cite{baker07}. 
 \ei

 To the best of our knowledge, this work is the first to try freeing
 {\em both} the $Project$ and $Model$ variables. 
 Even in the field
 in {\em search-based software engineering}, we have not seen anything like
 this study. It is true that search-based SE often uses non-liner search
 methods like SA. A recent review of 123 search-based SE
 papers~\cite{rela04} showed that much of that work relates to testing
 (e.g. SA to minimize test suites for regression
 testing) while only a handful of those papers related to the kinds of early
 project process planning discussed here.  For example, Aguilar-Ruiz
 et.al.~\cite{aguilarevolutionary} and Alvarez
 et.al.~\cite{alvarez-data} apply search-based methods for effort
 estimation.  One facets that distinguished STAR from other methods is
 that we are searching over more than just the
 effort models explored by the 
 Aquilar-Ruiz \& Alvarez teams. Also, unlike standard data mining approach,
 we  do not try to learn better $Model$ variables from historical data.






\section{STAR}
STAR's current implementation explores three software process models:

\bi
\item
The COQUALMO software defect predictor~\cite[p254-268]{boehm00b}.
\item
The COCOMO software effort predictor~\cite[p29-57]{boehm00b}.  
\item
The THREAT predictor for  project effort \& schedule
overrun~\cite[284-291]{boehm00b}. 
\ei

COQUALMO models two processes (defect introduction and defect removal)
for three phases (requirements, design, coding).  COCOMO assumes that
effort is exponentially proportional to some {\em scale factors} and
linearly proportional to some {\em effort multipliers}.  COCOMO
estimates are development months (225 hours) and includes all coding,
debugging, and management activities.  The THREAT model contains a
large set of two-dimensional tables representing pairs of variable
settings are problematic. For example, using the $rely$ vs $sced$
table, the THREAT model would raise an alert if our tool decides to
build a system with high $rely$ (required reliability) and low $sced$
(schedule available to the development).






%% %% Alexei Lapouchnian, Yijun Yu, John Mylopoulos: Requirements-Driven Design and Configuration Management of Business Processes. BPM 2007: 246-261
%% %% exploring goal graphs

%% %% Yuan An, John Mylopoulos, Alexander Borgida: Building Semantic Mappings from Databases to Ontologies. AAAI 2006
%% %% golog framework


STAR samples the space of possibles models inside COCOMO and COQUALMO using the following 
technique.
Internally, COCOMO and COQUALMO models contain many
linear relationships.
Nominal values of $x=3$ change some estimate by a factor of one.
These COCOMO lines can hence be
 modeled as a straight line $y = mx + b$ passing 
through the point 
${x, y}={3, 1}$. 
Such a line has a y-intercept of 
$b = 1 - 3m$. Substituting this value of $b$ into $y = mx + b$ yields
$y=m(x-3)+1$. COCOMO's effort slopes are either positive or negative, 
denoted $m^+$, $m^-$ (respectively):
\bi
\item
The positive slopes $m^+$
represents the variables that are proportional to effort; e.g.
$increasing$ required reliability also $increases$ the development effort.
\item
The negative
slopes $m^-$
represents the variables that are 
{\em inversely} proportional to effort; e.g.
$increasing$ analyst capability
		 $decreases$ the development effort.
\ei
Based on decades of experiments with calibrating COCOMO models, we have identified
variables with different slopes.
These following COCOMO variables  have $m^+$ slopes:
cplx,
data,
docu,
pvol,
rely,
ruse,
stor, and
time. Also, these variables  have $m^-$ slopes
acap,
apex,
ltex,
pcap,
pcon,
plex,
sced, and
site (for an explanation of those terms,
see \fig{emsf2}). Further, based on decades of calibration of COCOMO models,
we assert that 
 effort estimation, $m^+$ and $m^-$ have the ranges:
\begin{equation}\label{eq:mm}\scriptsize
\begin{array}{c}
 -0.178 \le m^- \le -0.078\\
0.073 \le m^+ \le 0.21
\end{array}
\end{equation}
Using an analogous procedure, it is possible
to derive similar equations 
for  the COCOMO scale factors,
the COQUALMO scale factors/effort multipliers/ defect removal
variables
(for full details, see~\cite{me07f}). 





\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{p{3cm}|r@{:~}l|c|c|}
\multicolumn{3}{c}{~}&strategic?&\multicolumn{1}{|c}{tactical?}\\\cline{2-5}
scale   &prec & have we done this before?&\ding{51}&\\
factors &flex & development flexibility &&\ding{51}\\
(exponentially        &resl & any risk resolution activities?&&\ding{51}\\ 
decrease       &team &  team cohesion&&\ding{51}\\ 
effort)       &pmat & process maturity&\ding{51}&\\\hline 
upper  &acap & analyst capability&\ding{51}&\\
(linearly       &pcap & programmer capability&\ding{51}&\\ 
decrease      &pcon & programmer continuity&\ding{51}&\\
effort)       &aexp &  analyst experience&\ding{51}&\\       
&pexp &  programmer experience&\ding{51}&\\       
&ltex &  language and tool experience&\ding{51}&\\       
&tool &  tool use&&\ding{51}\\       
&site &  multiple site development&\ding{51}&\\       
&sced & length of schedule  &&\ding{51} \\\hline 
lower &rely &    required reliability && \\
(linearly      &data &   secondary memory  storage requirements&&\ding{51}\\
increase      &cplx &  program complexity&&\ding{51}\\
effort)      &ruse &  software reuse&&\ding{51}\\      
&docu &   documentation requirements&&\ding{51}\\      
&time &   runtime pressure&&\\      
&stor &   main memory requirements&&\ding{51}\\     
&pvol &    platform volatility  &&\\\hline
COQUALMO &auto& automated analysis&\ding{51}&\ding{51}\\
defect removal&execTest & execution-based testing tools&\ding{51}&\ding{51}\\
methods&peer& peer reviews&\ding{51}&\ding{51}\\\cline{2-5}
\end{tabular}}
\end{center}
\caption{The variables of COCOMO, COQUALMO, and the THREAT model.}\label{fig:emsf2}
\end{figure}

With the above machinery, it is now possible to define
a Monte Carlo procedure to sample the space of possible
THREAT/COCOMO/COQUALMO $Models$: just
 randomly selecting $\{m^-,m^+\}$.
As to sampling the space of possible
THREAT models, this is achieved by adding  random variables
to the cells of THREAT's  tables.

STAR tries to minimize  defects ($D$), threats ($T$), and 
development effort ($E$).
 This is a non-linear optimization function: e.g. reducing costs can introduce more defects. For this reason, we use simulated annealing (SA) to explore trade-offs between models. 
SA is best explained in comparison to  the Metropolis
algorithm. 


A  {\em Metropolis} Monte Carlo algorithm~\cite{metropolis53}
improves on basic Monte Carlo as follows.
New solutions are created
by  small mutations to some
{\em current} solutions. 
In the case of STAR, an  ``solution'' is some randomly selected
part of the space of possible $Projects$.
If a new solution is ``better'' (as assessed via an
{\em energy function}),  it becomes the new {\em current}
solution used  for future
mutations.  
STAR's energy function is 
\mbox{$E=\sqrt{\overline{E}^2 + \overline{D}^2 + \overline{T}^2} / \sqrt{3}$}
where $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Energy ranges $0 \le E \le 1$ and
{\em lower} energies are {\em better}.
If a new solution does not have lower energy, a Boltzmann acceptance
criteria is used to probabilistically decide to
assess the new state: the worse the new state, the less
likely that it becomes the new current state.

A {\em simulated annealer} (SA)~\cite{kirkpatrick83}
adds
a ``temperature'' variable to the Boltzmann accept criteria
such that, at high temperatures, it is more likely that the
algorithm will jump to a  new worst current state.
This allows the algorithm to jump out of local minima while
sampling the space of options. As the temperature cools,
such jumps become less likely and the algorithm reverts
to a simple hill climber.
 
Our {\em RANKER} algorithm instruments the internals of SA.
Whenever a solution is assigned some energy, that energy
is added to a counter maintained
for each variable setting in $Projects$.  When SA terminates,
RANKER
sorts all variable ranges by the sum of the energies seen during
their use. The ranges that are lower in the sort order are associated
with lower energy solutions; i.e. lower defects, efforts, threats.
RANKER then conducts experiments where it fixes the first $N$ ranked
ranges and lets the remaining variables float. $N$ is increased
till some minimum energy point is reached. A {\em policy} are the project
settings that achieve that minimum energy point.

The last two columns of \fig{emsf2} 
show the results of  Delphi panel session at JPL where the COCOMO variables
were separated into those $tactical$ variables
that can be changed within the space of one project,
and those $strategic$ variables
that required higher-level institutional change (and so may take
longer to change). For example, the panel declared that $pmat$ (process maturity)
is hard to change within the space of a single JPL project. 
In the sequel, all our RANKER experiments will be divided into those that
just use the $strategic$ variables and those that just use the $tactical$
variables\footnote{Note that these definitions of $strategic$ and $tactical$ choices
are not hard-wired into STAR. If a user disagrees with our definitions of
strategic/tactical, they can change a simple configuration file.}.

\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{minipage}{.45\linewidth}\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{float}      &\multicolumn{2}{c}{fixed}\\\hline
project&variable&low&high&variable&setting\\\hline
&prec&1&2&data&3\\
OSP&flex&2&5&pvol&2\\
&resl&1&3&rely&5\\
&team&2&3&pcap&3\\
&pmat&1&4&plex&3\\
&stor&3&5&site&3\\
&ruse&2&4&&\\
&docu&2&4&&\\
&acap&2&3&&\\
&pcon&2&3&&\\
&apex&2&3&&\\
&ltex&2&4&&\\
&tool&2&3&&\\
&sced&1&3&&\\
&cplx&5&6\\
&KSLOC&75&125\\
\hline
&prec&3&5&flex&3\\
OSP2 &pmat&4&5&resl&4\\
&docu&3&4&team&3\\
&ltex&2&5&time&3\\
&sced&2&4&stor&3\\
&KSLOC&75&125&data&4\\
&&&&pvol&3\\
&&&&ruse&4\\
&&&&rely&5\\
&&&&acap&4\\
&&&&pcap&3\\
&&&&pcon&3\\
&&&&apex&4\\
&&&&plex&4\\
&&&&tool&5\\
&&&&cplx&4\\
&&&&site&6
\end{tabular}
\end{minipage}~~~~~~~~\begin{minipage}{.45\linewidth}
\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{float}      &\multicolumn{2}{c}{fixed}\\\hline
project&variable&low&high&variable&setting\\\hline
&rely&3&5&tool&2\\
 &data&2&3&sced&3\\
flight&cplx&3&6&&\\
&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&7&418&&\\
\hline
&rely&1&4&tool&2\\
 &data&2&3&sced&3\\
ground&cplx&1&4&&\\
&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&11&392&&\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}


\end{tabular}
\end{minipage}
\end{center}
\caption{Four case studies.}\label{fig:cases}
\end{figure}
\section{Experiments}

\fig{cases} shows various $Projects$ expressed in term of $float$ing
and $fixed$ variables. For example, with JPL's flight systems,
the $rely$ (required reliability) can float anywhere in the upper range;
i.e. $rely\in\{3,4,5\}$. However, for flight systems, $sced$ (schedule pressure)
is tightly defined (so $sced$ is fixed to the value 3).

\begin{figure}[!t]
\begin{minipage}{.5\linewidth}
\begin{center}
%%%%%%%%%\includegraphics[width=2.4in]{OSP/strategic/Energy.pdf} 
%\includegraphics[width=2.4in]{OSP/strategic/Defects.pdf} 
%\includegraphics[width=2.4in]{OSP/strategic/Effort.pdf} 
%%%%%%%%\includegraphics[width=2.4in]{OSP/strategic/Threat.pdf} 
%%%%%\includegraphics[width=2.4in]{OSP/strategic/Months.pdf} 
{\scriptsize
\begin{tabular}{r|r@{~=~}l}
X& variable & setting\\\hline
1&pmat&4\\
2&ltex&4\\
3&acap&3\\
4&apex&3\\
5&prec&2\\
6&pcon&3\\
7&execution testing and tools&6\\
8&peer reviews&6\\
9&automated analysis&6\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{{\bf Fig.\ref{fig:rrr}.A:}
controlling only strategic $Project$ variables}
\end{tabular}
}
\end{center}
\end{minipage}\begin{minipage}{.5\linewidth}
\begin{center}
%%%%%%%%%\includegraphics[width=2.4in]{OSP/tactical/Energy.pdf} 
%\includegraphics[width=2.4in]{OSP/tactical/Defects.pdf} 
%\includegraphics[width=2.4in]{OSP/tactical/Effort.pdf} 
%%%%%%%%%\includegraphics[width=2.4in]{OSP/tactical/Threat.pdf} 
%%%%%%%%%%\includegraphics[width=3.2in]{OSP/tactical/Months.pdf} 
{\scriptsize
\begin{tabular}{r|r@{~=~}l}
X& variable & setting\\\hline
1&ruse&2\\
2&cplx&5\\
3&resl&3\\
4&tool&3\\
5&sced&2\\
6&stor&3\\
7&flex&5\\
8&automated analysis&6\\
9&peer reviews&6\\
10&docu&2\\
11&execution testing and tools&6\\
12&sced&1\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{{\bf Fig.\ref{fig:rrr}.B:}
controlling only tactical $Project$ variables}
\end{tabular}
}
\end{center}
\end{minipage}
\caption{Some RANKER results on OSP. The settings shown under the plots
describe the policy that leads to the policy point.}\label{fig:rrr}
\end{figure}
\begin{figure}
\begin{minipage}{.5\linewidth}
\begin{center}
%%%%%%%%\includegraphics[width=2.4in]{ground/strategic/Energy.pdf} 
%\includegraphics[width=2.4in]{ground/strategic/Defects.pdf} 
%\includegraphics[width=2.4in]{ground/strategic/Effort.pdf} 
%%%%%%%\includegraphics[width=2.4in]{ground/strategic/Threat.pdf} 
%%%%%%%\includegraphics[width=2.4in]{ground/strategic/Months.pdf} 
{\scriptsize
\begin{tabular}{r|r@{~=~}l}
X& feature & range\\\hline
1&pmat&3\\
2&site&6\\
3&pcon&5\\
4&plex&4\\
5&pcap&5\\
6&ltex&4\\
7&apex&5\\
8&prec&5\\
9&acap&5\\
10&automated analysis&6\\
11&execution testing and tools&6\\
12&peer reviews&6\\
13&acap&4\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{{\bf Fig.\ref{fig:yyy}.A:}
controlling only strategic $Project$ variables}
\end{tabular}
}
\end{center}
\end{minipage}\begin{minipage}{.5\linewidth}
\begin{center}
%%%%%%%\includegraphics[width=2.4in]{ground/tactical/Energy.pdf} 
%\includegraphics[width=2.4in]{ground/tactical/Defects.pdf} 
%\includegraphics[width=2.4in]{ground/tactical/Effort.pdf} 
%%%%%%\includegraphics[width=2.4in]{ground/tactical/Threat.pdf} 
%%%%%%\includegraphics[width=2.4in]{ground/tactical/Months.pdf} 
{\scriptsize
\begin{tabular}{r|r@{~=~}l}
X& feature & range\\\hline
1&resl&5\\
2&cplx&1\\
3&execution testing and tools&6\\
4&flex&5\\
5&docu&1\\
6&ruse&2\\
7&data&3\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{{\bf Fig.\ref{fig:yyy}.B:}
controlling only tactical $Project$ variables.}
\end{tabular}
}
\end{center}
\end{minipage}
\caption{Some RANKER  results on JPL ground systems.
The settings shown under the plots.
describe the policy that leads to the policy point.
}\label{fig:yyy}
\end{figure}


\fig{rrr} and \fig{yyy}
shows the results of STAR.
The variable ranges are sorted along the x-axis according the order
generated by RANKER. 
At any $x$ value we see the results of fixing the ranges $1..x$, letting
all ranges $x+1... max$ float,
then
running 1000 Monte Carlo simulations. In the results, ``median'' refers
to the 50th percentile band and ``spread'' refers to the difference
between the 75th and 50th percentile in the 1000 generate estimates.


For this paper, we ran SA+RANKER on the four case studies
of \fig{cases}, plus a fifth study called ``ALL'''' that
used the entire COCOMO ranges,
unconstrained by a particular project. Each study was repeated
twice- one for controlling just the strategic variables
and once for controlling just the tactical variables.
This resulted in ten experiments.

Some of the results from four of those experiments are shown in \fig{rrr}
and \fig{yyy} (space restrictions prevent us from showing all the results).
In those four
experiments
 (and in the other six,  not shown) the same effect was observed.
Minimum effort and defects was achieved after fixing
a small number of $Project$ variables
(in 
 \fig{rrr}.A, \fig{rrr}.B, \fig{yyy}.A, and \fig{yyy}.B,
that number was
at X=\{9,12,13 7\} respectively).
 At these minimum
points, the median and spread estimates were greatly reduced.
We call this minimum the $policy point$ and use
the term $policy$ to refer
to  the intersection of the case study defined in \fig{cases},
and the ranges found in the range between 
$\{1 \le x \le policy point\}$.

\fig{rrr} and \fig{yyy} are the reports we would offer back to the
manager.  Start at the top of this list, we would advise, and apply
as many oft eh top $N$ things that you can. Do not waste time
implementing policy changes off this list.

In terms of controlling
uncertainty, the reduction in the spread estimates
at the policy point
is particularly interesting.
Note that this reduction in model uncertainty
was achieved by only
controlling a few of the $Project$ variables while
letting all other $Project$ and $Model$ variables float free.
That is, in these case studies, projects could be controlled
(development effort and defects reduced) without using
historical data to constrain the $Model$ variables.

For each of our ten experiments,
a set of random $Projects$ were generated, consistent
with the policies; i.e. 
\bi
\item
If the policy fixes a value, then the $Project$ contains that value;
\item
Otherwise, if the variable is found \fig{cases}, it is drawn from those constraints;
\item
Otherwise, the variable's value is selected at random from background knowledge of the legal range of the \fig{emsf2} variables.
\ei
For each set, the following procedure was repeated 20 times.
Ten examples were removed at random and Boehm's local calibration (LC) procedure~\cite[p526-529]{boehm81}  was
used to train a COCOMO model on the remaining $Project$ 
examples\footnote{LC was chosen since, in extensive experiments,
we have found this decades old procedure to be 
remarkably competitive with current data mining methods~\cite{jalali07}
including bagging and boosting~\cite{baker07}.}. LC's estimates were then compared to the estimates generated by
STAR's simulation at the policy point (i.e. floating over both the policy and the $Model$ ranges). 
\fig{deltas} show the median difference in the 
 estimates generated
by LC or STAR . Note that, in $\frac{8}{10}$
cases, the difference is under 50\%. 
The reason for the large deltas seen in $\frac{2}{10}$ of the
results (from the OSP case study)
are currently unknown but
are a subject of much current exploration.
%\begin{figure}
%\begin{center}
%\includegraphics[width=1.5in]{graphs/OSP2-tactical.pdf}    %  34.8
%\includegraphics[width=1.5in]{graphs/ALL-strategic.pdf}    %  35
%\includegraphics[width=1.5in]{graphs/OSP2-strategic.pdf}   %  35.1
%\includegraphics[width=1.5in]{graphs/flight-tactical.pdf}  %  35.6
%\includegraphics[width=1.5in]{graphs/ground-tactical.pdf}  %  37.3
%\includegraphics[width=1.5in]{graphs/ALL-tactical.pdf}     %  41
%\includegraphics[width=1.5in]{graphs/flight-strategic.pdf} %  42.1
%\includegraphics[width=1.5in]{graphs/ground-strategic.pdf} %  49
%\includegraphics[width=1.5in]{graphs/OSP-tactical.pdf}     % 112.1 
%\includegraphics[width=1.5in]{graphs/OSP-strategic.pdf}    % 146.5
%\end{center}
%\caption{Effort estimates generated by LC (thin line) and 
%STAR (fat line). The ten plots are sorted in order of the median differences
%(shown in \fig{deltas}. Within in each plot,
%the results are sorted by the size of estimated offered by LC
%(the thin line).
%}\label{fig:group1}
%\end{figure}

\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{tabular}{l|c|rl}
cast study&~control method &~~ $\delta$ \%  & \\\hline
OSP2&tactical&34&\rule{15mm}{2mm}\\
All&strategic&35&\rule{15mm}{2mm}\\
OSP2&strategic&35&\rule{15mm}{2mm}\\
flight&tactical&36&\rule{18mm}{2mm}\\
ground&tactical&37&\rule{18mm}{2mm}\\
All&tactical&41&\rule{20mm}{2mm}\\
flight&strategic&42&\rule{21mm}{2mm}\\
ground&strategic&49&\rule{24mm}{2mm}\\
OSP&tactical&112&\rule{56mm}{2mm}\\
OSP&strategic&147&\rule{74mm}{2mm}
\end{tabular}
\end{center}
\caption{Median 
 $\delta=(estimate(STAR) - estimate(lc))$
between effort
estimates generated by conventional means (LC)
and STAR.}\label{fig:deltas}
\end{figure}


The median $\delta$ values of \fig{deltas} are around 
0.4; i.e. a STAR estimate of 100 months
could really range for 60 to 140 months.
Compared to
the effort estimate reductions shown in the  introduction, $\delta$ 
is quite small.
Recall that STAR reduced effort estimates to a small part of the initial values, sometimes
a factor of 20; i.e by  a factor that is much larger than 0.4. Clearly,
even if STAR is wrong by $\pm 40$\%, then the overall benefits to be gained from applying
STAR's policies are  still
dramatically large.

 % ---- Bibliography ----
%

\section{Discussion}
Given all the randomized exploration
STAR performs over the space of possible $Models$, this discrepancy is very small.
and 
those discrepancies are dwarfed 
by the much larger  effort reductions of Figure 1.

How are we to  explain the remarkable effectiveness of STAR in
managing uncertainty?
Researchers in planning and theorem proving have
recently shown that as model complexity grows, other constraining
effects may appear such as ``master variables''; i.e. a small number
of settings that control all other
settings~\cite{crawford94,williams03}. Such master variables can
greatly reduce the search space within large models.  

 We hypothesize that software process models also contain master variables;
i.e. much 
 much of uncertainty in a model is due to the influence of a 
small subset
of model variables. If so, then after (a)~ranking variables
by their ability to constrain the output; and
(b)~applying a small number of the top-ranked variables;
then 
it should be possible to (c)~make
stable predictions
in the constrained space.
\section{Conclusion}


In studies with one widely-used suite of effort/ detect/ threat predictors 
for software systems, we have shown that:
\bi
\item 
$Estimation$ median values can be greatly reduced (see Figure 1). In comparisons with other effort
estimation tools, the reduction can quite dramatic. In the best case our tools found
$Project$ ranges that yields estimates that were 5\% of estimates found by other means.
\item $Estimation$ variance can be reduced by only floating the $Project$ values and leaving the $Model$ values free (see \fig{rrr} and \fig{yyy}).
\item
Within the space of $Project$ options that most reduce $Estimation$ median and variance, the
predictions made by our process models are remarkably similar to those made by 
conventional methods (see \fig{deltas} ). 

\ei


The
first result suggests that it may be highly advantageous to use STAR.
Projects designed around STAR's recommendations will be
will be
delivered sooner and have fewer bugs or threats.


The second result is of much practical importance  since it means
we do not require calibration data to tune the $Model$ variables. 
If process models can be deployed without calibration, then they
can be used with much greater ease and {\em without} the requirement for an expensive and time-consuming period
of data collection.

The third result is showing that (a)~this method can find and remove the major sources of uncertainty in a project;
(b)~in the reduced space, it is possible that the estimates
in the resulting constrained space will be close
to estimates found via tuning on historical data.
In the above discussion section, we commented that this result
has precedent in the AI planning and  theorem proving literature.

Finally, we comment on the external validity of these results.
Compared to many other process models\footnote{See
 Software Process journal,  issue on Software Process Simulation,
vol. 7, No. 3-4,  2002.} this combination of  effort/threat/defect models is relatively simple.
As model complexity grows, then the space of possible $Estimates$ can grow exponentially and STAR's
controlling effect may disappear. 
Therefore it is clear that   we can not claim that, for {\em all}
process models, that
$Estimate$ variance can be controlled by just constraining $Project$, not
$Model$, variance.

Nevertheless, data collection for the purposes of model calibration remains
as  a
expensive, tedious, and often incomplete process.
Our results suggest that such data collection may be, for some process models,
an optional activity (caveat: provided that a process model exists that
specifics the general relationships between concepts in a domain).
Our hope is that the results of this paper
encouraging enough that other software process modeling researchers
will try the following strategy. {\em First},
find the fewest number of variables that most effect model output.
{\em Next},
constrain them. {\em Finally},
check for stable conclusions in the constrained space.

If these results from STAR generalize to more complex models,
then is should be possible to make reasonably accurate
predictions without local calibration data.

Note that if such stability is {\em absent} in more complex models,
and those models are being used in domains with data collection problems,
then we would argue that that is a reason to abstain from such complexity,
and use COCOMO-style models instead.

\bibliographystyle{acm}
\bibliography{refs}
%% \newpage
%% \appendix
%% \section{Simulated Annealing}
%% A {\em Monte Carlo} algorithms randomly sample the space
%% of possible controllable model states. 
%% A  {\em Metropolis} Monte Carlo algorithm~\cite{metropolis53}
%% creates new states
%% by  small mutations to some
%% {\em current} state. 
%% If a new state is ``better'' (as assessed via an
%% {\em energy function}),  it becomes the new {\em current}
%% state used  for future
%% mutations.  Otherwise, a Boltzmann acceptance
%% criteria is used to probabilistically decide to
%% assess the new state: the worse the new state, the less
%% likely that it becomes the new current state.
%% The algorithm is silent on the mutation mechanism.
%% In our implementation of this algorithm, we only randomized $\frac{1}{3}$ of the
%% attributes being sampled during each iteration of the algorithm. Note that
%% the attributes being randomized are different for consecutive iterations.

%% In 1983, Kirkpatrick et.el.~\cite{kirkpatrick83} 
%% proposed a modification that was
%% inspired
%% by a procedure used to make the strongest possible glass. Initially,
%% glass is heated to allow atoms to move freely. The temperature
%% is then slowly lowered such that the atoms can find the stablest
%% configuration with lowest energy. 
%% A {\em simulated annealing} (SA) algorithm adds
%% a ``temperature'' variable to the Boltzmann accept criteria
%% such that, at high temperatures, it is more likely that the
%% algorithm will jump to a  new worst current state.
%% This allows the algorithm to jump out of local minima while
%% sampling the space of options. As the temperature cools,
%% such jumps become less likely and the algorithm reverts
%% to a simple hill climber.

%% Formally, the acceptance criteria $P$ for a new state is defined using
%% the current temperature $T$, 
%% the energy of the current solution ($e$),
%% and the energy of the new mutation ($en$):
%% \begin{equation}\small
%% P(e,en,T) = e^{(e -en)/T}
%% \end{equation}
%% $T$ is defined to $decrease$ as the simulator loops through $k= 1\ldots kmax$ iterations.
%% We use
%% $T = e^{-100*k/kmax}$, where $kmax$ used in our implementation is 1000, which is a number of iterations determined to produce stable solutions in our implementation of the algorithm and for our intents and purposes.

%% The following pseudo-code {\tt sample} describes our simulated
%% annealer. 
%% A new solution $sn$ (with new energy $en$) replaces the current solution                                  
%% if (a)~it has a lower energy or (b)~the acceptance predicate $P$
%% endorses it. Only in the case of (a)
%% should the new solution
%% replaces the current best solution.

%% {\scriptsize\begin{verbatim}
%% function sample 
%%   s := s0; e := E(s)                       // Init state, energy.
%%   for t in 1 to tmax                       // temperature control
%%   do   sn = randomly change 1/3 of 's'     // Pick neighbor.
%%        en := E(sn)                         // Compute energy.
%%        for x in sn   
%%             out[x] += en                   // record project settings
%%        if P(e,en,temp(t/tmax)) > random()  // is it better?
%%        then 
%%              s := sn;                      // new solution
%%              e := en                       // new best energy
%%   done                                		 
%%   return out, sorted ascending  by en
%% \end{verbatim}}

%% The {\tt sample} function returns an array whose keys are the $Project$
%% settings and the values are the sum of the energies seen when that
%% setting was used. This array is sorted in increasing order so
%% the first entries were associated with lower (and better) energies while
%% the later entries are associated with higher (and less desirable) energies.

%% The {\tt rank} function  takes this array and experiments with 
%% using just the first $I$ items:

%% {\scriptsize\begin{verbatim}
%% function rank(order)
%%    for I in order
%%    do  cache=();                           // clear old results
%%        for n = 1 to 1000
%%        do  sn = random settings            // pick anything at all
%%       	    for j = 1 to I                  // insert the first I things
%%                sn[I] = order[I]
%%            cache[n]= E(sn)                 // score it
%%        done
%%        sort cache                          // sort
%%        print  cache[500]                   // print 50% (median)
%%        print  (cache[750] - cache[500])    // print 75% (spread)
%%    done
%% \end{verbatim}}
%% By plotting the {\tt print} statements in {\tt rank}, \fig{u} is generated.



\end{document}
