Limited space precludes a survey of propositional satisfiability algorithms and linear programming methods in this paper. See [Cook and Mitchell1997] for a survey of satisfiability and [Karloff1991] for a survey of linear programming.
Our work was inspired by the idea of compiling probabilistic planning problems to MAJSAT [Majercik and Littman1998]. It seemed that if one could extend the SAT ``virtual machine'' to support probabilistic reasoning, then it would be useful to consider the orthogonal extension to handle metric constraints.
Other researchers have combined logical and constraint reasoning, usually in the context of programming languages. CLPR may be thought of as an integration of Prolog and linear programming, and this work introduced the notion of incremental Simplex [Jaffar et al.1992]. Saraswat's thesis [Saraswat1989] formulates a family of programming languages which operate through the incremental construction of a constraint framework. CHIP [Van Hentenryck1989] augments logic programming with the tools to efficiently solve constraint satisfaction problems (e.g., consistency checking), but deals only with variables over finite domains. NUMERICA extends this work by adding a variety of differential equation solvers to the mix [Van Hentenryck1997]. Hooker et al. describe a technique for combining linear programming and constraint propagation [Hooker et al.1999].
BLACKBOX uses a translate/solve/decode scheme for planning and satisfiability [Kautz and Selman1998]. ZENO is a causal link temporal planner which handled resources by calling an incremental Simplex algorithm within the plan-refinement loop [Penberthy and Weld1994]. The GRAPHPLAN [Blum and Furst1995] descendant IPP has also been extended to handle metric reasoning in its plan graph [Koehler1998]. SIPE [Wilkins1990] and OPLAN [Currie and Tate1991] are industrial strength planners which include resource planning capabilities. Two recent systems address the metric planning problem using compilation to integer programming [Kautz and Walser1999,Vossen et al.1999].