Journal of the Japanese Society for Artificial Intelligence
Online ISSN : 2435-8614
Print ISSN : 2188-2266
Print ISSN:0912-8085 until 2013
SL Method for Computing a Near-Optimal Solution Using Linear and Non-Linear Programming Methods in Cost-Based Hypothetical Reasoning
Yutaka MATSUOTomoyuki FUTADAMitsuru ISHIZUKA
Author information
MAGAZINE FREE ACCESS

1998 Volume 13 Issue 6 Pages 953-961

Details
Abstract

Hypothetical reasoning is an important framework for knowledge based systems due to its theoretical basis and its usefulness for many practical problems. Since its inference time grows exponentially with respect to problem size, its efficiency becomes the most crucial problem when applying it to practical problems. Some approximate solution methods have been proposed for computing cost-based hypothetical reasoning problems efficiently;however, their mechanisms are complex for human to understand. We here present an understandable efficient method called SL(slide-down and lift-up) method, which uses a linear programming technique, namely simplex method, for determining aninitial 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 when a local optimal point is detected. This SL method can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time when respect to problem size. From pictorially illustrated behaviors of the SL method, its simple inference mechanism can be easily understood.

Content from these authors
© 1998 The Japaense Society for Artificial Intelligence
Previous article Next article
feedback
Top