SL Method for Computing a Near-Optimal Solution Using Linear and Non-Linear Programming Methods in Cost-Based Hypothetical Reasoning

DOI Web Site 7 Citations 16 References
  • MATSUO Yutaka
    Dept.of Information and Communication Engineering, Faculty of Engineering, The University of Tokyo
  • FUTADA Tomoyuki
    Dept.of Information and Communication Engineering, Faculty of Engineering, The University of Tokyo
  • ISHIZUKA Mitsuru
    Dept.of Information and Communication Engineering, Faculty of Engineering, The University of Tokyo

Bibliographic Information

Other Title
  • SL法 : 線形・非線形計画法の併用によるコストに基づく仮説推論の準最適解計算
  • SLホウ : センケイ ・ ヒセンケイ ケイカクホウ ノ ヘイヨウ ニ ヨル

Search this article

Description

<p>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.</p>

Journal

Citations (7)*help

See more

References(16)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top