DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS

Abstract

Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of constraints. In this paper we present a formal specification of dependency directed backtracking as applied to this problem. We also generalize the satisficing assignment problem to include limited resource constraints that arise in operations research and industrial engineering. We discuss several new search heuristics that can be applied to this generalized problem, and give some empirical results on the performance of these heuristics.