Report Number:  CSM-261 
Report Title:   The validity of normality assumption in CSP research 
Authors:        Alvin C. M. Kwan & Edward P. K. Tsang
 
 
                                 Abstract

There are many new methods for solving constraint satisfaction problems
proposed in recent years.  Due to their complexity, a theoretical analysis
on their average-case behaviours seems to be very difficult.  Researchers
tend to adopt an empirical approach to evaluate constraint satisfaction
techniques.  When empirical results are ready, statistical techniques are
often employed for analysis.  The question is which statistics to use.  
Some recent research uses parametric tests such as t-test and ANOVA.  
However those tests assume that the characteristic of the normal curve
can be applied.  In this paper, we provide evidence that the normality 
assumption is often not valid in the results produced by a range of 
constraint satisfaction algorithm-heuristic combinations on random binary 
constraint problems and 3-colouring problems, particularly when a problem 
is within the "mushy region", which are popular benchmark problems for 
evaluating CSP methods.  The failure of normality assumption highlights 
the need for some statistics which do not rely on the normality assumption 
to analyse empirical results from CSP research.  We believe that non-
parametric techniques could be the right tools for that purpose.