Experimental study of algorithms for connected row convex constraints

Date

2008-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

In recent years, many tractable classes of CSP problems have been identified. Solutions can be found for these problems by enforcing various levels of local consistency. An elimination algorithm to solve the problems of the class of CRC constraints which is based on the ideas of variable elimination and the efficient composition of CRC constraints has been proposed. A path-consistency algorithm, PC-CRC, obtained by instantiating a generic path-consistency algorithm called PC-GEN and tailored to CRC constraints is also in use.

In this thesis research, we implemented a random problem generator for the sparse constraint graph problems. We provided an efficient implementation of the elimination algorithm and carried out the empirical study of the elimination and PC-CRC algorithms. We also analyzed the behavior of elimination algorithm and compared its performance with that of PC-CRC. Our experimental results show that the elimination algorithm which uses fast composition behaves well in practice and reveals that it has a significant performance margin over the PC-CRC algorithm.

Description

Keywords

Variable elimination, PC-CRC algorithms, Connected row convex

Citation