%// constrains ATTRIBUTE to a single RANGE and generates a score
\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$.

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).

SEESAW prunes the final  recommendations (line 21).
This function pop off the $N$
selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls
any final irrelevancies in the selections.

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 was designed after observing experimentally
that
the most interesting ranges in $Options$
are generally 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.
In fact,
SEESAW takes its name from the way the algorithm seesaws between extreme values.
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.

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.


\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}

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
simulated annealing or MaxWalkSat, which simultaneously offer settings to all features
at every step of their reasoning.
\fig{run} shows a single run of SEESAW: each dot marks one selection  (lines 16,17,18 of \fig{MWF}).
In our terminology, selecting  one value from a range  is a {\em decision} 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 decisions.
(this is why the 29 dots of
\fig{run} result in 100 decisions).
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). 
\begin{figure}
\centering
\includegraphics[width=3in]{default.pdf}
\caption{Single run of SEESAW, score normalized min..max to 0..1}
\label{fig:run}
\end{figure}

Incremental decision making  is an important property of SEESAW.
Observe how, in 
\fig{run},
50\% of the score reduction
arises from around 15\% of the decisions.
If a manager cannot implement all SEESAW's recommendations and a 50\% reduction
is adequate,
she might elect to  use just these top 15\% 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$.


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.


