Analyzing and Extending an Infeasibility Analysis Algorithm

Constraint satisfaction problems (CSPs) comprise of finding assignments to a set of variables that satisfy some mathematical constraints. Unsatisfiable constraint problems are CSPs with no solution. However, useful characteristic subsets of the problem may be extracted with algorithms such as the MARCO algorithm, which outperforms the best known algorithms in the literature. A heuristic choice in the algorithm affects how it traverses the search space to output these subsets. The effect of this choice on the performance of the algorithm is analyzed. In addition, three different improvements to the algorithm are proposed: the first of these improvements sacrifices completeness in terms of one type of subset in order to improve the output rate of another; The second and third are variations of a local search in between iterations of the algorithm which result in improved guidance in the search space. The performance of these improvements is analyzed both individually and in combinations across a variety of benchmarks and they are shown to improve the output rate of MARCO