Year

2010

Degree Name

Doctor of Philosophy

Department

School of Computer Science and Software Engineering - Faculty of Informatics

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. In this thesis, we present various methods to solve SCSPs.

We first consider how a SCSP might be relaxed: we relax individual constraints until an acceptable solution can be obtained. A second semiring is used to define a measure of difference between the original problem and the relaxed problem. This research was first presented at the International Workshop on Preferences and Soft Constraints at CP-2005 [40], and an extended version of the paper has been published in the Information Processing Letters journal [41].

We then show how the two semirings of a relaxed SCSP can be combined into a single semiring structure. This combined semiring structure will make it possible to use existing tools for solving SCSPs to solve Combined SCSPs. This work appears in Leenen et al. [42].

The remainder of this thesis focusses on algorithms to solve SCSPs. A significant amount of work has been devoted to solving the well-known maximum satisfiability problem (Max SAT) [1, 63] and the related Weighted M ax -SAT problem. This prompted us to modify the methods for solving Max-SAT, into methods for solving SCSPs. We show how to translate a SCSP into a variant of the Weighted Max –SAT Problem, which we call a Weighted Semiring Max -SAT problem, and then present a local search algorithm that is a modification of the GSAT algorithm for solving Max -SAT. This work appears in Leenen et al. [38].

Finally, we extend well-known algorithms for maximal constraint satisfaction into SCSP algorithms. We present a branch and bound algorithm, a backjumping algorithm, and a forward checking algorithm. Our branch and bound algorithm performs significantly better than CONFLEX [17], a well-known fuzzy CSP solver. The branch and bound algorithm has been presented in Leenen et al. [38]. The forward checking and backjumping algorithms perform better than the branch and bound algorithm on harder problems. This work appears Leenen et al. [39 ].

List of Publications resulting from the research presented in this thesis: - L. Leenen, T. Meyer, and A. Ghose. Relaxations of semiring constraint satisfaction problems. In Proceedings of the 7 th International Workshop on Preferences and Soft Constraints (SOFT-05), 2005. - L. Leenen, T. Meyer, P. H arvey, and A. Ghose. A relaxation of a semiring constraint satisfaction problem using combined semirings. In Proceedings of the 9th Pacific Rim International Conference on Artificial Intelligence (PR ICAI-2006), pages 907-911, 2006. - L. Leenen, T. Meyer, and A. Ghose. Relaxations of semiring constraint satisfaction problems. Information Processing Letters, 103(5 ):177-182, 2007. - L. Leenen, A. Anbulagan, T. Meyer, and AG hose. Modelling and solving semiring constraint satisfaction problems by transformation to w eighted semiring max-SAT. In Proceedings of the Twentieth Australian Joint Conference on Artificial Intelligence (AI-2007), pages 202-212, 2007. - L. Leenen and A. Ghose. Branch and bound algorithms to solve semiring constraint satisfaction problems. In Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence (PRICAI-2008), 2008 .

Download

02Whole.pdf (506 kB)

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.