DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS
|Publisher:||Stern School of Business, New York University|
|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.|
|Appears in Collections:||IOMS: Information Systems Working Papers|
Items in FDA are protected by copyright, with all rights reserved, unless otherwise indicated.