TY - GEN

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

AU - Ishizuka, Mitsuru

AU - Matsuo, Yutaka

PY - 1998

Y1 - 1998

N2 - Hypothetical reasoning is an important framework for knowledgebased systems because it is theoretically founded and it is useful 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, for humans their mechanisms are complex to understand. In this paper, we present an understandable efficient method called SL (slide-down and lift-up) method which uses a linear programming technique, namely simplex method, 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 when a locally optimal point is detected. This SL method can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time with respect to problem size. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.

AB - Hypothetical reasoning is an important framework for knowledgebased systems because it is theoretically founded and it is useful 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, for humans their mechanisms are complex to understand. In this paper, we present an understandable efficient method called SL (slide-down and lift-up) method which uses a linear programming technique, namely simplex method, 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 when a locally optimal point is detected. This SL method can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time with respect to problem size. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.

UR - http://www.scopus.com/inward/record.url?scp=80054880050&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054880050&partnerID=8YFLogxK

U2 - 10.1007/BFb0095304

DO - 10.1007/BFb0095304

M3 - Conference contribution

AN - SCOPUS:80054880050

SN - 354065271X

SN - 9783540652717

VL - 1531

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 611

EP - 625

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

T2 - 5th Pacific Rim Intemational Conference on Artificial Intelligence, PRICAI 1998

Y2 - 22 November 1998 through 27 November 1998

ER -