On the Discovery and Generation of Certain Heuristics

This paper explores the paradigm that heuristics are discovered by consulting simplified models of the problem domain. After describing the features of typical heuristics on some popular problems, we demonstrate that these heuristics can be obtained by the process of deleting constraints from the original problem and solving the relaxed problem which ensues. We then outline a scheme for generating such heuristics mechanically, which involves systematic refinement and deletion of constraints from the original problem specification until a semidecomposable model is identified. The solution to the latter constitutes a heuristic for the former.