Title

Branch and Bound Algorithms to Solve Semiring Constraint Satisfaction Problems

RIS ID

27060

Publication Details

Leenen, L. & Ghose, A. K. (2008). Branch and Bound Algorithms to Solve Semiring Constraint Satisfaction Problems. In T. Ho & Z. Zhou (Eds.), Pacific Rim International Conference on Artificial Intelligence (pp. 991-997). Germany: Springer-Verlag.

Abstract

The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. Considerable research has been done in solving SCSPs, but limited work has been done in building general SCSP solvers. This paper is part of a series in which incremental changes are made to a branch and bound (BnB) algorithm for solving SCSPs. We present two variants of a BnB algorithm: a backjumping algorithm and a forward checking algorithm. These algorithms are based on the maximal constraints algorithms of Freuder and Wallace [1], and we show they perform better than the BnB algorithm on some problem instances.

Please refer to publisher version or contact your library.

Share

COinS
 

Link to publisher version (DOI)

http://dx.doi.org/10.1007/978-3-540-89197-0_96