|
Archive@NYU >
Stern School of Business >
IOMS: Information Systems Working Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2451/14423
|
| Title: | A PROBLEM-SOLVER/TMS ARCHITECTURE FOR GENERAL CONSTRAINT SATISFACTION PROBLEMS |
| Authors: | Croker, Albert
Dhar, Vasant |
| Issue Date: | Dec-1988 |
| Publisher: | Stern School of Business, New York University |
| Series/Report no.: | IS-89-001 |
| Abstract: | Constraints, in various forms, are ubiquitous to design problems. In
this paper, we provide a formal characterization of a generalized
constraint satisfaction problem (CSP) that can be used to model many
types of design/planning problems, and the architecture of an imlemented
reasoning system for solving this problem. The architecture includes a
truth maintenance system (TMS) which is specifically designed to reason
about the relationships expressed in the constraints as a problem
solution evolves. The CSP consists of two types of data. The first type
of datum corresponds to assignments that are handled by the problem
solver, and the second type corresponds to constraint terms handled by
the TMS. The dependency network, representing the relationships among
constraint terms, is static and generally quite small, depending on the
number of constraint terms. Also, justifications are never manipulated
(only evaluated). This results in an architecture that makes efficient
use of both space and time. The need for efficient TMSs, even though
these might deal only with certain classes of problems, is underscored
by the fact that general purpose TMSs have often been found to be highly
inefficient for solving large problems. We also show how certain
instances of the generalized CSP can be formulated as an integer
programming problem, special cases of which can be solved efficiently
using mathematical (integer) programming techniques. |
| URI: | http://hdl.handle.net/2451/14423 |
| Appears in Collections: | IOMS: Information Systems Working Papers
|
All items in Faculty Digital Archive are protected by copyright, with all rights reserved.
|
