Experiments with an Integer Programming Formulation of an Expert System

We present expert system (ES) and Integer Programming (IP) formulations of an NP-completeconstraint satisfaction problem (CSP). The problem involves generating aplan for assigning faculty to courses given a variety of constraints and preferences andother tentative data. The expert system consists of a heuristic rule-based problemsolver and a truth maintenance system. The IP model consists of about 700 zero-onedecision variables and 300 constraints. We describe and contrast the expert systemand 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 objectivefunction, inability to encode various types of complex preferences, the lack of usefuloutput 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 IPmodel. 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, itdoes 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 heuristicfailed to find one