Cavalieri S
University of Catania, Faculty of Engineering, Institute of Informatic and Telecommunications, Italy.
Int J Neural Syst. 1999 Feb;9(1):27-39. doi: 10.1142/s0129065799000046.
The paper deals with integer linear programming problems. As is well known, these are extremely complex problems, even when the number of integer variables is quite low. Literature provides examples of various methods to solve such problems, some of which are of a heuristic nature. This paper proposes an alternative strategy based on the Hopfield neural network. The advantage of the strategy essentially lies in the fact that hardware implementation of the neural model allows for the time required to obtain a solution so as not depend on the size of the problem to be solved. The paper presents a particular class of integer linear programming problems, including well-known problems such as the Travelling Salesman Problem and the Set Covering Problem. After a brief description of this class of problems, it is demonstrated that the original Hopfield model is incapable of supplying valid solutions. This is attributed to the presence of constant bias currents in the dynamic of the neural model. A demonstration of this is given and then a novel neural model is presented which continues to be based on the same architecture as the Hopfield model, but introduces modifications thanks to which the integer linear programming problems presented can be solved. Some numerical examples and concluding remarks highlight the solving capacity of the novel neural model.
本文探讨整数线性规划问题。众所周知，即使整数变量数量相当少，这些问题也极其复杂。文献中提供了各种解决此类问题的方法示例，其中一些方法具有启发式性质。本文提出了一种基于霍普菲尔德神经网络的替代策略。该策略的优势主要在于神经模型的硬件实现使得获得解决方案所需的时间不依赖于待解决问题的规模。本文介绍了一类特定的整数线性规划问题，包括诸如旅行商问题和集合覆盖问题等著名问题。在对这类问题进行简要描述之后，证明了原始的霍普菲尔德模型无法提供有效的解决方案。这归因于神经模型动态中存在恒定偏置电流。对此进行了论证，然后提出了一种新颖的神经模型，该模型继续基于与霍普菲尔德模型相同的架构，但通过引入修改能够解决所提出的整数线性规划问题。一些数值示例和结论突出了新颖神经模型的求解能力。
