%// constrains ATTRIBUTE to a single RANGE and generates a score
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
 1 function run (AllRanges, ProjectConstraints) {
 2   OutScore = -1
 3   P = 0.95
 4   Out = combine(AllRanges, ProjectConstraints)
 5   Options = all Out features with ranges low < high
 6   while Options {
 7     X = any member of Options, picked at random
 8     {Low, High} = low, high ranges of X
 9     LowScore = score(X, Low)
10     HighScore = score(X, High)
11     if LowScore < HighScore
12       then Maybe = Low;  MaybeScore = LowScore
13       else Maybe = High; MaybeScore = HighScore
14     fi
15     if MaybeScore < OutScore or P < rand()
16       then delete all ranges of X except Maybe from Out
17       delete X from Options
18       OutScore = MaybeScore
19     fi
20   }
21  return backSelect(Out)
22 }
23 function score(X, Value) {
24   Temp = copy(Out)  ;; don't mess up the Out global 
25   from Temp, remove all ranges of X except Value 
26   run monte carlo on Temp for 100 simulations
27   return median score from monte carlo simulations
28 }
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for SEESAW.}
\label{fig:MWF}
\end{figure}

Before describing SEESAW in detail, we offer a quick high-level sketch of the algorirthm:
\bi
\item Given a model that can generate a score;
\item Given a project description comprising a set of $Options$
for all project features;
\item Given a tuning description compring a set of ranges for
all model tunings;
\item Let the {\em treatment} be a constraint (a subset) on the project $Options$, found as follows:
\be
\item Initialize the treatment to the empty set;
\item Select some feature not in the treatment;
and reduce
its options to a single value.
\item Using the model, test the current treatment  with that added option.
100 times, pick random values for the tunings as well
as any project features not in the treatment.
\item Usually, reject the feature if it does not improve the score.
\item Sometimes, accept the feature (just to allow limited exploration
of new options).
\item Move the accepted feature to the treatment.
\item Go to 2
\ee
\item After all features are in the treatment, apply a {\em back select} (described below)
to prune the treatment.
\item Return the pruned treatment.
\ei
SEESAW gets it name from step 2 (reducing the options to a single value). 
On experimentation, we found that the most interesting 
interesting ranges in options
were usually  the minimum and maximum values.  The reason for this is simple:
All the functions in COCOMO/COQUALMO are  monotonic, causing
the most dramatic effects to occur at the extreme ends of the ranges.
We have conducted experiments with other approaches that allow
intermediate values.
On comparison with the simulated annealing method used
in a prior publications~\cite{me07f}, we found that
seesawing between
$\{Low,High\}$ values was adequate for our purposes.



\begin{figure}[!t]
\scriptsize
\begin{center}
\includegraphics[width=3in]{plots/single-seesaw-tpts100-all-trio-2-1.pdf}
\end{center}
Decisions made from X=1 to X=13: 

\begin{tabular}{p{0.2\linewidth}p{0.35\linewidth}p{0.35\linewidth}}
&
\bi
\item[1.] pmat = 3
\item[2.] resl = 4 
\item[3.] team = 5
\item[4.] aexp = 4 
\item[5.] docu = 3
\item[6.] plex = 4
\item[7.] rely = 3 
\ei
&
\bi
\item[8.] stor = 3 
\item[9.] time = 3 
\item[10.] tool = 4 
\item[11.] sced = 2 
\item[12.] site = 4
\item[13.] acap = 5
\ei
\end{tabular}
\caption{Results of single run of SEESAW. In the plot at top the  search grows left to right along the x-axis
(each line shows median results from 100 simulations). 
The numbered shows the constraints added at each x-axis point.
For example, at x=3, the constraint were \{pmat=3 and resl=4 and team=5\}.}
\label{fig:run}
\end{figure}
\fig{MWF} shows SEESAW's pseudo-code. The code is an adaption 
of Kautz \& Selman's MaxWalkSat local search procedure~\cite{kautz97}. 
The main changes are that  
each solution  is scored via a Monte Carlo  procedure (see {\tt score} in \fig{MWF}) and that
SEESAW seeks to {\em minimize} that score (since, for our models it is some combination of
defects, development effort, and development time).
Other changes are discussed below.

SEESAW
first combines the ranges for 
all the COCOMO features
with the known project constraints of \fig{cases}.
These constraints 
range from $Low$ to $High$ values.
If a case study does not mention a feature, then there
are no constraints on that feature, and the $combine$ function (line 4)
returns the entire range of that feature. Otherwise, $combine$
returns only the values from $Low$ to $High$.
For an example of the results of this combination process, see \fig{changed}.

In the case where a feature is $fixed$ to a single
value, 
then $Low = High$. Since there is no choice to be made for this
feature, SEESAW ignores it. The algorithm
 explores only those
 features with a range of $Options$ where
 $Low < High$ (line 5).
In each iteration of the algorithm, it is possible that one acceptable value
for a feature $X$ will be discovered. If so, the range for $X$
is reduced to that single
value, and the feature is not examined again (line 17).


