Staff View
Two approaches to the hierarchical solution of constraint satisfaction problems

Descriptive

Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
Genre (authority = RULIB-FS)
Other
Genre (authority = marcgt)
technical report
Genre (authority = RULIB-FS)
Dissertation
PhysicalDescription
InternetMediaType
application/pdf
Extent
1 online resource (240 pages) : illustrations
Note (type = special display note)
Technical report LCSR-TR-256
Name (type = corporate); (authority = RutgersOrg-School)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
TypeOfResource
Text
TitleInfo
Title
Two approaches to the hierarchical solution of constraint satisfaction problems
Abstract (type = abstract)
Constraint Satisfaction Problems (CSPs) involve assigning values to a finite set of variables from their finite domains such that a finite set of constraints is satisfied. Graph coloring, Scheduling and Time-table design are some of the commonly occurring CSPs. All general solution procedures for CSPs are based upon a combinatorial enumeration of variable bindings, with the addition of clever devices to reduce the number of nodes explored in the corresponding search tree. CSPs, however, are NP-hard, and general-purpose search algorithms are slow. This research explores the application of problem decomposition to construct faster CSP solvers

Previous applications of Problem Decomposition to CSPs have been based upon the representation of a CSP as a Constraint Graph, where nodes represent variables, and arcs represent constraints. A tree-shaped constraint graph, after some preprocessing on the nodes, can be solved without backtrack (Freuder, 82). Researchers have proposed different methods for reducing a constraint graph into a tree of node-clusters, with the cost of solution dependent on the size of the largest such cluster.

Tree-clustering based methods of decomposition fail on CSPs with global constraints, where any cluster including the global constraint has to include all the problem's variables. This thesis proposes reducing redundant constraint-checks as an alternative motivation for problem decomposition in CSPs. The decomposition algorithms developed here are applicable to CSPs unrestricted on constraint arity.

There are three major components to this research. The first is the development of a framework, named <I>bottom-up solution</I>, for solving a CSP through its decomposition. It is aimed at handling decompositions that do not completely partition a problem into independent components. The framework allows for the efficient handling of problem components dependent upon other subproblems. The bottom-up solution framework has been implemented on top of the basic Backtrack and Forward-Check search algorithms.

The thesis then introduces two problem decomposition algorithms aimed directly at reducing redundant constraint checks. The main insight here is that redundant constraint tests are caused by artificial dependencies of constraints on non-argument variables, set up by the serial nature of combinatorial enumeration used as the basis for search algorithms. The decomposition algorithms seek to reduce artificial dependencies in a problem, and the resulting decompositions can be solved in the bottom-up solution framework.

The third component of this thesis focuses on global and high-arity constraints. The complexity of a class of problems with a particular constraint topology is defined by the highest arity of its constraint set. This is reflected in the inability of search algorithms to take advantage of global constraints to reduce the size of the explored search space. This thesis proposes a procedure for the syntactic decomposition of a global constraint in a problem. This decomposition is used to define an abstract problem layer, and a new hierarchical problem which is equivalent to the original problem, and in which the global constraint is replaced with a set of smaller arity constraints.

The problem decomposition techniques are evaluated on random problems and on some sample application domains. In general the decomposition is shown to be more beneficial for problems which, when solved in their original form, exhibit high artificial serial dependencies and produce bushier search trees. Global constraint decomposition is demonstrated on some sample application domains, and shown to significantly reduce search effort.

Constraint satisfaction problems are difficult enough that there do not exist any reliable and effective general purpose problem solving heuristics and evaluation functions. It is therefore significant that the <I>DOI decomposition</I> algorithm proposed in this research is guaranteed never to make the problem harder to solve.

The primary contribution of this research is in the form of new problem solving methods for general constraint satisfaction problems which significantly improve performance, particularly for harder problems. It also extends the current understanding of what makes constraint satisfaction problems difficult to solve and where search algorithms spend their effort. On the more general side, this thesis promotes a deeper understanding of the application and benefits of problem decomposition as a problem solving strategy.
Name (type = personal)
NamePart (type = family)
Mohan
NamePart (type = given)
Sunil Kumar
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Ellman
NamePart (type = given)
Thomas
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (type = text); (authority = RULIB)
chair
OriginInfo
CopyrightDate (encoding = w3cdtf); (qualifier = exact)
1996-01
DateCreated (encoding = w3cdtf); (qualifier = exact); (keyDate = yes)
1996-01
RelatedItem (type = host)
TitleInfo
Title
Computer Science (New Brunswick)
Identifier (type = local)
rucore21032500001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/t3-2te9-bt37
Back to the top

Rights

RightsDeclaration (AUTHORITY = rightsstatements.org); (TYPE = IN COPYRIGHT); (ID = http://rightsstatements.org/vocab/InC/1.0/)
This Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.4
ApplicationName
GPL Ghostscript 9.07
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:27
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:37:27
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019