Empirical analysis of Solution Guided Multi-Point Constructive Searc

Solution Guided Multi-Point Constructive Search (SGMPCS) is a constructive search technique inspired by local search algorithms that guide search from multiple viewpoints. SGMPCS consists of a series of resource-limited backtracking searches: each starting from an empty solution or guided by one of a set of high quality, elite solutions encountered earlier. The thesis of this dissertation is that SGMPCS works, in part, because of two factors: the benefit of revisiting the areas near good solutions, and through the exploitation of heavy-tails. We provide a detailed analysis of the various parameters of SGMPCS on a variety of constraint satisfaction problems. We show evidence of heavy-tailed distributions for only the sets of problems where SGMPCS performs well. We show how performance is correlated with how well the evaluation of guiding solutions predicts actual distance to a solution. Finally, we explore various static cost models of SGMPCS performance.