The application of automated reasoning to formal models of combinatorial optimization

摘要

Many formalisms have been proposed over the years to capture combinatorial optimization algorithms such as dynamic programming, branch and bound, and greedy. In 1989 Helman [9] presented a common formalism that captures dynamic programming and branch and bound type algorithms. The formalism was later extended to include greedy algorithms. In this paper, we describe the application of automated reasoning techniques to the domain of our model, in particular considering some representational issues and demonstrating that proofs about the model can be obtained by an automated reasoning program. The long-term objective of this research is to develop a methodology for using automated reasoning to establish new results within the theory, including the derivation of new lower bounds and the discovery (and verification) of new combinatorial search strategies.