Faculty Digital Archive

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

Files in This Item:

File Description SizeFormat
IS-89-001.pdf4.49 MBAdobe PDFView/Open

Items in Faculty Digital Archive are protected by copyright, with all rights reserved, unless otherwise indicated.

 

The contents of the FDA may be subject to copyright, be offered under a Creative Commons license, or be in the public domain.
Please check items for rights statements. For information about NYU’s copyright policy, see http://www.nyu.edu/footer/copyright-and-fair-use.html 
Valid XHTML 1.0 | CSS