The $score$ function shown at the bottom of
\fig{MWF} calls COCOMO/COQUALMO models 100 times,
each time selecting
random values for each feature $Options$. The median value
of these 100 simulations is the $score$ for the current project settings. As SEESAW executes,
the ranges in $Options$ are removed and replaced by single values (lines 16-17),
thus constraining the space of possible simulations.


SEESAW is a stochastic algorithm:
the selection of the next feature to explore is completely random (line 7).
We use this stochastic approach
 since much research from the 1990s showed the benefit of such search methods.
Not only can stochastic algorithms solve non-linear problems and escape from local minima/maxima, 
but they can also find solutions faster than complete search, and for larger problems~\cite{motwani95}.
For example, we have implemented a deterministic version of SEESAW that
replaces the random selection of {\em one} feature in line 7 with a search
through {\em all} features for
the best $\{Low,High\}$ value.  That algorithm ran much slower (runtimes were 12 times greater)
with nearly identical results to those of the stochastic search.

Crawford and Baker~\cite{crawford94} offer one explanation for the strange success of stochastic search.
For models
where the solutions are a small part of the total space, a complete search
wastes much time exploring uninformative areas of the problem. A stochastic search, 
on the other hand, does not get stuck in such  uninformative areas.

In order to support incremental decision making, SEESAW uses
a very large $P$ value to control its reasoning.   This
$P$ value is used to delay ``lose-lose'' decisions until the
later iterations of the algorithm.  Suppose our search has only constrained (say)
$pcap=5$ so far.  Our next randomly chosen feature might be  $data$,
so SEESAW tries $\{Low, High\}$ values of $data=2$ and
$data=5$.  It is possible that both of these values will result in scores
that are worse than the current score (using $pcap=5$ alone).
This means that
$data$ is not a valuable feature to control,
and picking either of the $\{Low,High\}$ values would be a ``lose-lose'' decision.
Using $P=0.95$,
SEESAW will very likely (95\% of the time) leave $data$ unconstrained
and pick another, potentially better,  feature to constrain on the next iteration.  The algorithm
will eventually come back to $data$, but if SEESAW delays making
that lose-lose decision, it has a better chance of making good
decisions early in the search.



SEESAW incrementally grows solutions
from unconstrained (where all features can take any value in $\{Low,High\}$)
to fully constrained (where all features are set to a single value).
This is unlike
exhaustive enumeration or simulated annealing or MaxWalkSat, which simultaneously offer settings to all features
at every step of their reasoning.

\fig{run} shows the effects of SEESAW adding constraints to the treatment.
In that plot, as ``$x$'' increases,
SEESAW is adding one new constraint.
At each ``$x$'' value, our models are run 100 times to generate predictions for effort (total staff months),
delivered defects (per KLOC), and months (calendar duration). 

After committing to all possible values, SEESAW does a {\em back-select} which checks if dropping
off the last x-value signiicantly changes the performance scores.
This is a fast process since SEESAW collects mean and standard deviaitions of all scores as it grows
the treatment along the x-axis. 
In the case of \fig{run}, the back-select ran from $x=26$ back to $x=15$
before if found a median result for mnthos or defects or effort that was signifincatly different to
the $x=26$ results
(using a t-test with a  95\% conifedence interval). 

As shown on \fig{run}, the region from $x=15$ to $x=26$ is ``noise''. The back-select
prunes this noise and SEESAW returns all the decisions
made from x=1 to before the noise starts. 

In our terminology, selecting  one value from a range  is a {\em constraint} on all  
values in the range. For example, if \fig{cases} includes a process maturity of (3,4,5)
and SEESAW selects ``5'', then that is three constraints.
The effects of adding constraints in shown by the decreased months, effort, and defect predictions
of \fig{run}.
Note how, as decisions are made, the score is minimized. Score minimization is desirable since
our scores
are calculated 
from  a combination of project predictions that we want to reduce 
(total effort, defects, development time). 

Returning now to the disucssion at the end of \tion{stochast}, recall that our ideal search engine:
\bi
\item Returns
the smaller set of constraint to project inputs...
\item 
...that  performs based across the space of possible tunings...
\item 
... and that comments on the stability of the result in the neighborhood of the solution.
\ei
SEESAW, followed by the visualization of \fig{run} fullfills all these requirements.
The solution is grown smallest to largest across the x-axis. If the solution gets too elaborate,
the back-select prunes it back. 
Consequently, SEESAW's recommendations can be quite short; e.g. in \fig{run},
SEESAW's treatment only mentions 13 of the 25 features of \fig{cparems}.

Also, by comparing the median results left and right of the treatment,
a user can check if make decisions within a stable zone.
Further he space around SEESAW's treatment is shown in \fig{run}: using
this diagram, a business user can ask the question ``what happens in only apply the first {\em half}
of SEESAW's recommendation''. 

This ability to se partial SESSAW results is an important feature of the tool.
Observe how, in 
\fig{run},
50\% of the defect reduction
arises from adding only 6 constraints to a project.
If a manager cannot implement all SEESAW's recommendations and a 50\% reduction
is adequate,
she might elect to  use just those first six decisions.
That is, SEESAW not only makes $R$ recommendations, it also reports on the value of
just applying just some subset of $r \subseteq R$.



