SL method for computing a near-optimal solution using linear and non-linear programming in cost-based hypothetical reasoning

Hypothetical reasoning is an important framework for knowledge-based systems, however, its inference time grows exponentially with respect to problem size. In this paper, we present an understandable efficient method called slide-down and lift-up (SL) method which uses a linear programming technique for determining an initial search point and a non-linear programming technique for efficiently finding a near-optimal 0-1 solution. To escape from trapping into local optima, we have developed a new local handler, which systematically fixes a variable to a locally consistent value. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood. (C) 2002 Elsevier Science B.V. All rights reserved.