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.

Parameter setting of the Hopfield network applied to TSP.

The major drawbacks of the continuous Hopfield network (CHN) model when it is used to solve some combinatorial problems, for instance, the traveling salesman problem (TSP), are the non feasibility of the obtained solutions and the trial-and-error setting values process of the model parameters. In this paper, both drawbacks are avoided by introducing a set of analytical conditions guaranteeing that any equilibrium point of the CHN characterizes a tour for the TSP. In this way, any instance of the TSP can be solved with this parameter setting. Some computational experiences are also included, allowing the solution of instances with sizes of up to 1000 cities.