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

我们在有效的基于成本或加权的假设推理领域取得了有意义的结果，用于计算满足所有给定约束的近乎最优的解决方案。在这项研究之前，我们开发了一种基于多项式时间成本的假设推理方法，其中将描述的知识集转换为线性不等式，然后应用称为枢轴和补码方法的0-1整数规划的高效近似求解方法来计算多项式时间内的接近最优解。虽然这种方法非常有效，但我们很难掌握其在数学领域的行为；结果，我们无法通过考虑给定问题的知识结构来进一步提高其效率。因此，我们开发了一种称为网络气泡传播（NBP）方法的多项式时间假设推理方法，该方法在概念上类似于独特知识网络上的枢轴和补充方法执行推理操作。通过考虑知识结构，改进了交换基节点和非基节点（0-1整数规划中的变量）状态的耗时旋转操作。实验证明了 NBP 方法的低阶多项式时间效率。可以说，这项研究结果对于桥接面向符号的人工智能推理和多维数值领域的数学运算OR（运筹学）计算也很有意义。

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.