الفهرس 
coverOnly 14 pages are availabe for public view
 |  | from | 142 |  |  |
| | | from | 142 | | |
Abstract
The Constraint Satisfaction Problem (CSP) is a powerful and efficient
framework for modelling and solving many real world problems. Many
problems in artificial intelligence, computer science, engineering, and other
disciplines can be naturally represented as constraint satisfaction problems.
In a CSP, the goal is to find values for variables such that these values are not
violating any constraints that hold between the variables. It often happens
that a CSP is over-constrained, thus researchers may seek to partially solve
the problem such as in maximal constraint satisfaction problem (Max-CSP).
In Max-CSP framework, the aim is to satisfying maximum number of the
constraints.
The objective of this thesis is introducing a study on CSPs and Max-
CSPs. Larrosa and Schiex ([25],2004) introduced advanced node consistency
property NC* to improve the lower bound of branch and bound (B&B)
algorithm. Then, Zivan and Meisels in 2007 presented NC*-CBJ algorithm
which developed B&B-NC* algorithm without improving its lower bound.
During our study, we give a new treatment for improving the lower bound
of B&B-NC* and NC*-CBJ algorithms. The proposed treatment leads to
vi
suggesting new algorithm, M-NC*-CBJ which is a natural successor of NC*-
CBJ algorithm including the modification of the lower bound. By comparing
with the results of NC*-CBJ, the experimental results of M-NC*-CBJ on
random CSPs show improvement both in execution times and number of
assignments.
This thesis consists of four chapters, conclusion, two appendices, and
list of the most recent references used in this study.
The first chapter presents a brief introduction to CSPs. The formal definition
of CSP is also given. In addition, classification of CSP according to
types of variables and constraints is introduced. Furthermore, this chapter
contains the explanation of some problems and how modelling them as
CSP. Also, we describe the graphical representation of CSP and how can
be exploited to simplify the problem solving. Finally, a brief overview on
some practical applications of CSP is included.
The second chapter contains a brief description of the basic techniques
for solving CSPs. The proposed techniques are searching strategy, constraint
propagation, and combining the search with constraint propagation.
Also, some ordering heuristics methods for variables and values in the search
strategy are included.
In chapter three, some briefly information about the partial constraint
satisfaction problem (PCSP) is introduced. Then, we focus on Maximal
Constraint Satisfaction Problem (Max-CSP) which is a special case of PCSP.
Also, description of the basic branch and bound algorithm for solving Max-
CSP is given. Furthermore, a brief description of NC*-CBJ algorithm which
is modified in chapter four, is presented.
Chapter four gives a new treatment for improving NC*-CBJ lower bound,
producing M-NC*-CBJ algorithm. This via adding new bound resulting
vii
from taking into account more inconsistencies resulted from the partially
incompatible relation between the future variables. Also, analysis of complexity
of the additional part to NC*-CBJ lower bound and providing a
proof that M-NC*-CBJ lower bound is still lower bound are included. Finally,
this chapter gives experimental results of M-NC*-CBJ; by comparing
with previous results, showing the efficiency and robustness of M-NC*-CBJ
and its superiority with respect to the previous NC*-CBJ algorithm. This
treatment is considered a new contribution in this field.
In Appendix A, the implementation of M-NC*-CBJ algorithm that is
described in the fourth chapter, is written using the programming language
C++.
Appendix B is devoted to illustrating the execution of M-NC*-CBJ algorithm
on a simple example of CSP. The execution shows that the problem
is over-constrained CSP.
Finally, we present a conclusion that summarizes the obtained results
and suggest some prospectives for future works.
Viii