Study of State Space Search by Lagrangian Method for Combinatorial Problems

我们提出了一种神经网络LPPH，它比传统的方法更有效地解决了命题微积分的可满足性问题。LPPH基于拉格朗日方法，其动力学用一组连续微分方程表示。在本项目中，我们将研究以下内容。(1) LPPH动力学有一个称为“衰减因子”的参数。讨论了衰减因子与全局收敛性之间的关系。根据讨论的结果，我们提出了具有两种衰减因子的LPPH动力学。它们分别被称为长期记忆和短期记忆。实验证明了该方法的有效性。(2)提出了另一种改进动力学的方法。动力学的参数被称为“注意系数”。通过控制系数，找到难以满足的CNF子句集，并优先满足。实验结果表明，该方法特别适用于疑难问题的求解。(3)提出了一种基于拉格朗日方法的路由算法。该方法比传统方法更有效地解决了一些小而拥挤的路由问题。(4)我们研究了用CNF给出一些初步解的情况。初步解决方案来自背景知识、初步搜索、启发式或附加约束，以便找到的解决方案必须与给定的解决方案相似。我们在LPPH动力学中引入“偏置”来处理初步解。实验结果表明，即使存在一些不确定性和/或误差，所提出的动力学方法也能有效地找到给定初始解的最接近或近似最接近解。

We have proposed a neural network called LPPH which solves the satisfiability problem of propositional calculus (SAT) more efficiently than the conventional methods. The LPPH is based on Lagrangian method, and its dynamics is represented by a set of continuous differential equations. In this project, we investigate the following.(1) The LPPH dynamics has a parameter called "decay factor". We discusse the relationship between the decay factor and the global convergence property. From the result of the discussion we proposed the LPPH dynamics which has two types of decay factor. They are called long and short term memory, respectively. By experiment their effectiveness is proved.(2) Another improvement of the dynamics is proposed. The dynamics has parameters called "coefficients of attention". By controlling the coefficients, sets of clauses of the CNF which are hard to satisfy are found and satisfied by priority. Experimental results show the dynamics is effective especially for difficult problems.(3) A routing algorithm which is based on Lagrangian method is proposed. Some small but congested routing problems are solved more effectively then the conventional methods.(4) We investigate the cases where some preliminary solution is given with a CNF.The preliminary solution comes from the background knowledge, the preliminary search, the heuristics, or the additional constraint such that the solution to be found must be similar to the given one. We introduce "bias" to the LPPH dynamics to deal with the preliminary solution. Experimental results show that the proposed dynamics can effectively find the nearest or approximately nearest solution to the given preliminary solution even if it includes some uncertainties and/or errors.