A Hypothetical Reasoning Method for Computing Near-optimal Solution in polynomial Time

点击翻译按钮获取中文摘要

We have achieved a meaningful result in the area of efficient cost-based or weighted) hypothetical reasoning for computing a near-optimal solution which satisfies all given constraints. Prior to this research, we developed a polynomial-time cost-based hypothetical reasoning method, in which the set of described knowledge is transformed into linear inequalities and then an effioient approximate solution method of 0-1 integer programming called pivot and compliment method is applied to compute a near-optimal solution in polynomial time. While this method is very effective, it is hard for us to grasp its behavior operated in mathematical domain ; as a result, we can not improve its efficiency further by considering the knowledge structure of given problems. Thus we have developed a polynomial-time hypothetical reasoning method called networked bubble propagation (NBP) method, which performs an inference operation conceptually similar to the pivot and compliment method on a unique knowledge network. The time-consuming pivoting operation exchanging the states of basis and non-basis nodes (variables in 0-1 integer programming) is improved by considering the knowl-edge structure. The low-order polynomial-time efficiency of the NBP method is shown experimentally. It can be said that the result of this research is also meaningful in bridging symbol-oriented Al reasoning and OR (operation research) computation operated mathematically in multi-dimensional numerical domains.