|
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/14435
|
| Title: | EXPERIMENTS WITH AN INTEGER PROGRAMMING FORMULATION OF AN EXPERT SYSTEM |
| Authors: | Dhar, Vasant
Ranganathan, Nicky |
| Issue Date: | Mar-1989 |
| Publisher: | Stern School of Business, New York University |
| Series/Report no.: | IS-89-039 |
| Abstract: | We present expert system (ES) and Integer Programming (IP) formulations
of an NP-complete constraint satisfaction problem (CSP). The problem
involves generating a plan for assigning faculty to courses given a
variety of constraints and preferences and other tentative data. The
expert system consists of a heuristic rule-based problem solver and a
truth maintenance system. The IP model consists of about 700 zero-one
decision variables and 300 constraints. We describe and contrast the
expert system and IP models in terms of behavior, quality of results,
and computational performance. We find that the expressiveness of the IP
model is hampered by its single objective function, inability to encode
various types of complex preferences, the lack of useful output when it
fails to find a feasible solution, and a general lack of control over
inference. It is also difficult to make incremental revisions to the
plan produced by the IP model. In contrast, the truth maintenance system
maintains justifications for assignments, which makes it possible to
reason about incremental modifications to a plan. In terms of
performance, we found that whenever the IP approach finds a solution, it
does so quickly using the Pivot and Complement heuristic of Balas and
Martin (1980). The branch and bound always failed to find a feasible
integer solution when the heuristic failed to find one. |
| URI: | http://hdl.handle.net/2451/14435 |
| Appears in Collections: | IOMS: Information Systems Working Papers
|
All items in Faculty Digital Archive are protected by copyright, with all rights reserved.
|
