The generalized quadratic knapsack problem. A neuronal network approach.
The solution of an optimization problem through the continuous Hopfield network (CHN) is based on some energy or Lyapunov function, which decreases as the system evolves until a local minimum value is attained. A new energy function is proposed in this paper so that any 0-1 linear constrains programming with quadratic objective function can be solved. This problem, denoted as the generalized quadratic knapsack problem (GQKP), includes as particular cases well-known problems such as the traveling salesman problem (TSP) and the quadratic assignment problem (QAP). This new energy function generalizes those proposed by other authors. Through this energy function, any GQKP can be solved with an appropriate parameter setting procedure, which is detailed in this paper. As a particular case, and in order to test this generalized energy function, some computational experiments solving the traveling salesman problem are also included.
Instituto Nacional de Estadística, Josefa Valcárcel 46, 28027 Madrid, Spain.
Pedro M
PM
Talaván
Javier
J
Yáñez
D000465:Algorithms; D001185:Artificial Intelligence; D001288:Attention / Q000502:physiology*; D019277:Entropy; D006801:Humans; D016571:Neural Networks, Computer; D011340:Problem Solving / Q000502:physiology*